CS 228: Discrete Structures II
James Madison University, Fall 2013 Semester

### Schedule

Topics are subject to change. Section numbers are from the Rosen 7/e book; see Table of Contents.

1 Aug 26
Aug 28
Aug 30
Review CS 227 logic, CNF/DNF
Quantifiers, LaTeX crash course
Proof techniques and strategies
Sec 1.1--1.3
Sec 1.4--1.5
Sec 1.6--1.7

Scavenger Hunt   PDF Solution
2 Sep 02
Sep 04
Sep 06
Prime numbers, Python tutorial
Mod arithmetic, GCDs, LCMs
Sec 1.8, 4.1
Sec 4.2--4.3
Learn Python

HW #1 (due 09/06 before 9am)
3 Sep 09
Sep 11
Sep 13
Hashing, random, check digits
Shift/block ciphers, public key
Review CS 227 set operations
Sec 4.5
Sec 4.6
Sec 2.1--2.2

HW #2 (due 09/13 before 9am)
4 Sep 16
Sep 18
Sep 20
Recurrence relations, summations
Matrices, arithmetic, transposes
Review and prepare for Exam #1
Sec 2.4
Sec 2.6
Ex1 Prep

HW #3 (due 09/20 before 9am)
5 Sep 23
Sep 25
Sep 27
Exam #1 (in class)
Proof by mathematical induction
Strong induction, well-ordering

Sec 5.1
Sec 5.2
6 Sep 30
Oct 02
Oct 04
Product/sum rules, pigeonhole
Permutations and combinations
Probability theory, more Python
Sec 6.1--6.2
Sec 6.3--6.4
Sec 7.1

HW #4 (due 10/04 before 9am)
7 Oct 07
Oct 09
Oct 11
Random variables, distributions
Bayes' Theorem, classification
Functions, relations, composites
Sec 7.2
Sec 7.3
Sec 9.1

HW #5 (due 10/11 before 9am)
8 Oct 14
Oct 16
Oct 18
Matrix vs digraph representation
Transitive closure, Warshall algo
Graph structures and terminology
Sec 9.3
Sec 9.4
Sec 10.1--10.2

HW #6 (due 10/18 before 9am)
9 Oct 21
Oct 23
Oct 25
Representation and isomorphism
Graph connectivity, paths/circuits
Review and prepare for Exam #2
Sec 10.3
Sec 10.4
Ex2 Prep

HW #7 (due 10/25 before 9am)
10 Oct 28
Oct 30
Nov 01
Exam #2 (in class)
Euler/Hamilton, weighted graphs
Shortest paths, Dijkstra's, Floyd's

Sec 10.5
Sec 10.6
11 Nov 04
Nov 06
Nov 08
Graph coloring, trees and forests
Search trees, Huffmann coding
Traversal strategies, infix notation
Sec 10.8, 11.1
Sec 11.2
Sec 11.3

HW #8 (due 11/08 before 9am)
12 Nov 11
Nov 13
Nov 15
DFS backtracking, Prim/Kruskal
Finite-state machines with output
Sec 11.4
Sec 11.5
Sec 13.2

HW #9 (due 11/15 before 9am)
13 Nov 18
Nov 20
Nov 22
Set of strings, finite-state automata
Regular expressions, Kleene's thm
Crash course on Turing machines
Sec 13.3
Sec 13.4
Sec 13.5

HW #10 (due 11/22 before 9am)
Thanksgiving Break
14 Dec 02
Dec 04
Dec 06
Review chapters 1, 2, 4, 5
Review chapters 6, 7, 9, 10
Review chapters 11, 13, etc
Final Exam on Wednesday, December 11th, 8:00--10:00