Fundamental Algorithms
Marc Millstone
Office: WWH 530
Office Hours: Monday, after class
- Location
- WWH 102
- Mondays, 6-7pm, Wednesdays 6-8:20pm
Note: class will meet on Monday 14 May, the first recitation session of the
of the term. There I will discuss the class policy and guidelines as
well as review a multitude of mathematical techniques that will prove
necessary throughout the course (ie. dont skip the first lecture).
- Topics
We will cover material as stated on the core exam syllabus plus
additional topics, time allowing. Core exam material includes:
- Analysis of the correctness and running time of Algorithms
- Basic data structures: arrays, stacks, queues, linked lists and binary trees
- Recurrence equations
- Sorting algorithms
- Selection, binary search
- Hashing
- Binary search trees and balanced trees
- Graph algorithms: spanning trees, shortest path, graph searching
- Algorithm design paradigms: Dynamic Programming, divide and conqueur, greedy algorithms
Additional Material may include:
- NP-completeness
- Decidability
- Requirements
- Attend class and recitations
- Do the assigned readings
- Do the homework
- Complete the quizzes (Approximately, there will be a short 10-15 minute
quiz given during the recitation section every other week).
- Complete a final exam. This will be cumulative.
- Join the mailing list by clicking
here
- Textbook
Most lectures will be based upon material covered in
Introduction to Algorithms, Second edition by Cormen, Leiserson, Rivest, and Stein.
- Homework
Homework 1: Due 23 May 2007
Homework 2: Due 4 June 2007
Homework 3: Due 11 June 2007
Homework 4: Due 20 June 2007
Now due 25 June 2007
Homework 5: Due 11 July 2007
Additional Problems
Homework Policy
You may work on the homework in pairs. Each student is responsible
for understanding all homework problems and for submitting his or her own
assignment and work (ie, working together does not allow copying solutions!).
Also, if you do choose to work in a pair, please write
your partners name on the top of your assignment.
IN total, there will be approximately 10 homeworks, due on each
Wednesday. Each student is allowed 3 extensions for use at any time
during the semester. If an extension is used, the assignment must be turned
in on the Monday following the original due date, no exceptions.