[ news | information | lectures | problem sets | links ]

CS55 - Spring 2008
TR 2:45-4:00 in Lincoln 1135
Prof. Chen

News

Please check here regularly for assorted announcements. You are responsible for being aware of any information posted here.
  • 4/12/2008: No office hours tomorrow (4/13).
  • 3/22/2008: No office hours tomorrow (3/23).
  • 2/27/2008: I'm cancelling my office hours on Sunday 3/2. Instead I will have office hours on Friday 2/29 from 1:15-3:30.
  • 2/13/08: The first midterm will be in class on Thursday 2/21. It will be open notes (but closed book).

    • Information

    CS55 is an introduction to discrete mathematics for computer scientists. In particular, we will study finite mathematical structures and ways to build them, count them, and analyze them. The topics and examples will be chosen to relate to concepts of interest in the design and analysis of computer algorithms.

    No programming experience is required (or assumed). However, mathematical maturity (as evidenced by passing first semester calculus) and an interest in applications of math to computer science is a prerequisite.

    The lectures are on Tuesdays and Thursdays from 2:45-4:00 in Lincoln 1135

  • Administrivia <pdf>

    • Lectures

    Any topic that's listed for a date in the future should be taken as tentative. Any topic that's listed for a date at least 2 days in the past is what was actually covered in that lecture.

    Week Date In class Assignment due
    1 (Tue) 1/22 introduction, administrivia, review
    (Thu) 1/24 problem solving, proofs (part 1)
    triangles (1,2)
    2 (Tue) 1/29 propositional logic
    assorted related topics     		ps1
    (Thu) 1/31 circuits
    quantifiers, proofs (part 2)
    3 (Tue) 2/5 proofs (recap), induction ps2
    (Thu) 2/7 strong induction
    recurrences
    guess-and-check, substitution
    4 (Tue) 2/12 more on recurrences
    more on induction     		ps3
    (Thu) 2/14 algorithms (sorting dates)
    asymptotics
    5 (Tue) 2/19 review for midterm
    survey    		 ps4
    (Thu) 2/21
    Midterm
    6 (Tue) 2/26 introduction to sets
    diagonalization
    (Thu) 2/28 counting: addition/multiplication rules,
    pigeonhole principle, inclusion-exclusion
    7 (Tue) 3/4 combinations and permutations
    introduction to probability     		ps5
    (Thu) 3/6 more probability
    conditional probability
    8 (Tue) 3/11 random variables
    expected value     		ps6
    (Thu) 3/13
    *** class cancelled ***
    (Tue) 3/18
    *** no class: Spring Break ***
    (Thu) 3/20
    9 (Tue) 3/25 probability (review)
    compression     		ps7 (optional)
    (Thu) 3/27 compression (II)
    tangents on images
    relations
    10 (Tue) 4/1 relations
    functions     		ps8
    (Thu) 4/3 numbers
    11 (Tue) 4/8 review for midterm ps9
    (Thu) 4/10
    Midterm
    12 (Tue) 4/15 introduction to graphs
    article on citation analysis (pages 95-100)
    (Thu) 4/17 subgraphs, Eulerian circuits
    13 (Tue) 4/22 Hamiltonian cycles
    introduction to P/NP
    connectivity     		ps10
    (Thu) 4/24 planarity
    colorings
    14 (Tue) 4/29 trees, applications of graphs
    evaluations     		ps11
    (Thu) 5/1 Guest lecture by Dan Barcay '06
    15 (Tue) 5/6 wrap-up, review for final ps12

    The final exam will be on Thursday, May 15 at 2PM.

    Problem Sets

  • ps1, due 2:45PM on 1/29 <tex><pdf>
  • ps2, due 2:45PM on 2/5 <tex><pdf>
  • ps3, due 2:45PM on 2/12 <tex><pdf>
  • ps4, due 2:45PM on 2/19 <tex><pdf>
  • ps5, due 2:45PM on 3/4 <tex><pdf>
  • ps6, due 2:45PM on 3/11 <tex><pdf>
  • ps7 (optional), due 2:45PM on 3/25 <tex><pdf>
  • ps8, due 2:45PM on 4/1 <tex><pdf>
  • ps9, due 2:45PM on 4/8 <tex><pdf>
  • ps10, due 2:45PM on 4/22 <tex><pdf>
  • ps11, due 2:45PM on 4/29 <tex><pdf>
  • ps12, due 2:45PM on 5/6 <tex><pdf>

    • Links

  • some pages discussing LaTeX, which is the best way to format anything containing mathematical equations.
  • A simple latex document sample.tex that creates the file <sample.pdf>
  • A gentle introduction to TeX by Laura Tallman and Michael Kozdron.
  • The Not So Short Introduction to LaTeX2e, also known as LaTeX2e in 139 minutes by Oetiker, Partl, Hyna, and Schlegl. (This is an evolving document, at the moment they're on version 4.20, dated May 2006.)
  • Information specific to running TeX on the DCI systems is here, and information on TeX distributions can be found here.
    • "Computers do not solve problems, they execute solutions"
    --Laurent Gasser