Algorithms
CSc 22000
Monday, Wednesday ,Thursday, 10:30am-12:10pm, room 6111
|
Syllabus
|
This is an approximate syllabus for our course.
|
Date
|
Subject
|
Reference
in the First Edition book
|
Reference
in the Second Edition book
|
|
Insertion sort, merge sort, bubble sort
|
Introduction (Chapter 1)
|
Introduction (Chapters 1,2)
|
|
|
Mathematical Foundations
|
Chapters 2,3,4,5
|
Chapters 3,4, Appendix: Mathematical Background A, B
|
|
|
June 16-17
|
Heaps, heapsort, priority queues
|
Chapter 7
|
Chapter 6
|
|
June 17
|
Quicksort, randomized version of Quicksort. Worst case complexity |
Chapter 8
|
Chapter 7
|
|
June 21
|
Lower bounds for sorting, the decision tree model |
Chapter 9
|
Chapter 8
|
|
June 21, 23
|
Counting, Radix and Bucket sorts |
Chapter 9
|
Chapter 8
|
|
June 23, 28
|
Binary search trees, balanced search trees |
Chapter 13
|
Chapter 12
|
|
June 28, July 1
|
Red-Black trees |
Chapter 14
|
Chapter 13
|
|
July 19, 21
|
Dynamic programming |
Chapter 16
|
Chapter 15
|
|
July 21, 22
|
Greedy algorithms |
Chapter 17
|
Chapter 16
|
|
July 1, 7
|
Representation of graphs, Breadth-first search, Depth-first search, topological sort, strongly connected components |
Chapter 23
|
Chapter 22
|
|
July 8
|
Minimum spanning trees |
Chapter 24
|
Chapter 23
|
|
July 12, 14
|
Single-source shortest paths |
Chapter 25
|
Chapter 24
|
|
July 14, 15
|
Flow networks, maximum flow |
Chapter 27
|
Chapter 26
|