U Chicago CS Dept Logo
University of Chicago CSPP 50102—General Information

CSPP 50102: Mathematics for Computer Science
Summer 2011
General Information

Goal

This course is an introduction to ideas and techniques from discrete mathematics that are widely used in computer science. Topics include: propositional logic and quantifiers, proof methods, mathematical induction and recursion, sets and functions, growth of functions and asymptotic notation, sums, series and closed forms, recurrences and methods of solving recurrences, basics of counting, discrete probability, conditional probability and independence, random variables, expected value, linearity of expectation, variance, graph theory, modular arithmetic and Euclid's algorithm. This course is prerequisite for courses in Algorithms, Databases, Networks, Data Mining, and Numerical Methods.

Prerequisites

Precalculus, especially logarithms and exponentials, is a prerequisite; calculus is not required. There are no computer science prerequisites.

Textbook

The required text for the course is Discrete Mathematics and its Applications. 6th ed. (McGraw-Hill, 2007) by Kenneth H. Rosen (ISBN 978-0073229720). The text also may be purchased at reduced prices in used condition.
Recommended book:
Mathematical Thinking: Problem-solving and Proofs. 2nd ed. (Prentice-Hall, 2000) by Johh P. D'Angelo and Douglas B. West (ISBN 0130144126) = West

Syllabus

week topics
1 logic (ch 1):
propositional and quantifier logic
2 mathematical proof (ch 4):
proof methods; mathematical induction
3 fundamental mathematics (ch 2):
sets, relations, and functions
4 growth of functions (ch 3):
asymptotic notation
5 arithmetic and geometric sums (ch 2):
recursion (ch 4)
6 recurrences (ch 7):
methods of solving recurrences
7 counting (ch 5):
counting methods
8 discrete probability (ch 6):
independence and conditional probability
9 Bayes's theorem (ch 6):
Bernoulli trials and binomial distribution
10 random variables and expected value (ch 6):
linearity of expectation and variance
11 graph theory (ch 9):
Euler and Hamilton cycles; connectedness
12 trees, bipartite graphs, matching (ch 10)
graph isomorphism; planar graphs
13 modular arithmetic (ch 3);
Euclid's algorithm; multiplicative inverses
14 final exam
brady at cs dot uchicago dot edu