4005-800-70 Theory of Computer Algorithms
Course Schedule and Topics

Tuesday, Thursday, 6:00pm-7:50pm -- Room 70-2590

Sun	Mon	Tue	Wed	Thu	Fri	Sat
Nov. 30	Dec. 1	Dec. 2 Introduction	Dec. 3	Dec. 4 Module 1. Fundamental Concepts	Dec. 5	Dec. 6
Dec. 7	Dec. 8	Dec. 9 Module 2. Algorithm Analysis, Part 1 Module 2 Homework due (6:00pm)	Dec. 10	Dec. 11 Module 2. Algorithm Analysis, Part 1	Dec. 12	Dec. 13
Dec. 14	Dec. 15	Dec. 16 Module 3. Sorting, Part 1 Module 3 Homework due (6:00pm)	Dec. 17	Dec. 18 Module 3. Sorting, Part 1	Dec. 19	Dec. 20
Dec. 21 Break	Dec. 22 Break	Dec. 23 Break	Dec. 24 Break	Dec. 25 Break	Dec. 26 Break	Dec. 27 Break
Dec. 28 Break	Dec. 29 Break	Dec. 30 Break	Dec. 31 Break	Jan. 1 Break	Jan. 2 Break	Jan. 3 Break
Jan. 4	Jan. 5	Jan. 6 Module 4. Sorting, Part 2 Module 4 Homework due (6:00pm)	Jan. 7	Jan. 8 Module 4. Sorting, Part 2	Jan. 9	Jan. 10
Jan. 11	Jan. 12	Jan. 13 Module 5. Searching Module 5 Homework due (6:00pm)	Jan. 14	Jan. 15 Midterm Exam (one hour) Project assigned	Jan. 16	Jan. 17
Jan. 18	Jan. 19	Jan. 20 Module 6. Algorithm Analysis, Part 2 Module 6 Homework due (6:00pm)	Jan. 21	Jan. 22 Module 6. Algorithm Analysis, Part 2	Jan. 23 Last Day to W	Jan. 24
Jan. 25	Jan. 26	Jan. 27 Module 7. Graph Algorithms, Part 1 Module 7 Homework due (6:00pm)	Jan. 28	Jan. 29 Module 7. Graph Algorithms, Part 1	Jan. 30	Jan. 31
Feb. 1	Feb. 2	Feb. 3 Module 8. Graph Algorithms, Part 2 Module 8 Homework due (6:00pm)	Feb. 4	Feb. 5 Module 8. Graph Algorithms, Part 2	Feb. 6	Feb. 7
Feb. 8	Feb. 9	Feb. 10 Module 9. Hard Problems Module 9 Homework due (6:00pm)	Feb. 11	Feb. 12 Module 9. Hard Problems Project due (11:59 pm)	Feb. 13	Feb. 14
Feb. 15	Feb. 16	Feb. 17 Module 10. Selected Topics	Feb. 18	Feb. 19 Module 10. Selected Topics	Feb. 20	Feb. 21
Feb. 22	Feb. 23 Finals	Feb. 24 Final Exam 6:00pm-8:00pm, Room 70-2590	Feb. 25 Finals	Feb. 26 Finals	Feb. 27 Finals	Feb. 28

Introduction

Topics Course introduction Course policies

Reading Course Description and Objectives Course Grading and Policies

Module 1. Fundamental Concepts

Topics Alternative algorithms: Insertion sort, merge sort Algorithm characteristics: Storage, run time Theoretical prediction of algorithm characteristics Experimental measurement of algorithm characteristics

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 1 Cormen, Leiserson, Rivest, & Stein, Chapter 2

Module 2. Algorithm Analysis, Part 1

Topics Asymptotic notation Recurrences Probabilistic analysis Randomized algorithms

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 3 Cormen, Leiserson, Rivest, & Stein, Chapter 4 Cormen, Leiserson, Rivest, & Stein, Chapter 5

Module 3. Sorting, Part 1

Topics Heaps Heapsort Priority queues Quicksort

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 6 Cormen, Leiserson, Rivest, & Stein, Chapter 7

Module 4. Sorting, Part 2

Topics Linear-time sorting Selection Medians Order statistics

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 8 Cormen, Leiserson, Rivest, & Stein, Chapter 9

Module 5. Searching

Topics Hash tables, hash functions Perfect hashing Binary search trees Binary searching of sorted arrays

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 11 Cormen, Leiserson, Rivest, & Stein, Chapter 12 Jon Bentley, "Programming Pearls: Writing Correct Programs" [PDF, 648,550 bytes]

Module 6. Algorithm Analysis, Part 2

Topics Dynamic programming Greedy algorithms Amortized analysis

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 15 Cormen, Leiserson, Rivest, & Stein, Chapter 16 Cormen, Leiserson, Rivest, & Stein, Chapter 17

Module 7. Graph Algorithms, Part 1

Topics Breadth-first search Depth-first search Topological sort Strongly connected components Minimum spanning trees

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 22 Cormen, Leiserson, Rivest, & Stein, Chapter 23

Module 8. Graph Algorithms, Part 2

Topics Single-source shortest paths algorithms All-pairs shortest paths algorithms Maximum flow algorithms

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 24 Cormen, Leiserson, Rivest, & Stein, Chapter 25 Cormen, Leiserson, Rivest, & Stein, Chapter 26

Module 9. Hard Problems

Topics Complexity classes: P, NP NP-complete problems Examples of NP-complete problems Approximation algorithms

Reading Cormen, Leiserson, Rivest, & Stein, Chapter 34 Cormen, Leiserson, Rivest, & Stein, Chapter 35

Module 10. Selected Topics

Topics The class will select the topics to be covered

Reading TBD

Theory of Computer Algorithms 4005-800-70 Winter Quarter 2003

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2004 Alan Kaminsky. All rights reserved. Last updated 13-Jan-2004. Please send comments to ark­@­cs.rit.edu.