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.
Topics to be covered in the exam -- given as sections from CLRS: 1 to 4 (skip maximum subarray, Strassen, proof of master theorem). You should know 6. We did 7 except for 7.3, we did the sorting lower bound in 8.1, we did 9.3. You should already know 10. We did 15.1, 15.2 (didn't quite finish 15.2). Did 16.1, 16.2, 16.3. You should know 22, we did 23.1 and Prim's from 23.2.
Location: BH 242 TR 9:30 -- 10:45.
Instructor: Funda Ergun. Office: LH 428C. Email: fergun@indiana.edu.
Instructor office hours: T 11:00 -- 12:00 or by appointment.
AI: Erfan Sadeqi Azer. Office hours TBA. Email: esadeqia@indiana.edu
Textbook: Introduction to Algorithms. T. Cormen, C. Leiserson, R. Rivest, C. Stein.
Funda. No, we didn't do this in my home country either, but I got used to it and so can you. What not to call me: Ma'am, anything that starts with Miss, Ms., Mrs. -- tolerable (for a little while) is stuff that starts with "Professor" if you really must.
This course studies algorithms: what they do, how to construct them, how to analyze them for correctness and efficiency. Every time you need to solve a problem, write a program, design a technique, you need to understand your problem, as well as how to solve it. Once you (think that you) have a solution, you need to be able to show without a doubt that it solves a problem, and solves it well. In this class we cover more of how to do all of this. We will look at general techniques for solving algorithmic problems, then learn how to design our own.
This is a crucial course for any computer scientist (as our MS and PhD requirements demonstrate), and is quite mathematical. You will not do much programming here, except for a relatively small project. 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.
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 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 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:
What is an algorithm, analyzing algorithms.
Growth of functions, asymptotic complexity. Big Oh, Theta, Omega. Little oh, omega. We have discussed all of these.
A brief review of sorting/searching. Worst and average case complexity, deterministic vs randomized, lower bound. We have discussed some of these (mergesort, different versions/average/worst/best case of quicksort, binary search). We will finish sorting lower bound.
Recurrences, Master Theorem. We have discussed substitution, recursion tree, master theorem. We have seen deterministic selection (median find), and are analyzing its complexity. We have briefly discussed randomized selection.
Greedy algorithms. Optimal substructure. We discussed activity selection and proved that the greedy algorithm is optimal. We did Huffman and MST. We analyzed the running time of MST and showed what "safe" means and how to prove that a particular choice is safe.
Dynamic programming. Relationship to recursive algorithms. Examples. We did rod cutting and change making. We also did most of matrix chain multiplication.
Graph algorithms: Prim's MST, Dijkstra's shortest paths, max flow.
NP-Completeness. Big one. What is it? How do we do a reduction?
Advanced topics as time permits: Randomized algorithms, approximation algorithms.
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.
Homework 1, due September 17.
Homework 2, due October 9.
Homework 3, due November 12.
Homework 4, due December 8.
Project, due on the last day of class.