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