Basic Algorithms, fall 2013

Alan Siegel
M 3:30-4:45, T, Th: 2-3:15 in room 109   
Attendance in the Monday recitations is required.
Office: 330WWH. Office Hours: T, Th 3:15-4:15 and by appointment.

Final: Dec. 17, Room 109, 2:00 - 3:50.

Required Text:

An Introduction to Algorithms: their methods and madness, by A.R. Siegel.
This will be a NEW EDITION, but it is not yet availble.

Chapter 1 of the textbook and the accompanying exercises will be disributed in class on Tuesday. The entire book will be available by the end of the week, and cost about $45.00 for more than 800 pages.

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


Algorithmic Design Paradigms

The Greedy Method
Dynamic Programming
Sorting- and Selection-based processing
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
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

Schedule of Topics


Course Grading Policy