V22.0310-001

Honors Basic Algorithms, spring 2011

Alan Siegel
T, Th, 2-3:15, now in Room 1302   
        T,    9:30-10:45, stil in Room 102

The Tuesday sessions are for recitation, and attendence is a course requirement.
Office: 330WWH. Office Hours: T 3:15-4:15 and by appointment.

Section Leader: Vasileios Gkatzelis
Office Hour: by appointment and Wednesdays, 6-7PM.
Location: 715 Broadway 10th floor. This is a locked floor:
Use the phone by the door to call Vasilis at the last four digits of (212-99)8 3359
The number is posted at the door.
The recitations will be team taught by Gkatzelis and Siegel
Midterm: Tuesday, March 8 at 2:00.

This page describes the honors version of Basic Algorithms, which is a more demanding version of V22.0310-002. The lectures, assignments, recitations and tests are all part of the regular Basic Algorithms V22.0310-002. However, honors participants are required to complete a higher percentage of the weekly assignments, and to complete a course project as well.


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, students are expected to attend the Tuesday recitation sessions, where students will practice applying sophisticated concepts to solve challenging exercises.

COURSE TOPICS

Algorithmic Design Paradigms

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

The Analysis of Algorithmic Performance

Asymptotic Growth
Recurrence Equations
The Recursion Tree Solution Method
Probabilistic Analysis
Structural Analysis
Lower Bounds

Managing Data for Efficient Processing

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

Selected Representative Algorithms/problems

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

Required Text:

An Inside Guide to Algorithms: their application, adaptation, design and analysis, by A.R. Siegel and R.J. Cole, which is available at the Unique Copy Center, 252 Greene St. (between Waverley and 8th Street).

Schedule of Topics

Homework

Course Grading Policy