Course Schedule (tentative)

Week of

 Lecture

 Readings

Sept

5

  Intro: the Truth and nothing but - Notation, Proofs, and
    Unforgiving computers; Boolean circuits

Administrativia,
lecture slides,
Notation (past),
Ch.1, 2.1

 

12

Computational limits of physical realities and Exponential growth;
Counting: unary, binary, decimal, hex,...

ps0 due Sept. 12

 

 Monday, September 18, 2006: Last Day to ADD Classes

 

19

Data representation

 ps1 due Sept. 21 (see Dual)

 

26

Recursion and proofs by inductions

ps2 due Sept. 28
Read sec.2-3; also strongly recommended are updated notes: 1,2,3,4,5

 

 

 

 

Oct

3

Sorting

 ps3 due Oct.12

 

Friday, October 6, 2006: Last Day to DROP Classes (without a 'W' grade), or to Change from Credit to Audit Status
Tuesday, October 10, 2006: NO class (Monday schedule)

 

10

 Invariants and proofs of correctness

 

 

17

 Recurrences and complexity of recursive algorithms

 sec. 12 (see also here)

 

24

 Oct. 26: Midterm (pictures: 1, 2, 3, 4, 5, 6, 7, 8)

 sec. 10; ps4 due Oct. 24

 

 Friday, October 27, 2006: Last Day to DROP Classes (with a 'W' grade)

 

31

asymptotics: algorithms complexity

 11; ps5 Due Nov. 14

 

 

 

 

Nov

7

Counting: strings, substrings, arrangements, ...

 

 

14

Counting continued

14, 15, 16 (or the updated notes: 1, 2, 3, 4, 5, 6). ps6 Due Nov. 21

 

21

Graph definitions and algorithms

  6

 

 November 22-26, 2006: Thanksgiving Break

 

28

Scheduling and graph coloring, 2-coloring and spanning trees

 

 

 

 

 

Dec

5

ST algorithms: DFS, BFS, MST, SPT

 ps7 Due Dec.5

 

12

 Review

  ps8 Due Dec.12

 

 Classes end on Tuesday, December 12, 2006

 

16

 Final: Saturday, December 16, 2006
 3-5 pm