Computer Science 160
Algorithms
Fall 2009 Syllabus
http://www.cs.tufts.edu/comp/160
FIRST EXAM: 10/20/2009
SECOND EXAM: 11/24/2009
FINAL EXAM: Tuesday, December 15th 12:00 - 2:00 pm.
Handouts:
Announcements, assignments, and handouts will be posted on the class web
pages http://www.cs.tufts.edu/comp/160/documents . Please check frequently.
Brief Description:
Introduction to the study of algorithms. Strategies such as divide-and-conquer, greedy methods and dynamic programming. Graph algorithms, sorting, searching, hashing, integer arithmetic, and NP-complete problems.
Prerequisites:
Prior completion of COMP 15 (Data Structures and
Algorithms) and MATH 22 (Discrete Mathematics) OR the
EXPLICIT permission of the instructor.
Class Meetings in Halligan 111A:
Lectures: Tuesdays and Thursdays, 10:30 - 11:45 AM
Problem Sessions: Mondays, 9:30 - 10:20 AM [Optional, but highly recommended]
Mail sent to ta160@ is sent to all of the instructional staff, including
Professor Souvaine. Please
try to make e-mails about homework questions concise. If a message
takes more than one screen, then you should come to office hours or
make an appointment to talk with someone in person or raise the issue in
a problem session, instead of sending an email.
.
Office: Halligan 102A
Problem Sessions: Mondays, 9:30-10:20 in classroom.
Office Hours: Mondays, 2:30 - 3:30 PM and by appointment. Please email dls and cc csadmin.
.
Office: Halligan 107
Office Hours: Tuesdays 3:00 - 4:30pm, Wednesdays 12:00 - 1:30pm in Lab 118
Textbooks:
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein,
Introduction to Algorithms (second edition)
MIT Press, Cambridge, MA & McGraw Hill, New York, NY, 2001. [REQUIRED]
S. Baase and A. Van Gelder,
Computer Algorithms, 3rd edition,
Addison-Wesley, Reading, MA, 2000. [RECOMMENDED]
Expected Work:
Students are expected to attend class regularly and to complete regular
reading assignments in CLR. Students are responsible for all material
covered in class as will as all material covered in the assigned
reading, whether or not the material is also covered in class.
Graded course work will include regular homework sets, frequent quizzes,
two in-class examinations, one final examination, and one programming assignment.
Homework will be collected at the BEGINNING of the lecture
on the specified due date and will NOT be
accepted thereafter. Individual completion and submission of the homework
with full attribution of sources is a prerequisite for passing this
course.
NOTE: Groups of people may work together at the outset, discussing
and strategizing how to solve problems, and various other sources may be consulted,
subject to the following conditions:
EACH person must write up and submit his/her solutions in his/her OWN words;
every person and/or text and/or web site consulted in the process of completing the assignment must be accurately cited on the homework paper submitted.
Spontaneous short quizzes will be given during the class period roughly
once per week. At the end of the semester, the two lowest quiz grades
will be thrown out, to cover for unavoidable absence from class. There
will be no makeup quizzes. The two in-class exams and the one final
exam will include questions similar to those included on homework
assignments and will draw on material covered in lecture and/or in the
reading.
No collaboration is allowed on quizzes or examinations.
Toward the end of the semester, each student will pick a problem/algorithm
of interest to implement and test.
Outline and Reading List :
1. Basic Concepts of Algorithm Design and Analysis
Background Reading: Chapters 1-4, C.1 & C.2
Application Reading: Chapters 6-9, 32.1 & 32.4
Technique Reading: Chapters 15, 16.1 & 16.2, 17
- Main Concepts:
Models of Computation: RAM, Turing machine
Asymptotic Complexity: worst/average case, amortized, upper/lower bounds
Use of Recurrence Relations
- Example Areas for Complexity Analysis:
Sorting: worst case and average case
Selection: upper/lower bounds, average case
String matching: amortized analysis
- Algorithmic Design Techniques:
dynamic programming, divide and conquer, branch and bound, backtracking, greedy algor
ithms
2. Basic Data Types and Corresponding Data Structures
Essential Reading: Chapters 10-14
Advanced Reading: Portions of Chapters 18-21
- Searching:
Trees: optimal static (Knuth's principle), dynamic (red-black trees, B-trees)
Hashing: collision resolution, complexity
- Disjoint Set Union: applications, complexity
- Priority Queues (in the context of shortest paths and minimum spanning trees--see below)
Binary and K-ary Heaps
Fibonnaci Heaps
3. Graph Algorithms
Background reading: Chapter B
Application reading: Chapters 22-25
- Depth-First and Breadth-First Search
- Biconnected and Strongly Connected Components
- Topological Sort
- Shortest Path Trees and Minimum Spanning Trees (see above)
4. Coda on Algorithmic Complexity: Tractable and Intractable Problems
Reading: Chapters 34-35. Chapter 33.3.
- Definitions of P and NP
- Reductions as a way of establishing upper and lower bounds
- Upper and lower bounds for computing the convex hull
- NP-completeness
- Exact algorithms versus approximation algorithms