University of Chicago CSPP 50102—General Information

CSPP 50102: Mathematics for Computer Science: Discrete Mathematics Summer: 2012 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 (direct proof, proof by contradiction, case analysis, mathematical induction), basic number theory (GCD, Euclid's algorithm, prime factorization, modular arithmetic), summations and closed forms, growth of functions and asymptotic notation, basics of counting (permutations, combinations, binomial theorem, pigeonhole principle), recurrences and methods of solving linear recurrences, basic graph theory (connectedness, trees, bipartite graphs), discrete probability, conditional probability and independence, random variables, expected value, and variance. This course is prerequisite for courses in Algorithms, Databases, Networks, Systems, 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. 7th ed. (McGraw-Hill) by Kenneth H. Rosen (ISBN 978-0073383095).
This course will also support the 6th edition of the same textbook: Discrete Mathematics and its Applications. 6th ed. (McGraw-Hill, 2007) by Kenneth H. Rosen (ISBN 978-0073229720).
Recommended problem book:
Schaum's Outline of Discrete Mathematics (2nd edition) by Seymour Lipschutz et al. (ISBN 0070380457).

Syllabus

 week topics 1 basic logic (ch 1) methods of proof (ch 1) 2 mathematical induction (ch 5) fundamental mathematics: sets and functions (ch 2) 3 asymptotic notation (ch 3) sums, series, summations, and closed forms (ch 2) 4 basic counting (ch 6): permutations and combinations, binomial theorem, pigeonhole principle 5 recurrences (ch 8) methods of solving recurrences 6 midterm 7 basic graph theory (ch 10): paths, connectedness, trees, bipartite graphs 8/9 discrete probability (ch 7): independence and conditional probability, random variables, expected value, variance 10 basic number theory (ch 4): divisibility, primes, and and Euclid's algorithm 11 final exam

brady at cs dot uchicago dot edu