16:198:513:01 Design And Analysis Of Data Structures And Algorithms I, Fall 2006

Announcement: 16:198:514 Spring 2007

Final Exam: same room: HLL-120, same time: 3:20pm.

Time: T-Th 3:20-4:40 pm
Place: HLL-120
Instructor:
Endre Szemerédi
Office : HLL-492
Office Hours: Tuesday 9:20am-10:20am & 5pm-6pm
TA:
Miguel Mosteiro
Office: HLL-414
Office Hours: Wednesday 10am-11am

TA 10/16 -> 11/30:
Devendra Desai
Office: HLL-203
Office Hours: Monday 1pm-3pm

Objectives: Core material for Computer Science degree candidates. Discussion of representative algorithms and data structures encountered in applications.

Prerequisites: Admission requirements; familiarity with the Prim and Kruskal minimum spanning tree algorithms and with the Dijkstra shortest path algorithm. Knowledge of basic concepts of programming and data structures is assumed (e.g. lists, stacks, queues, trees) as well as basic mathematics (e.g. proof by induction, permutations, logarithms, the basics of solving recurances, and asymptotic (i.e. "big-oh", "big-omega") notation). A general background in undergraduate algorithms: sorting upper and comparison model lower bounds, MST algorithms, shortest paths, etc.

Outline: Basic Concepts of Algorithm Design and Analysis. Worst-case, average case, and amortized analysis. Data structures: search trees; hash tables; heaps; Fibonacci heaps; union-find programs. Algorithms: string matching; sorting and order statistics; graph algorithms. NP-completeness. Fundamental techniques for designing efficient combinatorial algorithms and mathematical methods for analyzing their complexity.

Expected Work: The course is primarily a lecture course with 6-7 homework assignments. There is a midterm and final examination.

Text: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 2nd Ed., MIT Press, 2001 (CLRS2).

References:
Jon Kleinberg and Éva Tardos, Algorithm Design, Addison-Wesley, 2006.
Tarjan, R.E., Data Structures and Network Algorithms, SIAM, 1984.
Baase, S., Computer Algorithms: Introduction to Design and Analysis, Addison-Weslay, 1978.

Tentative list of topics: All chapter numbers are listed for the CLRS2 book (The list of topics may vary according to level of student algorithmic and graph-theoretic background). All these chapters are present in the first edition of the book as well, but chapter numbers and problem numbers will not be provided for this.
Grading Policy: There will be one midterm and a final exam. The midterm is worth 30% of the final grade. The final will weigh 40% of the final grade. All tests are cumulative. Weekly homework assignments will constitute the remaining 30% of the final grade.

The homework assignments are mathematically oriented and involve derivations of mathematical equations, proofs of combinatorial theorems and running time analysis of combinatorial algorithms. Homework is to be done independently. Students are encouraged to discuss general course material with their classmates, the TA or the instructor, but specific homework problems may not be written collaboratively. NO LATE HOMEWORK WILL BE ACCEPTED.

Homeworks: A '*' indicates that a problem is difficult.

16:198:514 Design And Analysis Of Data Structures And Algorithms II
Spring 2007

Schedule for the first 6 weeks: Most probably the students will have to present a paper at the end of the semester.

The first class will be on January 25.