Basic information:

• Instructor: David Liben-Nowell
• Lecture: 2a (MW 9:50-11:00a, F 9:40-10:40a), CMC 209.
• Office Hours: M 11:00a-12:00p, T 10:00a-12:00p, W 11:00a-12:00p 2:00-3:00p, CMC 320.
  Always feel free to stop by or email for an appointment.
  
  
• Catalogue description: A collection of topics useful in computer science topics: elements of logic and Boolean algebra; methods of proof; sets, relations, and functions; graphs, counting techniques; elementary complexity theory; and finite probability. Additional topics may be drawn from recurrence relations, finite-state machines, and linear algebra. Prerequisites: Mathematics 110 or 111; Computer Science 117 or concurrent registration in Computer Science 117.

Announcements:

• There is an anonymous feedback form available for any comments that you have about the course. If you have any suggestions or comments on the class (style, content, workload, etc.), please feel free to use this form to let me know.
  
  
• Problem Set #7 due on Wednesday, 16 November, in class. Clarification: on question 4, the set S has to be nonempty.
• I'd like to encourage you all to sign up for The Carleton Sentinel, an email-based CS newsletter, at lists.carleton.edu.

Lectures:

• 12 September 2005 (M): course logistics, propositional logic (MR §0.6 (ignore "justification below the proof level"), §7.1, §7.2.)
• 14 September 2005 (W): predicate logic, applications within CS (MR §0.6, §7.3, §7.6, Wikipedia natural language processing, SAT, and NP-Completeness)
• 16 September 2005 (F): proof techniques, the beginning of game trees (MR §0.6, Wikipedia Therac 25, Ariane 5 Flight 501, and the Pentium bug)

• 19 September 2005 (M): game trees concluded, basic math review (MR §0.1 (skip "relations"), §0.2, §0.4, §0.5, Question 0.4.17 (p. 50), Wikipedia Deep Blue)
• 21 September 2005 (W): basic math review concluded, error-correcting codes, repetition codes (MR §0.1 (functions), §0.5 (matrix multiplication))
• 23 September 2005 (F): Hamming codes. (Wikipedia: Hamming codes and Reed/Solomon codes)

• 26 September 2005 (M): review of algorithms, induction begun (MR Prologue §1.1 (skim), §1.3 (Towers of Hanoi pp. 99-100), §2.1, §2.2)
• 28 September 2005 (W): more induction, strong induction (MR §2.3 through 2.8)
• 28 September 2005 (W): the Fibonacci numbers, even more induction (MR Chapter 2).

• 3 October 2005 (M): relations begun (MR §0.1 (relations))
• 5 October 2005 (W): relations, Painter's Algorithm (MR §0.1 (relations) and Wikipedia binary relations, equivalence relations, partial orders, Painter's Algorithm)
• 7 October 2005 (F): a magic trick; counting basics (MR §4.1, §4.2)

• 10 October 2005 (M): pigeonhole principle, generalized product rule (MR §4.3, §4.4, §4.10)
• 12 October 2005 (W): division rule, inclusion/exclusion, permutations, combinations (MR §4.4, §4.7)
• 14 October 2005 (F): Midterm!

• 17 October 2005 (M): midterm break.
• 19 October 2005 (W): counting practice, binomial theorem, combinatorial proofs (MR §4.5, §4.6)
• 21 October 2005 (F): intro to probability (MR §6.1, §6.2)

• 24 October 2005 (M): conditional probability (MR §6.3, "Frequency vs. probability formats: Framing the three doors problem" by E. Aaron, M. Spivey-Knowlton)
• 26 October 2005 (W): hashing (MR §6.3)
• 28 October 2005 (F): expectation, random variables (MR §6.3 through §6.5, §6.9)

• 31 October 2005 (M): randomized select (MR §6.9)
• 2 November 2005 (W): graph introduction (MR §3.1, §3.2, §3.5)
• 4 November 2005 (F): BFS, DFS, distances, diameter (MR §3.4)

• 7 November 2005 (M): Dijkstra's algorithm (MR §3.4)
• 9 November 2005 (W): Dijkstra concluded; trees (MR §3.1, §3.7)
• 11 November 2005 (F): more trees, graph coloring and bipartite graphs (MR §3.8)

• 14 November 2005 (M): bipartite graphs concluded, algorithmic performance (MR §3.8, §0.3, §1.1, § 1.5)
• 16 November 2005 (W): recurrence relations (MR §5.1; §5.8).