Office: 330 Phone: 998-3122

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 solving skills.

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.

252 Greene St. (1/2 block below 8th St). Hours: M-F 8-9, Sat. 10-4.

Recursion

Depth-First-Search

Breadth-First-Search

The Greedy Method

Divide-and-Conquer

Dynamic Programming

Sorting- and Selection-based processing

Randomization

Algorithm Redesign and Adaptation

Problem Transformations

Asymptotic Growth

Recurrence Equations

The Recursion Tree Solution Method

Probabilistic Analysis

Structural Analysis

Lower Bounds

Lists, Stacks, Queues, Priority Queues, Trees and
Graphs

Tarjan's Categorization of Data
Structures

Search Trees and their Enhancement

Union-Find

Sorting, Selection, and Hashing

Topological Sort

Connected Components

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 problems, 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.

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