Some Thoughts for the New Course

When Eric wrote "Hamzeh tells me that a recent change in the curriculum gives us space to insert one more math course into our Honours programme," I got very excited.

Possible New Course: Great Theoretical Ideas In Computer Science
The course will give the high level understanding of a wide range of topics and show students that theory is both fun and useful.

To avoid downloading time I have downloaded all files locally. You will need powerpoint to view most of these pages.

  • Previous mail about the new course

  • 2001: I have said that I do not like 2001. The truth is that I am frustrated that no matter what I do the students seem to come out of it thinking that it is theoretical mumble jumble that is scary, boring, and useless. My understanding of why 2001 is important for many later courses is that it is to teach students to have an abstract view of computation and to translate between different models like JAVA, DFA, regular languages, TM. I would like to find a way to ground this material in things that they understand and find practical. This is the best I have done so far.
    Jeff's 2001 Notes

    Students can write small loops to check simple string properties, but even after 2001 most cant write a DFA. These are notes of mine that attempt to give them the abstract understanding to translate a JAVA loop program into a DFA. I am also quite religious about loop invariants. I would like it covered over and over again.

  • 3101: These are a number of topics that I have spent too much time on in 3101 and that could be covered earlier in a more computer science way. (Jeff's 3101 Notes)
    00-Introduction (ps) Some philosophies and overview

    I realize that they take quantifiers in various courses. However, I find that when they get to 3101, they really do not get it. I also feel that it is core. I wrote something for 3101 that could be moved earlier. It explains quantifiers as a game between a prover and a verifier.
    Math (ps) BigOh, Sums, Recurrence Relations
    Iterative (ps) As said, I am also quite religious about loop invariants. These slides give my intuition about them.
    Recursion (ps) Students find recursion surprisingly hard.

  • Steven Rudich's course As said Steven's course has been given with tremendous success both at Carnegie Mellon and Berkeley. They do one topic an hour. I thought we could do one every 1.5 hours.
    01 intro.ppt Philosophies of CS Theory
    02 dating.ppt Stable Marriage Problem. Algorithms and Proofs
    03 powers.ppt Prove upper and lower bounds of log b to compute a^b.
    04 mult.ppt Asymptotics and recursive algorithms for multiplying
    05 golden.ppt Golden Ratio & Fibonacci numbers.
    06 counting.ppt Counting, 1-1 mappings, # of choices, {n choose a), ...
    07 parallel.ppt Parallel Computation, Circuit Depth, Log depth adder, Log depth multiplier
    08 flex.ppt More Counting, Binomial Coefficient
    09 polycount.ppt More Counting, Enumeration & Generating Functions. (** This was jeff's favorite undergrad course.**)
    10 inclusion.ppt Set intersections, Inclusion, Exclusion, probabilities.
    11 infinity.ppt Countable, Uncountable, Representations.
    12 undecidability.ppt Halting Problem, Godel's Incompleteness Theorem.
    13 NP_Complete.ppt Excellent Class on NP Reductions.
    14 groups.ppt Groups Theory and Subgroups
    15 automata.ppt DFA, Regular languages, DFA cant count.
    17 expectations.ppt Probability Theory and Expectation
    18 pitfall.ppt Cool things that go wrong with probability theory
    20 primality.ppt Unique Prime Factoring, Density of Primes, Fermat's Little Theorem, Primality Testing.
    21 Chaitin.ppt Paradoxes, Randomness, Incompressible strings,
    22 graphs.ppt Graph Theory, Hamiltonian Paths, DFA
    23 wind.ppt Counting # of trees, games strategies
    25 planarity.ppt Planer graphs, Faces, Forbidden Minors, Art Gallery Theorem.
    26 ramsey.ppt Ramsey Theory
    28 rsa.ppt Cryptography.