ECS 20 - Discrete Mathematics for Computer Science

Spring 2019

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

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

Review
Lecture Date Topics Covered Sect in Textbook Web Links/ Handouts
1 Apr 2 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 Apr 4 Implications, Logical equivalences Sec 1.2, 1.3
  • Propositional Calculus
  • Handout 2 (pdf)
  • Slides, Lec 2 (pdf)
    		•
    3 Apr 9 Predicate logic, and Quantifiers
    		 Sec 1.3, 1.4
  • Prolog language
  • Common logical fallacies
  • Handout 2 (pdf), cont.
  • Slides, Lec 3 (pdf)
  • Written notes, Lec 3 (pdf)
    		•
    4 Apr 11 Sets Sec 2.1, 2.2
  • Handout 3 (pdf)
  • Slides, Lecs 4 (pdf)
  • Written notes, Lec 4 (pdf)
    		•
    5 Apr 16 Functions
    		 Sec 2.3 
  • Handout 4 (pdf)
  • Slides, Lec 5 (pdf)
    		•
    6 Apr 18 Rules of Inference, Logical forms, Methods of Proof Sec 1.5, 1.6
  • Win a million dollars with maths
  • Millenium Prizes
  • Handout 5 (pdf)
  • Slides, Lecs 6 (pdf)
  • Written notes, Lec 6 (pdf)
    		•
    7 Apr 23 More Proofs
    		 Sec 1.7
  • Existence Proof: Tic-tac-toe
  • Handout 5 (pdf)
  • Slides, Lec 7 (pdf)
  • Written notes, Lec 7 (pdf)
    		•
    8 Apr 25 Proofs, Sequences and Summations Sec 1.7, 2.4
  • "Cash for Math", Quanta magazine
  • Sloane's Online Encyclopedia
  • Handout 6 (pdf)
  • Written Notes, Lec 8 (pdf)
    		•
    9 Apr 30 Sequences and Summations
    		 Sec 2.4
  • History of prime numbers proof
  • Telescopic series
  • Handout 6 (pdf)
  • Written Notes, Lec 9 (pdf)
  • Proof of infinite primes (pdf)
    • 10 May 2 Algorithms, Complexity Sec 3.1
  • Review probs for midterm
  • SOLUTIONS to review probs
  • Origin of "algorithm"
  • Foundations of algebra
  • Handout 7 (pdf)
  • Written Notes, Lec 10 (pdf)
    • 11 May 7 Review
  • NOTES: MIDTERM REVIEW
    • May 9 MIDTERM
    12 May 14 Algorithms, Function Growth, Complexity Sec 3.2-3.3
  • Big-Oh notation (Wikipedia)
  • Handout 7 (pdf)
  • Handout 8 (pdf)
  • Slides, Lec 12 (pdf)
  • Written Notes, Lec 12 (pdf)
    		•
    13 May 16 Complexity, Mathematical Induction  
    Sec 5.1:
    pgs 311-321, 324, 329*
  • Induction
  • Handout 9 (pdf)
  • Written Notes, Lec 13 (pdf)
    		•
    14 May 21 Induction, Recursion & Recursive Functions Sec 5.3:
    pgs 344-347
  • Images of recursive fractals
  • Fibonacci Numbers
  • Handout 10 (pdf)
  • Written Notes, Lec 14 (pdf)

    		•
    15 May 23 Recursive Algorithms,
    Product and sum rules
    Sec 5.4 pgs 360-367
    Sec 6.1
  • Counting Problems
  • Handout 11 (pdf)
  • Notes, Lec 15 (pdf)

    		•
    16 May 28 Permutations, Combinations, Poker hands
    		Sec 6.3

  • Travelling Salesman Prob (TSP)
  • Counting Problems
  • Handout 12 (pdf)
  • Notes, Lec 16 (pdf)

    		•
    17 May 30 Bonus EC class!
    		 Sec 7.1-7.2
  • Counting Problems
  • Poker probabilities (and history
    of probability theory)
  • The Euler Award

    		•
    18 June 4 Discrete Probability
    		 Sec 7.1-7.2
  • Counting Problems
  • The Eudaemonic Pie
  • Handout 13 (pdf)
  • Notes, Lec 18 (pdf)

    		•
    19 June 6 Conditional Probability & Review
  • Monty Hall Problem (wikipedia)
  • Monty Hall Problem (Coopertoons)
  • Handout 14 (pdf)
  • Notes, Lec 19 (pdf)

    		•
    June 7 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
  • Apple
  • 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 HW assignments and solutions: (Schedule subject to change.)

    -- Due via GRADESCOPE --