Lecture: T 5:10-7:00, Room 109
Recitation: Th 5:10-6:00, Room 109
Office Hours: T 2-3, Th 6-7 and by appointment
This course covers the design and analysis of
combinatorial algorithms. The curriculum is concept-based and emphasizes the
art of problem-solving. The class features
weekly exercises designed to strengthen conceptual understanding and problem
Attendence in the recitation sessions is MANDATORY. In a few
recitations, sophisticated problems will be solved by
the class in closely supervised individual, collaborative, and group efforts.
However, MOST of these sessions will be used to present additional course content.
Prerequisites: Although some mathematical
sophistication is very helpful for this course, the necessary mathematics is
contained within the curriculum.
However, students are presumed to have adequate programming skills and
to have a solid understanding of basic data structures and their implementation
in the programming languages of their choice.
For example, students should be able to insert a record as a new leaf in a binary search tree. For those with no prior programming experience, a B or better in PAC II is expected. Anyone who lacks this background is expected to secure the written permission of the course instructor or the Director of the MS program.
Required Text: An Introduction to Algorithms: their Methods and ssendaM
A NEW edition of the coursee text IS available at Unique Copy Center.
252 Greene St. (1/2 block below 8th St). Hours: M-F 8-9, Sat. 10-4.
Algorithmic Design Paradigms
The Greedy Method
Sorting- and Selection-based processing
Algorithm Redesign and Adaptation
The Analysis of Algorithmic Performance
The Recursion Tree Solution Method
Managing Data for Efficient Processing
Lists, Stacks, Queues, Priority Queues, Trees and
Tarjan's Categorization of Data
Search Trees and their Enhancement
Sorting, Selection, and Hashing
Selected Representative Algorithms/problems
It will change as the lectures and organization are adapted to
fit the evolving time constraints.
Biconnected Components and Strong Components
Representative styles of Dynamic Programming and their applications
Standard Sorting and Selection Algorithms
Selected topics in Hashing
Shortest Path Problems
Minimum Spanning Trees
There will be approximately 11 written homework assignments
that contain 10 to 15 multi-part exercises. Perhaps one-third
to one-half of these problems will be extremely challenging. That is,
the necessary concepts will have already been taught, but significant
thought will be needed to figure out how to apply these techniques
to solve the more challenging exercises.
- Students are not required to solve even the majority of the difficult
but they are expected to write down what ideas/methods they used, and where
their solution method seems to have broken down.
- Students are also expected to compare their own answers with the
solution handouts to identify the concepts and techniques were overlooked.
In particular, students are required to keep a copy of every homework assignment, and submit a self-grading of that copy in the first class that follows the due date for the assignment.
- Because more than a third
of the course is embedded in the exercises, students are expected to study the
answers as a vehicle for mastering the material.
- Homework will receive two grades: overall performance, and Quality of
the self-grading Effort (QoE). Incorrect and even fragmentary incorrect answers can receive full
credit for the QoE self-grading.
Course Grading Policy
20% Midterm Exam
10% Overall homework performance grade
20% Overall QoE homework grade
44% Final Exam
6% Classroom participation
The homework and exam grading policy allocates significantly more credit for
incorrect and partial solutions that include an explanation about what is
wrong than for comparable answers that lack any such comments.
These policies are subject to change due to growth in enrollment, and other
class characteristics that change from year to year.