Course Web page (this page) http://www.cs.tufts.edu/comp/160/
Office Hours: Monday 4-5 Location: Halligan 230.
Office Hours: Tuesday 10-11, Thursday 11-12, Friday 2-3 Location: Halligan 121.
Class Times: Tuesday, Thursday, 1:30-2:45 Halligan Hall 111A.
Brief Syllabus: The course develops basic theoretical foundations of algorithm design and analysis. We will study various methods for designing efficient algorithms and data structures that support them. We will prove correctness of algorithms and analyze their run time. The following (not-disjoint) topics will be explored, each for 1-2 weeks.
Activities, Coursework and Grading: The course grade is based on a number of assignments, quizzes and exams as follows:
Assignments: The following table will include all reading assignments, homework assignments, information for quizzes, exams and projects in chronological order as the course progresses.
|Background Reading||Appendices A, B, and C.1-C.3 as well as Chapter 3 (Asymptotic notation). I recommend doing some end of section exercises to make sure your review is effective.||Week 1|
|Reading||Chapters 1 and 2 (Introduction).||Week 1|
|Reading||Integer Multiplication: is from section 5.5 of [KT], and section 2.1 of [DPV].||Week 2|
|Reading||Chapter 4: 4.1,4.3-4.5.||Week 2|
|Homework Assignment 1||Tue 1/29|
|Quiz 1: 1/31||material includes all the reading above|| |
|Reading||Chapter 5 (probabilistic analysis) sections 1-3.|| |
|Reading||Chapter 7 (quicksort).|| |
|Homework Assignment 2||Tue 2/12|
|Reading||Chapter 8 (Linear time sorting).|| |
|Reading||Chapter 9 (medians and selection).|| |
|Reading||Chapter 6 (heaps and heapsort).|| |
|Quiz 2: 2/14||material includes all the topics from chapters 5,6,7,8,9 that were discussed in class.|| |
|Homework Assignment 3||Tue 2/26|
|Reading||Chapter 24 : introduction and 24.3 (Dijkstra's algorithm)|| |
|Reading||Chapter 16 (greedy algorithms) 16.3.(Optionally consult 16.1-2; they will be clearer after we discuss Dynamic programming.)|| |
|Reading||Chapter 23 (minimum spanning trees).|| |
|Reading||Set Cover: is discussed in section 35.3 of our textbook But we give a simpler result and analysis in class similar to section 5.4 of [DPV].|| |
|Reading||Clustering: is from section 4.7 of [KT] text.|| |
|Homework Assignment 4||Tue 3/12|
|Midterm exam 3/7 in class||Material includes everything (material from class and from reading) from the beginning of the semester to this point in the schedule. More detailed information for the exam is given on a separate page.|| |
|Reading||Chapter 15 (dynamic programming); you may skip 15.5.|| |
|Note||Material on Hidden Markov Models from class solves problem 15-7 in textbook.|| |
|Reading||Knapsack: is in 16.2 and is also discussed in section 6.4 of [KT] text.|| |
|Reading||Chapter 25 (all-pairs shortest paths): read 25.1 and 25.2.|| |
|Homework Assignment 5||Thu 4/4|
|Quiz 3: 3/28||includes the all material on dynamic programming from reading and from class (but excluding the last 1/2 lecture that discussed Markov Decision Processes.)|| |
|Reading||Chapter 11 (hashing): read 11.1-11.4.|| |
|Programming Project: Algorithms for Satisfiability||Mon 4/29|
|Reading||Chapter 17 (amortized analysis): read 17.1-17.3.|| |
|Reading||Chapter 21 (disjoint sets): read 21.1-21.3.|| |
|Reading||Chapter 17 (amortized analysis cont.): read 17.4.|| |
|Reading|| Chapter 19 (Fibonaci Heaps).
Copies of lecture slides (which were adapted from these lecture slides at Princeton.)
|Homework Assignment 6||Thu 4/18|
|Reading||Chapter 12 (binary search trees): read 12.1-3 for review.|| |
|Reading||Chapter 18 (B-trees).|| |
|Quiz 4: 4/23||Covers all material since the last quiz (chapters 11,17,21,19,12,18)|| |
|Reading|| Chapter 34 (NP-Completeness).
Copies of lecture slides
|Exam on Friday, 5/3, 3:30-5:30 in H-111A|| Includes all the material covered in the course.
More detailed information for the exam is given on a separate page.