Intoduction to Algorithms, by Cormen, Leiserson and Rivest.
Data Structures and Algorithms, by Aho, Hopcroft and Ullman.
The course follows both books. Recommended purchase - first book (to be used by other courses).

Course syllabus:

The course will deal with data strucutres and their use in the design of efficient algorithms.
Subjects: Growth of functions and asymptotic notation; amortized analysis; recurrences: the substitution, master, and iteration methods; elementary strucutres: lists, stacks, queues; trees: ordered trees, binary trees, labeled trees and expression trees; set representation and manipulation; dictionary and hash tables; Perfect Hash. Search trees (Binary trees). Priority Queue (Heap). Union-Find DS. Balanced trees: 2-3 tree, B-Tree, AVL, Red-Black., Splay. Sorting and order statistics. Advanced topics if time permits (e.g. Blum Filter, Minimum-subject-to-constraint tree)

Tentative course outline. The actual order of the classes differs from this outline. The actual material may vary as well.

• Class 1 :
  Introduction
  Recursion (review)
• Class 2 :
  Complexity
  Master Theorem
• Class 3 :
  Elementary Structures: Lists, Stacks, Queues.
  Doubling and amortized complexity.
• Class 4 :
  Trees: basic concepts. Ordered tress, labeled trees, expression trees. Binary trees and Huffman Coding.
• Class 5 :
  Dictionary and Hashing. Open and Closesd Hash. Expected value complexity analysis. Hash functions. Rehashing. Reorganization. Universal Hashing.
• Class 6:
  Hash (continue): Perfect Hash.
• Class 7:
  Multilist, sparse matrices, multiple-representation of data, Priority Queue (Heaps).
• Class 8:
  Binary search trees
• Class 9 :
  Red-Black Trees.
• Class 10 :
  2-3 trees, B-trees, Merge-find trees
• Class 11 :
  Merge-find trees (cont.). Near Constant Complexity. Sorting: Simple sort, Quick Sort (algorithm, worst-case and average complexity).
• Class 12 :
  Sorting: Heap Sort and use for partial sort, bin sort. Order Statistics.

For a list of actual material covered so far click here
Copies of slides to be shown at during the semester:
File1 ,File1-0607
File2 ,File2-0607
File3 ,File3-0607
File4 ,File4-0607
File5 , File5-0405,File5-0607
File4 (2nd part - probability-0607)
Perfect-Hash , Perfect-Hash-new ,Perfect-Hash-0607
File6 , File6-0405 , File6-0607
RedBlack_tree , RedBlack-tree-0405 ,>RedBlack-tree-0607
Splay-tree, Splay-tree--new
Bloom-filter ,Bloom-filter-0607
Minimium subject-to constraint

Tirgul, homeworks and project

Details will be given in the Tirgul Home Page.

Last updated February 19, 2007