Discrete Structures - Spring, 2012

Week	Readings	Topics	Assignments
1	1.1: Formal Logic 1.2: Propositional Logic 1.3: Predicate Logic 1.4: Logic in Mathematics The Penn predicate logic calculator	Connectives, propositions, truth tables, equivalences, tautologies, contradictions, derivations, proofs, forward/backward, predicates, quantifiers, translations, negations, constructions, definitions, statements, counterexamples, axiomatic systems,	1.1: 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 18, 21, 22, 23, 24, 25, 26,27, 29, 30, 31 1.2: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26 1.1&1.2 Solutions 1.3: 1 - 25 1.3 Solutions 1.4: 1 - 30
6-Feb
2	1.5: Methods of Proof MMLogic Logic Circuits and Boolean Algebra by Clive Maxfield	Direct proof vs. proof by contradiction or contraposition	1.5: 1-24, even To turn in: 1.4: 22-30 even 1.5: 20,22,24 1.4&1.5 Solutions
13-Feb
3	2.1: Graphs 2.2: Sets
20-Feb
4	2.3: Functions 2.4: Relations and Equivalences	MAA site for sets quiz	2.3 Solutions 2.4 Solutions
27-Feb
5	2.5: Partially Ordered Sets (posets) 2.6: Graph Theory 3.1: Recurrence Relations	The theme for Math Awareness Month is "Mathematics, Statistics and the Data Deluge."	2.5: 14, 18. 22 2.5 Solutions 2.6: 12, 14, 16, 24, 30 2.6 Solutions 3.1: 6, 14, 20, 22, 26 Test 1
5-Mar
6	3.2: Closed Form Solutions and Induction 3.3: Recursive Definitions 3.4: Proof by Induction 3.5: Recursive Data Structures	The Chaos Game. Read An Algebraic Approach to Geometric Optimization	3.2: 20, 22, 23, 24 36 3.3: 24, 26, 28, 29 3.4: 18, 22, 24 3.5: 20, 21, 22, 23, 24
12-Mar
7	4.1: Basic Counting 4.2: Selections and Arrangements	Read The Fourth Way to Sample k Objects from a Collection of n	4.2: 20, 22, 28, 30
19-Mar
8	4.3: Counting With Functions 4.4: Discrete Probability	Chapters 1 and 2 Test Solutions Racket Getting Started with Racket How to Design Programs in Racket	4.3: 8, 12, 14, 22, 29, 30 4.4: 6, 10, 14, 16, 18, 22, 26
26-Mar
9	4.5: Counting Operations in Algorithms 4.6: Estimation	Chapter 3 and 4 Test	4.5: 20, 24,26, 28, 30 4.6: 16, 20, 24, 28, 30
9-April
10	5.1: Algorithms 5.2: Three Common Types of Algorithms: Traversal, Greedy, and Divide and Conquer 5.3: Algorithm Complexity	Ohio State Greedy Algorithms UC Davis Lecture on P/NP UCB's Vazirani's Algorithms	5.1:18, 22 5.2: 18, 22, 24 5.3: 14, 16, 22
16-April
11	6.1 DNA	Play Phylo Implement the UPGMA for various phylogenetic distance tables. Distance-Based Approaches to Inferring Phylogenetic Trees
23-April
12	6.2 Social Networks 6.3: Structure of Languages	Study the finite state machine of quatrainment with articles here and here. UCLA Linguistics I Quiz
30-April
13	6.4 Discrete Time Population Models	The solutions to the second test are now available.	Who is Donald Knuth? How do you use LaTeX? Who is John Conway?
7-May
14		Read East West
14-May
15
21-May