Ileana Streinu
MW 2:30-4:00
Burton 307

Algorithms, Fall 1996

CSC 252

Week 1: Sept. 9-Sept. 15 Week 6: Oct.14-Oct. 20 Week 11: Nov. 18-Nov. 24
Week 2: Sept. 16-Sept. 22 Week 7: Oct. 21-Oct. 27 Week 12: Nov. 25-Dec. 1
Week 3: Sept. 23-Sept. 29 Week 8: Oct. 28-Nov. 3 Week 13: Dec. 2-Dec. 8
Week 4: Sept. 30-Oct. 6 Week 9: Nov. 4-Nov. 10 Week 14: Dec. 9-Dec. 15
Week 5: Oct. 7-Oct. 13 Week 10: Nov. 11-Nov. 17 Final Exam

Schedule subject to change. The lectures will follow the textbook closely. The readings are from the textbook. The projects will be announced later in the semester.

Week 1: Introduction, Chapter 1

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Sep 9
1
Introduction




-


1.1, 1.2, 1.3
Wed. Sep 11
2


Order of magnitude
Hw1

From textbook, page 42
Drills: 1-5
Required: 6, 11, 12, 13, 14, 25, 26, 28
Extra-credit: 27, 33, 34


-


1.4

Week 2: Divide and conquer

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Sep 16
3
Merge Sort, Quick Sort, Recurrence Relations








2.1-2.4
Wed. Sep 18
4
Matrix multiplication






Hw1



2.5,

2.7, 2.8



Week 3: Dynamic programming, Chapter 3

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Sep 23
5
Shortest paths






3.1, 3.2
Wed. Sep 25
6
optimization problems
3.3, 3.5


Week 4: Greedy, Chapter 4

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Sep 30
7
minimum spanning tree




4.1

Wed. Oct 2
8
scheduling



4.3



Week 5

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Oct 7
9
Knapsack problem





4.4
Wed. Oct 9
10
Backtracking


5.1, 5.2, 5.3



Week 6: Backtracking, Chapter 5

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Oct 14
no class (mid-semester break)
X
X
X
X
Wed. Oct 16
11
Graph coloring, Hamiltonian circuit


5.5, 5.6


Week 7: Midterm Exam

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Oct 21
12
TBA



projects assigned
Wed. Oct 23
13
midterm exam


Week 8: Lower bounds sorting, Chapter 7

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Oct 28
14
lower bounds for sorting





7.1-7.5, 7.7, 7.8
Wed. Oct 30
15
Heapsort




7.6


Week 9: Lower bounds for searching and selection, Chapter 8

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Nov 4
16
searching





8.1-8.4
Wed. Nov 6
17
selection



8.5


Week 10: Topic to be announced

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Nov 11
18
TBA







Wed. Nov 13
19
TBA




Week 11: NP-completeness, Chapter 9

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Nov 18
20
NP-hard, NP-complete problems, TSP




9.1-9.4
Wed. Nov 20
21
approximation algorithms for TSP & bin packing
9.5


Week 12

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Nov 25
22
discussion of projects






Wed. Nov 27
no classes (Thanksgiving)
X
X
X
X


Week 13: Parallel algorithms, Chapter 10

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Dec 2
23
parallel architectures




10.1
Wed. Dec 4
24
PRAM model


10.2


Week 14: Project week: class presentations

Date
Lecture #
Contents
Work Assigned
Homework Due
Reading
Mon. Dec 9
25







Wed. Dec 11
26


Final Exam: self-scheduled, exam period December 16-19

Page updated September 1, 1996