COMPSCI 230: Discrete Mathematics for Computer Science, Fall 2012

[Test image]

This is a self-contained course. The lectures for this course are primarily developed by Professor Steven Rudich.


Instructor: Bruce Maggs (
Graduate TA: Mahanth Gowda (
Undergraduate TA: Nicholas Gordon (

Lectures Time: Tuesday and Thursday, 3:05 pm -4:20 pm
Lectures Location: LSRC D106
Recitation Time: Friday, 11:45 am -1:00 pm
Recitation Location: Social Sciences 119

Office Hours:
Bruce Maggs: Tuesday and Thursday after class in LSRC D324
Mahanth Gowda: Tuesday 1 pm-2 pm in LSRC D307
Nicholas Gordon: Monday 5 pm-6 pm in the Link, in the lower level of Perkins Library

Homeworks (40%), Quizzes (30%) and Final (30%)
Please turn in your homeworks at the beginning of the class on the day it is due. There is a penalty of seven points a day late on the homework. Regarding collaboration/cheating policy, you may NOT share written work.
We reuse homework problems.

Sep 27: Sample Quizzes to help prepare for Quiz-1, from 2010 and 2011. Solutions are here - 2010 and 2011.
Oct 23: Sample Quizzes to help prepare for Quiz-2, from 2010 and 2011. Solutions are here - 2010 and 2011
Nov 20: Sample Quiz to help you prepare for Quiz-3, from 2011. Solutions are here - 2011


Note: All readings are from Discrete Mathematics and its Applications by Kenneth H. Rosen, published by McGraw-Hill (7th edition).

DateLecture TopicSlidesReadingAssignment
Aug 28 Pancakes with a problem Lecture 1  
Aug 30 Deterministic Finite Automata Lecture 213.2-13.4 
Aug 31 NO CLASSES   
Sept 4 Solving problems and writing proofs Lecture 31.7-1.8Homework 1
Sept 6 Inductive ReasoningLecture 45.1-5.3 
Sept 7 Recitation: DFA   
Sept 11 Ancient Wisdom: Unary and BinaryLecture 54.1-4.2  
Sept 13 Counting I: Correspondences and Choice TreesLecture 66.1-6.3 
Sept 14 Recitation: Proofs   
Sept 18 Counting II: Recurring Problems and CorrespondencesLecture 76.1-6.3, 2.3
Sept 20 Counting IIILecture 86.4Homework 2
Sept 21Recitation : Counting   
Sept 25 Probability I: Counting in Terms of ProportionsLecture 97.1-7.2 
Sept 27 Probability II: Great ExpectationsLecture 107.4 
Sept 28Recitation: Quiz Preperation   
Oct 2QUIZ 1   
Oct 4 Random WalksLecture 11 
Oct 5Recitation      
Oct 9 Ancient Wisdom: On Raising A Number to a PowerLecture 12  Homework 3
Oct 11Euclid's Algorithm and Continued FractionsLecture 134.3 
Oct 12Recitation    
Oct 18 Randomness and ComputationLecture 144.4 (Fermat's Little Theorem) 
Oct 19Recitation    
Oct 23 Fibonacci Numbers, Polynomial Coefficients, Vector Programs Lecture 15   
Oct 25Modular Arithmetic and the RSA CryptosystemLecture 164.1-4.6Homework 4
Oct 26Recitation    
Oct 30Group TheoryLecture 17  
Nov 1 GraphsLecture 1810.1-10.3 (Graph Representation only),
10.7-10.8, 11.1, 11.4
Nov 2Recitation   
Nov 6 Graphs IILecture 1911.5, 10.2 
Nov 8QUIZ 2   
Nov 9Recitation   
Nov 13How Computers Really Do ArithmeticLecture 20 
Nov 15The Big OhLecture 213.2 
Nov 16NO Classes   
Nov 20Cantor's Legacy: Infinity and DiagonalizationLecture 222.5Homework 5
Nov 22NO CLASSES, Thanksgiving recess   
Nov 23NO CLASSES, Thanksgiving recess   
Nov 27Turing's Legacy: The Limits of ComputationLecture 2313.5 
Nov 29Godel's Legacy: What is a Proof?Lecture 24  
Nov 30Recitation   
Dec 4QUIZ 3  
Dec 6Complexity Theory: Reductions Between Computational Problems, The P vs. NP Question  
Dec 7Recitation   
Dec 11FINAL EXAM 2:00pm-5:00pmLoc: LSRC D106