Discrete Structures - Spring, 2012

Calendar—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. 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 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. How do you use LaTeX? Who is John Conway? 7-May 14 Read East West 14-May 15 21-May