CSTBC: Theory Bridge CourseInstructor: Kevin Milans (milans@uiuc.edu) Newsgroup: news.cs.uiuc.edu/class.i2cs.theorybridge 

Photo by Bryan Clark 
 August 14: Lecture 27 is now posted; while recording the exam 3 discussion, I found a small mistake on problem #5. The exam and solution set have been fixed.
 August 14: Exam 3 solutions are now available. Good luck in CS473!
 August 4: Exam 3 is now available.
Lect. No.  R.D.  P.D.  Length  Summary  Video  Slides  HW  HW Solns  Questions 
1  June 4  June 4  1:27  Introduction; sets; functions  video1  slides1  hw1  hw1 solns  q1 
2  June 5  June 6  1:36  Permutations; binomial coefficients; bijective proofs  video2  slides2  hw2  hw2 solns  q2 
3  June 7  June 8  1:08  Graphs; pigeonhole principle; proofs by contradiction  video3  slides3  hw3  hw3 solns  q3 
4  June 12  June 12  1:16  Induction and recursion  video4  slides4  none  none   
5  June 12  June 13  1:12  Induction: examples  video5  slides5  ex1     
6  June 14  June 15  1:08  Induction: Ramsey theory  video6  slides6  ex1     
7  June 19  June 19  1:07  Relations; equivalence relations; components  video7  slides7  ex1     
8  June 19  June 19  0:52  Subgraphs; graph isomorphism; trees  video8  slides8  ex1     
9  June 21  June 21  1:30  Induction: an incorrect proof; kary, binary trees  video9  slides9  ex1     
10  June 28  June 29  1:23  Exam 1 Discussion  video10  slides10  none  none   
11  June 28  June 29  1:12  Induction: Kraft's inequality; dominoes and Eulerian circuits  video11  slides11  hw11     
12  July 10  July 10  1:10  Induction: trianglefree graphs; directed graphs  video12  slides12       
13  July 10  July 10  1:14  Recurrence relations  video13  slides13       
14  July 12  July 12  1:24  BigOh notation; recusion trees  video14  slides14       
15  July 17  July 17  1:17  LittleOh notation; geometric, harmonic series; recursion trees  video15  slides15  none    q15 
16  July 17  July 17  1:12  Linear recurrences: characteristic equation method  video16  slides16  read  n/a   
17  July 19  July 19  1:24  Discrete probability: introduction  video17  slides17  none     
18  July 24  July 24  1:22  Conditional probability; independence; birthday paradox  video18  slides18  ex2     
19  July 26  July 26  1:11  Bound 1x ≤ e^{x}; method of conditional probabilities  video19  slides19  ex2     
20  July 26  July 26  0:59  Random variables; expectation; linearity of expectation  video20  slides20  ex2     
21  July 31  July 31  1:09  Linearity of expectation; conditional expectation; coupon collection  video21  slides21  ex2     
22  August 2  August 2  1:16  Exam 2 Discussion  video22  slides22       
23  August 2  August 2  1:09  Random walk on the path  video23  slides23       
24  August 7  August 7  1:08  Markov's inequality; the probabilistic method  video24  slides24  ex3     
25  August 9  August 9  1:03  Introduction to algorithm analysis  video25  slides25  ex3     
26  August 9  August 9  1:12  More algorithm analysis; linear time median/selection  video26  slides26  ex3     
27  August 14  August 14  1:32  Exam 3 Discussion  video27  slides27       
R.D.: Record Date
P.D.: Post Date
Exam No.  Released  Due  Lectures Covered  Exam  Exam Solutions  Questions 
1  June 15  June 25  16  pdf, txt, tex, lyx  exam1 solns  qexam1 
2  July 20  July 30  717  pdf, txt, tex, lyx, fig1, fig2  exam2 solns  qexam2 
3  August 3  August 13  1824  pdf, txt, tex, lyx  exam3 solns   
Last Modified: 14 August 2007