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 calculatorConnectives, 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 - 306-Feb 2 1.5: Methods of Proof

MMLogic

Logic Circuits and Boolean Algebra

by Clive MaxfieldDirect 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 Solutions13-Feb 3 2.1: Graphs

2.2: Sets20-Feb 4 2.3: Functions

2.4: Relations and EquivalencesMAA site for sets quiz 2.3 Solutions

2.4 Solutions27-Feb 5 2.5: Partially Ordered Sets (posets)

2.6: Graph Theory

3.1: Recurrence RelationsThe 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 15-Mar 6 3.2: Closed Form Solutions and Induction

3.3: Recursive Definitions

3.4: Proof by Induction

3.5: Recursive Data StructuresThe Chaos Game.

3.2: 20, 22, 23, 24

363.3: 24, 26, 28, 29

3.4: 18, 22, 24

3.5: 20, 21, 22, 23, 2412-Mar 7 4.1: Basic Counting

4.2: Selections and ArrangementsRead The Fourth Way to Sample kObjects from a Collection ofn4.2: 20, 22, 28, 30 19-Mar 8 4.3: Counting With Functions

4.4: Discrete Probability4.3: 8, 12, 14, 22, 29, 30

4.4: 6, 10, 14, 16, 18, 22, 2626-Mar 9 4.5: Counting Operations in Algorithms

4.6: EstimationChapter 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 ComplexityOhio State Greedy Algorithms

UC Davis Lecture on P/NPUCB'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.

23-April 12 6.2 Social Networks

6.3: Structure of Languages

Study the finite state machine of quatrainment with articles here and here.

30-April 13 6.4 Discrete Time Population Models The solutions to the second test are now available. Who is John Conway?

7-May 14 Read East West 14-May 15 21-May