Computer Science 160: Algorithms
Department of Computer Science
Tufts University
Spring 2013

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

Announcement(s):
  • (5/9) Projects have been graded and can be collected in the CS main office (please ask staff for it).
  • (5/8) Exams have been graded and are available in the CS main office (please ask staff to see the exam).
  • (5/2) Extra office hours today (Thursday): Khardon will hold office hours during 1-2pm.
  • (5/2) Quiz 4 has been graded and can be collected from the CS main office. (There is one paper without a name. If you do not find your paper please come to see Prof. Khardon.)
  • (4/29) Detailed information for the final exam posted.

Instructor: Roni Khardon
Email: roni@cs.tufts.edu
Office Hours: Monday 4-5 Location: Halligan 230.

Teaching Assistant: Mona Yousofshahi
Email: Mona.Yousofshahi@tufts.edu
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:

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.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 pdf 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 pdf 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 pdf 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 pdf 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 pdf 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 pdf 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 pdf 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.