Course Web page (this page) http://www.cs.tufts.edu/comp/160/

Instructor:
Roni Khardon
Email: roni@cs.tufts.edu
Office Hours: Monday 45
Location: Halligan 230.
Teaching Assistant:
Mona Yousofshahi
Email: Mona.Yousofshahi@tufts.edu
Office Hours: Tuesday 1011, Thursday 1112, Friday 23
Location: Halligan 121.
Class Times: Tuesday, Thursday, 1:302: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 (notdisjoint) topics will be explored, each for 12 weeks.
Activities, Coursework and Grading: The course grade is based on a number of assignments, quizzes and exams as follows:
Textbooks:
Assignments: The following table will include all reading assignments, homework assignments, information for quizzes, exams and projects in chronological order as the course progresses.
Type  What  Due Date 
Background Reading  Appendices A, B, and C.1C.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.34.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 13.  
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.12; 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 157 in textbook.  
Reading  Knapsack: is in 16.2 and is also discussed in section 6.4 of [KT] text.  
Reading  Chapter 25 (allpairs 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.111.4.  
Programming Project: Algorithms for Satisfiability  Mon 4/29  
Reading  Chapter 17 (amortized analysis): read 17.117.3.  
Reading  Chapter 21 (disjoint sets): read 21.121.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.13 for review.  
Reading  Chapter 18 (Btrees).  
Quiz 4: 4/23  Covers all material since the last quiz (chapters 11,17,21,19,12,18)  
Reading  Chapter 34 (NPCompleteness).
Copies of lecture slides 

Exam on Friday, 5/3, 3:305:30 in H111A  Includes all the material covered in the course. More detailed information for the exam is given on a separate page. 