CS 522 - Algorithms 2

[ Announcements ] [ Academic Honesty ] [ General Information ] [ Lecture Notes ] [ Assignments ]

General Information

The course web page is http://karma.cs.drexel.edu/wiki/CS522/CS522. The course is in University Crossings 153 every Tuesday from 6:00-8:50pm.

Contact:

The professor for the campus section of this course is Ali Shokoufandeh, University Crossings, Room 141, phone 215-895-2671, ashokouf@cs.drexel.edu. Office hours are Thursdays from 5 - 6 p.m.

The TA for the course is Kamelia Aryafar, kca26@drexel.edu. Office hours are Tuesdays 4-6 P.M. in UC 147.

Objectives:

This course is intended as a broad study in design and analysis of algorithms for some of the most frequently encountered combinatorial problems.

Prerequisites:

You should already have some basic knowledge of algorithms, growth functions and asymptotic notation, recurrences, probabilistics analysis, sorting, median and order statistics, and elementary data structures at the level of Data Structures and Algorithms I course (CS 521)

Outline:

The course aims to provide familiarity with general algorithmic techniques, performance measures, analysis and problem areas. Specifically, we will cover the following topics:

  • All pairs shortest path and dynamic programming (1 lecture)
  • Disjoint union set systems (1 lecture)
  • Hash tables (1 lecture)
  • Splay trees (1 lecture)
  • Network flow (2 lectures)
  • NP-completeness and reduction among hard problems (3 lectures)
  • Approximation algorithms (1 lecture)
Expected Work

Biweekly Homework assignments (should be done independently), one midterm and final examination.

Grading:
  1. Homework: 30%
  2. Midterm: 30%
  3. Final exam: 40%
Text Book:

T.H. Cormen, C.E. Leiserson, and R.L. Rivest, C. Stein, Introduction to Algorithms, second edition.

Recommended References:
  1. Kozen, Design and Analysis of Algorithms. Springer Verlag, 1992.
  2. Tarjan, Data Structures and Network Algorithms. SIAM Series in Applied Mathematics 44, 1983.
  3. Papadimitriou and Steiglitz, Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982.