W: 12:30-1:45 in room 109

Attendance in the Wednesday recitations is required.

Alan Siegel

Office: 330WWH.

Office Hours: to be announced and by appointment.

A NEW EDITION is available from Unique Copy at 252 Greene Street, which is open every day but Sunday.

This course covers the design and analysis of combinatorial algorithms. The curriculum is concept-based and emphasizes the art of problem-solving. The course features weekly exercises designed to strengthen conceptual understanding and problem solving skills. 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. Although some mathematical sophistication would be helpful for this course, the necessary mathematics is contained within the curriculum.

Because of the emphasis on problem solving, everyone is required to attend the Wednesday recitation sessions, where students will practice applying sophisticated concepts to solve challenging exercises.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

Minimum Spanning Trees

Shortest Path Problems

- There will be approximately 11 written homework assignments that have, on average, about 12 exercises each. Perhaps one-third to one-half of these problems will be extremely challenging. That is, the necessary concepts will have already been taught, but a good deal of 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 half of the more difficult exercises, but they are expected to write down what ideas/methods they used, and where their solution method broke down.
- Students are also expected to compare their own answers with the solution handouts to see what concepts and techniques were overlooked. 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 effort. Incorrect and even fragmentary incorrect answers can receive full credit for the QoE grade, which will have a weighting that is comparable to the correctness grade for each assignment.

- 19% Midterm Exam
- 13% Overall homework performance grade
- 13% Overall QoE homework grade
- 47% Final Exam Date and time TBD
- 8% Classroom participation
- Due to the class size, these numbers are approximate, and subject to change. In addition, other grading instruments may be included in the course.