CPS 130: Fall 2001

Introduction to the Design and Analysis of Algorithms

Current Homework :

Exams :

Schedule:

Note: The following lecture notes were prepared by Michael L. Littman. The supplemental notes were prepared by Steven Skiena. style='mso-row-margin-right:.82%'> style='mso-row-margin-right:.82%'>

Date

Topic

Reference

 

Tue Aug 28

Introduction to Algorithms (1) (postscript, pdf)

Ch. 1 & 2

 

Thu Aug 30

Asymptotic Growth (2) (postscript, pdf) (Supplementals: postscript, pdf)

Ch. 3 & 4

 

Tue Sep 4

Master Method (3) (postscript, pdf) (Supplementals: postscript, pdf) (Homework 1: postscript, pdf)

Ch. . 3 & 4

 

Thu Sep 6

Recurrence Review

-

 

Tue Sep 11

Sorting (4) (postscript, pdf) (Homework 2: postscript, pdf)

Ch. 2.2, 2.3, 7.1, 7.2, 8.1, 8.3

 

Thu Sep 13

Analysis of Quicksort (5) (postscript, pdf) (Supplementals: postscript, pdf)

Ch. C.1, C.2, C.3, 7.2, 7.3, 7.4

 

Tue Sep 18

Computing Statistics (6) (postscript,pdf) (Homework 3: postscript, pdf)

Ch. 9

 

Thu Sep 20

Heaps (7) (postscript, pdf)

Ch. 6

 

Tue Sep 25

Binary Search Trees (8) (postscript, pdf) (Homework 4: postscript, pdf) (Supplementals: postscript, pdf) (More supplementals!: postscript, pdf)

Ch. 12.1, 12.2, 12.3

 

Thu Sep 27

Pre-exam Review

 

 

Tue Oct 2

 Exam 1: Putting Things in Order

(recurrences and searching, sorting)

(Solutions: postscript, pdf) (Class statistics: jpg)

 

Thu Oct 4

Splay Trees (9) (postscript, pdf)

Ch. 17

 

Tue Oct 9

Hashing (10) (postscript, pdf)

Ch. 11

 

Thu Oct 11

Stable Marriage (11) (postscript, pdf) (Homework 5: postscript, pdf)

-handout

 

Tue Oct 16

Fall Break

examination of leaves

 

Thu Oct 18

Graph Algorithms (12) (postscript, pdf) (Homework 6: postscript, pdf) (Supplementals: postscript, pdf) (More supplementals!: postscript, pdf)

Ch. 22

 

Tue Oct 23

Bipartite Matching (13) (postscript, pdf)

Ch. 26.2, 26.3

 

Thu Oct 25

Minimum Spanning Trees (14) (postscript, pdf) (Supplementals: postscript, pdf)

Ch. 26.2, 23, 23.2, 21

 

Tue Oct 30

Shortest Paths (15) (postscript, pdf) (Supplementals: postscript, pdf)

Ch. 25.1 (1st Ed.), 24.3

 

Thu Nov 1

More on Shortest Paths (Homework 7: postscript, pdf)

 

 

Tue Nov 6

Pre-exam Review of Graph Algorithms

 

 

Thu Nov 8

 Exam 2: Graph Algorithms

(Class statistics: jpg)

 

Tue Nov 13

Matrix Algorithms (16) (postscript, pdf)

Ch. 28.1, 28.3, 28.5

 

Thu Nov15

String Matching (17) (postscript, pdf) (Homework 8: postscript, pdf)

Ch. 32.1, 34.5 (1st Ed), 32.3, 32.4

 

Tue Nov 20

Dynamic Programming: Segmentation (18) (postscript, pdf) (Supplementals: postscript, pdf) (More supplementals!: postscript, pdf)

Ch. 15.4

 

Thu Nov 22

Thanksgiving Recess

-

 

Tue Nov 27

Dynamic Programming: LCS (19) (postscript, pdf)

Ch. 15.4

 

Thu Nov 29

Complexity (20) (postscript, pdf)

Ch. 34.1, 34.2, 34.4, 35.3

 

Tue Dec 4

Traveling Salesperson (21) (postscript, pdf)

Ch. 34.5, 35.2

 

Thu Dec 6

Review of Course for Final Exam

-

 

Tue Dec ?

 Final Exam (9 am to noon)

(Class statistics: jpg)

 
John Reif