Syllabus/Schedule of topics

Barring a few topics, the course will follow specified sections from the textbook fairly closely, augmented with

• videos on topics/problems from the textbook, and
• online lecture material from MIT’s 6.006 Course (Fall 2011).

The foundations of this course rest on core topics from the Data Structures course (CS 213), and while we will review some of that material, you are expected - by the end of the first month - to be quite comfortable with basic counting arguments and proofs by induction; recursion and recursive definitions; asymptotic notation; and basic data structures like (linked) lists, arrays, and binary search trees (both standard and balanced).

The class will follow a flipped classroom model which will be described in detail in the first week. We will use the Sakai site for the course as a hub for organizing all class-related material including links to external sites, notes, email and discussion forums. In brief, you will read and watch videos/explanations before coming to class, and classtime will be spent going over and analyzing finer points, and of course, solving problems.

A tentative, week-by-week outline of topics follows (note that except for the first week of class, the chapters/sections from the textbook indicated below in parentheses are to be read *before class* that week):

1. Review of big-oh notation, recurrences, divide and conquer (2.2, 2.3, 3.2, 4.2 and 4.4; Appendix A; Appendix B; Apendix C.1)
2. Review of heaps (6) and binary search trees (12.1 - 12.3); AVL trees.
3. Review of probability basics (Appendix C.2 - C.3); Quicksort (7)
4. Randomized (linear-time) selection; Counting sort, radix sort, bucket sort. (8, 9.2)
5. Hash tables and perfect hashing (11)
6. BFS and DFS (Appendix B.4, 22);
7. Applications of BFS and DFS; Exam 1
8. Shortest path algorithms: Bellman Ford; Dijkstra (24.1-24.3, 24.5)
9. Dynamic programming (15.1 - 15.3)
10. Dynamic programming (15.4 - 15.5); All-pairs shortest paths (25)
11. String Matching (32.3 - 32.4); Greedy algorithms: MSTs (16.1 and 16.2; 23)
12. Network Flows (26.1 - 26.3)
13. NP-completeness and reducibility (34.1-34.3)
14. NP-complete problems (34.4-34.5); An approximation algorithm for vertex cover (35.1)

The final exam will be held at the scheduled time on December 18th from 2:45pm to 5:45pm (although the exam itself will only be 2.5 hours long, you may take up the rest of the scheduled time if you wish).