Lecture log
- Wednesday, 12/9:
Review for the final exam.
- Monday, 12/7:
Huffman coding.
Handouts: Huffman coding practice problems and solutions
- Friday, 12/4:
EXAM 3!
- Wednesday, 12/2:
Review for Exam 3.
- Monday, 11/30:
Binary codes. Definitions: binary code, prefix-free. Encoding and decoding.
Handouts: binary coding practice problems and solutions
- Friday, 11/20:
Determining your Illinois driver's license number.
Handouts: IL driver's license number encoding scheme and auxiliary tables
- Wednesday, 11/18:
Finished ISBNs. Soundex coding.
- Monday, 11/16:
More on identification numbers: single-digit and transposition errors, UPCs, started ISBNs.
Handouts: Homework 6, due 11/30/09; UPC worksheet
- Friday, 11/13:
Started coding. Identification numbers and check digits.
Handouts: mixed strategy problems and solutions; game tree problems and solutions.
- Wednesday, 11/11:
Finished up game trees and backward induction.
- Monday, 11/9:
Game trees and backward induction.
Handouts: dollar auction worksheet
- Friday, 11/6:
Finished mixed strategies. Briefly introduced game trees.
- Wednesday, 11/4:
More game theory. Finished Chicken. Started on mixed strategies: betting game, studying game.
- Monday, 11/2:
Started game theory. Definitions: strategy, payoff, payoff matrix, Nash equilibrium. Prisoners' Dilemma. The game of Chicken.
Handouts: Homework 5, due 11/16/09.
- Friday, 10/30:
EXAM 2!
- Wednesday, 10/28:
Review for exam 2.
- Monday, 10/26:
(Chapters 13.4, 13.5, 13.6): Cake cutting. Divide-and-Choose, Lone Divider, Selfridge-Conway.
- Friday, 10/23:
(Chapter 13.2): Finished Knaster inheritance procedure.
- Wednesday, 10/21:
(Chapter 13.1, 13.2): More on the adjusted winner procedure. Started the Knaster inheritance procedure.
- Monday, 10/19:
(Chapter 13.1): Introduced fair division. Started the adjusted winner procedure.
Handouts: Homework 4, due 10/26/09.
- Friday, 10/16:
(Chapters 10.3, 10.4): The Gibbert-Sattherthwaite Theorem. The Chair's Paradox.
- Wednesday, 10/14:
(Chapters 10.1, 10.2): Formal definition of manipulability. Non-manipulability of majority rule and Condorcet's method. Manipulability of the Borda count and
sequential pairwise voting. Agenda manipulation.
Handouts: manipulability worksheet
- Monday, 10/12:
(Chapters 9.2, 9.3, 10.1): The Hare system and monotonicity. Arrow's Impossibility Theorem. Proof of a weakening of AIT. Started manipulability.
- Friday, 10/9:
(Chapter 9.2) More voting systems: sequential pairwise voting, the Pareto condition. Started the Hare system.
- Wednesday, 10/7:
(Chapter 9.2) More on voting systems: plurality voting, the Borda count, independence of irrelevant alternatives.
Just started sequential pairwise voting.
Handouts: dictatorship worksheet
- Monday, 10/5:
(Chapter 9.1) Introduction to voting systems. Majority rule and May's Theorem. Preference list ballots. Condorcet's Method.
Handouts: Homework 3, due 10/19/09.
- Friday, 10/2:
EXAM 1!
- Wednesday, 9/30:
Review for exam 1.
- Monday, 9/28:
(Chapter 3.1) More on generalized scheduling and the Generalized List-Processing algorithm. Touched on the Critical-Path Scheduling algorithm.
- Friday, 9/25:
(Chapter 3.1) Generalized scheduling. Order-requirement digraphs. Generalized List-Processing algorithm.
- Wednesday, 9/23:
(Chapter 3.3) Scheduling independent tasks. List-Processing algorithm, "Decreasing" List-Processing algorithm.
- Monday, 9/21:
(Chapter 3.4) Bin packing. Motivation and formal statement. Next-Fit, First-Fit, Worst-Fit heuristics and "decreasing" versions of each.
- Friday, 9/18:
Finished planarity. Kuratowski's Theorem and proving nonplanarity of specific graphs.
- Wednesday, 9/16:
More planarity. Euler's Formula and proof that the complete graph on 5 vertices is nonplanar. Definitions: face, unbounded face, contraction of an edge.
- Monday, 9/14:
Started planarity. Definitions: planar graph, planar embedding.
Handouts: planarity worksheet
- Friday, 9/11:
More graph coloring: checking for / finding 2-colorings, greedy coloring algorithm.
- Wednesday, 9/9:
Started graph coloring. Definitions: coloring, k-colorable, chromatic number. Application of graph coloring to scheduling problems.
Handouts: coloring worksheet
- Monday, 9/7:
No class (Labor Day)
- Friday, 9/4:
Finished sorted-edges heuristic for TSP. Introduced the Minimum-cost Spanning Tree Problem. Definitions: tree, spanning tree. Kruskal's Algorithm for MST.
Handouts: lecture notes (page 1, page 2, page 3)
- Wednesday, 9/2:
Definitions: Hamiltonian circuit, complete graph. Introduced the Traveling Salesman Problem. Briefly discussed NP-completeness (or: why TSP is probably very hard).
Went over the nearest-neighbor heuristic for TSP. Started the sorted-edges heuristic.
- Monday, 8/31:
Finished eulerization. Used eulerization to solve the Chinese Postman Problem in unweighted graphs. Briefly discussed the generalized CPP (i.e. the CPP in weighted
graphs).
Handouts: Homework 1, due 9/14.
- Friday, 8/28:
Presented an algorithm for finding Eulerian circuits in Eulerian digraphs (the "Voltron algorithm"). Started eulerization.
- Wednesday, 8/26:
Recap of characterization of Eulerian graphs. Presented an algorithm for finding Eulerian circuits ("don't burn your bridges"). Introduced the "street sweeper"
problem (i.e. the Eulerian circuit problem in directed graphs). Definitions: directed graph (a.k.a. digraph), in-degree, out-degree, strongly connected. Stated the
characterization of Eulerian digraphs.
Handouts: lecture notes (page 1, page 2)
- Monday, 8/24:
Went over course logistics -- office hours, grading, course overview, etc. Introduced graphs via the Königsberg bridge problem. Gave basic definitions:
graph, vertex, edge, degree, path, circuit, connected graph, Eulerian circuit, Eulerian graph. Stated Euler's characterization of Eulerian graphs.
Handouts: syllabus, Eulerian graph worksheet.
