ECS 20 - Discrete Mathematics for Computer Science

Winter 2017

Schedule and assignments listed below; (Basic course info page here.)


Tentative Lecture Plan#: (Handouts will be updated throughout quarter.)

Lecture Date Topics Covered Section in Textbook Web Links/ Handouts
1 Jan 10 Intro, Propositional logic,
Logical Connectives, Truth tables
*, Sec 1.1 Math Symbols
Logic Symbols
Truth Tables for Logic Operators
Handout 1 (pdf)
Slides, Lec 1 (pdf)
2 Jan 12 Implications, Logical equivalences Sec 1.2, 1.3 Propositional Calculus
Handout 2 (pdf)
Slides, Lec 2 (pdf)
3 Jan 17 Predicate logic, and Quantifiers
Sec 1.3, 1.4 Prolog language
Common logical fallacies
Slides, Lec 3 (pdf)
4 Jan 19 Rules of Inference, Logical forms, Methods of Proof Sec 1.5, 1.6 Win a million dollars with maths
Millenium Prizes
Handout 3 (pdf)
Slides, Lecs 4 - 5 (pdf)
5 Jan 24 More Proofs
Sec 1.7
Existence Proof: Tic-tac-toe
Handout 3 (pdf)
Slides, Lecs 4 - 5 (pdf)
6 Jan 26 Sets Sec 2.1, 2.2 Handout 4 (pdf)
Slides, Lecs 6 (pdf)
7 Jan 31 Functions
Sec 2.3 
Handout 5 (pdf)
Slides, Lec 7 (pdf)
8 Feb 2 Sequences and Summations Sec 2.4 Sloane's Online Encyclopedia
Handout 6 (pdf)
Slides, Lec 8 (pdf)
Written Notes, Lec 8 (pdf)
9 Feb 7 Finish Summations and mini-review
Sec 2.4 Review probs for midterm
Solutions to review probs
10 Feb 9 Review Note on binary numbers
NOTES: MIDTERM REVIEW
Feb 14 MIDTERM

Midterm solutions
11 Feb 16 Algorithms, Complexity Sec 3.1-3.3 Foundations of algebra
Handout 7 (pdf)
Slides, Lec 11 (pdf)
12 Feb 21 Function Growth, Complexity Sec 3.2-3.3 Big-Oh notation (Wikipedia)
Handout 8 (pdf)
Slides, Lec 12 (pdf)
Written Notes, Lec 12 (pdf)
The Halting Problem
13 Feb 23 Mathematical Induction, Strong induction 
Sec 4.1-4.2
(5.1-5.2 in 7th ed)
Example of not Big-O
Induction
Why induction is valid
Handout 9 (pdf)
14 Feb 28 Recursive Definitions, Structural Induction, Recursive Algorithms Sec 4.3-4.4
(5.3-5.4 in 7th ed)
Images of recursive fractals
Fibonacci Numbers
Handout 10 (pdf)
15 Mar 2 Product and sum rules, Pigeonhole Principle Sec 5.1-5.2
(6.1-6.2 in 7th ed)
Counting Problems
Handout 11 (pdf)
Written Notes, Lec 15 (pdf)
16 Mar 7 Permutations, Combinations, Poker,
Binomial Coefficients
Sec 5.3-5.4
(6.3-6.4 in 7th ed)
Travelling Salesman Prob (TSP)
Counting Problems
Handout 12 (pdf)
Written Notes, Lec 16 (pdf)
17 Mar 9 Discrete Probability
Sec 6.1-6.2
(7.1-7.2 in 7th ed)
Counting Problems
The Eudaemonic Pie
Handout 13 (pdf)
Written Notes, Lec 17 (pdf)
18 Mar 14 Conditional Probability Sec 6.3, 7.1
(7.3, 8.1 in 7th ed)
Monty Hall Problem (wikipedia)
Monty Hall Problem (Coopertoons)
Handout 14 (pdf)
Written Notes, Lec 18 (pdf)
19 Mar 16 Review Poker probabilities (and history
of probability theory)

Written Notes, Lec 19 (pdf)
March 23 Final Exam, 1pm
Resources for Internships:
  • UCD Internship and Career Center
  • NSF Research Experiences for Undergrads
    (NSF, REU CS opportunities)
  • AMS many listings (cisco, dell, ibm, xerox)
  • Microsoft
    Microsoft Research
  • Google
  • Fogcreek (NYC, includes housing)
  • Apple
  • Adobe
  • internships.com
  • Postings typically updated early Dec.

  • Deadlines tend to be
    early Jan through mid-Feb.
  • Resources for CS students:
  • ACM student magazine
  • Resources for additional help:
  • DCSC
  • Kahn Academy
  • # may change as we progress into the quarter; you should check it every week
    * material was/maybe used that is not in your book


    Watch this space for assignments and solutions: (Schedule subject to change.)

    -- Due in ECS20 Homework Box in Room 2131, Kemper Hall by 4:25pm
    -- Write your discussion section at the top of the assignment. (HW returned in discusson sections.)