ITCS 2215             Design and Analysis of Algorithms                
Fall 2007

Prerequisites and Course Description::
ITCS 2214, MATH 1165, and either MATH 1120 or 1241.  Introduction to the design and analysis of algorithms.  Design techniques: divide-and-conquer, greedy approach, dynamic programming.  Algorithm analysis: asymptotic notation, recurrence relation, time space complexity and tradeoffs.  Study of sorting, searching, hashing, and graph algorithms.

Suggested Textbooks:
[1] Introduction to Design & Analysis of Algorithms, by Anany Levitin
[2] Introduction to Algorithms, by Cormen, Leiserson, Rivest, Stein

Class Meetings::
Tuesday [6:30-9:15PM], Woodward Hall 135

Lectures (in PPT format):

Introduction I
Introduction II
Sorting I
Sorting II
Sample Problems for Test I
Selection and Search
Binary Search Tree
Red-Black Tree
Graphs I
Graphs II
Trees I
Trees II
Sample Problems for Test II
Dynamic Programming I
Dynamic Programming II
Matrix Multiplication
Optimal Binary Search Tree
Floyd Shortest Path Algorithm
Skip Lists and Hashing
Universal Hashing and Dynamic Order Statistics
Sample Problems for Final Exam

  • Exam I: September 18 (Tuesday), 2007 (in Woodward Hall 135)
  • Exam II: November 6 (Tuesday), 2007 (in Woodward Hall 135)
  • Project - deadline to submit: December 4, 2007
  • Final: December 11, 2007 (Tuesday), (in Woodward Hall 135)


  • Exams - 20 points each, Final - 30 points, Project - 30 points (maximum)
  • Grade A from 86 to 100 points, Grade B from 71 to 85 points, Grade C from 56 to 70, Grade D from 41 to 55 points.

  • Sample Problems

    Class meetings:

                Location: Woodward Hall 135
                Time: Tuesday, 6:30-9:15pm

    Instructor:       Zbigniew W. Ras

    Office: Location: Woodward Hall 430C
    Telephone: 704-687-8574
    Office Hours: Tuesday, Thursday: 4:30-6:00pm

    TA: Venxin Jiang      

    Office: Location: Woodward Hall 432 (KDD Lab.)
    Telephone: 704-687-8546
    Office Hours: Tuesday, Thursday [3:00-4:30pm]