Instructor: Funda Ergun

Welcome to CSCI 503!

I will use this page to post various announcements and documents; any information you need about this class will be in one of these documents. Please check this page regularly for updates.

Regarding homework submissions, please look below to where the assignments are for more info.

Sections from CLRS: Chapters 2, 3, 4 (except 4.2, 4.6), 7 (except we were not very thorough on the analysis of randomized quicksort), 8.1, 9, 16.1, 16.2, 16.3.

Instructor: Funda Ergun. Office: LH 428C. Email: fergun@indiana.edu.

Instructor office hours: M 1:45 --2:45 or by appointment.

AIs: We have a bunch. Stay tuned for contact and office hour information.

Textbook: Introduction to Algorithms. T. Cormen, C. Leiserson, R. Rivest, C. Stein.

This is a crucial course for any computer scientist (as our MS and PhD requirements demonstrate), and is quite mathematical. You will not do major/complicated programming here. It is also rumored to help with interview questions when you're looking for a job. But, most importantly, in a world where computer programs do so much for us, you will learn how to solve computational problems. By the time you get out, you should be ready to analyze most algorithms that come your way, and look at any theoretical problem, understand its requirements, and design a correct (and hopefully efficient) solution for it.

At the end of this course, you should be able to:

- Given an algorithm, analyze its correctness and running time.
- Given a problem, design a correct and efficient algorithm for it, express it in a form that a programmer can easily convert into code.
- Have an idea about what problems are intractable, and basic algorithms for those that are tractable.
- Know the mathematical techniques that you will need to analyze your algorithms.
- Enjoy designing algorithms. I will be giving out puzzles from time to time -- they are not only for your enjoyment, but many are known to have appeared as interview questions in the past.

This is a theoretical, graduate course; thus, we expect you to come with a certain amount of discrete math/data structures/algorithms knowledge from your undergrad studies. These include a comfortable level of basic arithmetics and algebra (are you super fluent with logs and exponents?), a good intuition about proof techniques (induction, contradiction, proof by counterexample, etc), discrete math/logic (sums, pigeonhole principle, sets, and so on), graph algorithms (DFS, BFS fluency, how do MST or SP algorithms work?), basic data structures (how good are you with balancing heaps?), big Oh and big Theta, basic algorithm design (types of recursion, how to get rid of recursion), and so on. For an idea about what IU undergrads are expected to have mastered by the time they start grad school, check out the curricula for 343 and 403.

Grade distribution: one midterm, around 5 homeworks, one project, final. Percentages 25, 25, 15, 35 per cent respectively. No collaboration allowed unless otherwise noted.

Late penalties: 10 points each late calendar day. Talk to me if you have a valid excuse for submitting your work late and the penalty might be waived.

The project The project will involve several stages involving a proposal, an intermediate submission, and a final submission. The stages before the final submission will not be graded, but not turning them in will cost you project points. The project will involve some coding (and hopefully some thinking!) -- other assignments will be (mostly) theoretical.

I will add stuff here about how we went about things as we cover the topics to jog your memory when you want to go back and study this stuff for the exams:

Warmin up to mathematical and algorithmic background. What is an algorithm, analyzing algorithms.

Growth of functions, asymptotic complexity. Big Oh, Theta, Omega. Little oh, omega.

A brief review of sorting/searching. Worst and average case complexity, deterministic vs randomized. Proof of lower bound on comparison sorting.

Recurrences, Master Theorem. Where do recurrences come from? How do we solve them using a recursion tree? Master theorem.

Greedy algorithms. Optimal substructure. Activity selection, Huffman tree, quick look at MST.

Dynamic programming. Relationship to recursive algorithms. Rod-cutting, matrix chain multiplication.

Graph algorithms: Prim's MST, Dijkstra's shortest paths, max flow.

NP-Completeness. Big one. What is it? Why does it matter? How do we prove a problem is NP-complete?

Advanced topics as time permits: Randomized algorithms, approximation algorithms.

Homeworks, etc.

All homeworks are due in class. You can write by hand, type using a tool such as latex (or word if you're brave :-) You are allowed to consult the book and/or your notes, but please don't work in groups or look in another book, or consult the Internet... If you have any questions, please email me or ask in class.

Resources: Here you find various resources for this course. I will add to these as I find new ones; you can email me any suggestions.

Puzzles: This is where you can find our puzzles. Don't be just a consumer; send me any puzzles you might have.