ITCS 6114/8114             Algorithms and Data Structures                

Course Description::
Introduction to techniques and structures used and useful in design of sophisticated software systems. Sorting, Selection, Trees & Graphs, Shortest Path, Binary Search Trees, AVL Trees, Red-Black Trees, Matrix Multiplication, Optimal Binary Search Trees, Strassen's Matrix Multiplication, Dynamic Programming, Polynomial Evaluation, FFT, String Matching, Hashing, Complexity, Problem Reduction Techniques.

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 130
Last Class: April 30

Lectures (in PPT format):

Introduction I
Introduction II
Sorting I
Sorting II
Selection and Search
Binary Search Tree
AVL Trees
Sample Problems
Red-Black Tree
Graphs I
Graphs II
Trees I
Trees II
Sample Problems
Matrix Multiplication
Optimal Binary Search Tree
Sample Midterm Problems
Floyd Shortest Path Algorithm
Strassen's Matrix Multiplication
Dynamic Programming I
Traveling Salesperson Problem
Polynomial Evaluation
FFT Example
String Matching I
String Matching II
Dynamic Programming II
Skip Lists and Hashing
Universal Hashing and Dynamic Order Statistics
Complexity I
Complexity -Sample Problems
Sample Problems for Final Exam


  • Midterm - 30 points, Final - 30 points, Project - 30 points, Participation - 10 points.
  • Grade A from 86 to 100 points, Grade B from 71 to 85 points, Grade C from 56 to 70.

Instructor:       Zbigniew W. Ras

Office: Location: Woodward Hall 430C
Telephone: 704-687-8574
Office Hours: Tuesday: 12:30am-1:30pm; 5:00-6:00pm

TA:       Ayman Hajja      

Office: Location: Woodward Hall 432 (KDD Lab.)
Telephone: 704-687-8546
Office Hours: Tuesday [11:30am-1:30pm; 5:00-6:00pm]