CSTBC: Theory Bridge Course
Instructor: Kevin Milans (milans@uiuc.edu)
Newsgroup: news.cs.uiuc.edu/class.i2cs.theory-bridge
Photo by Bryan Clark
|
CSTBC: Theory Bridge CourseInstructor: Kevin Milans (milans@uiuc.edu) Newsgroup: news.cs.uiuc.edu/class.i2cs.theory-bridge |
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; k-ary, 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: triangle-free graphs; directed graphs | video12 | slides12 | - | - | - |
| 13 | July 10 | July 10 | 1:14 | Recurrence relations | video13 | slides13 | - | - | - |
| 14 | July 12 | July 12 | 1:24 | Big-Oh notation; recusion trees | video14 | slides14 | - | - | - |
| 15 | July 17 | July 17 | 1:17 | Little-Oh 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 1-x ≤ 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 | 1-6 | pdf, txt, tex, lyx | exam1 solns | q-exam1 |
| 2 | July 20 | July 30 | 7-17 | pdf, txt, tex, lyx, fig1, fig2 | exam2 solns | q-exam2 |
| 3 | August 3 | August 13 | 18-24 | pdf, txt, tex, lyx | exam3 solns | - |
Last Modified: 14 August 2007