Discrete Structures - Spring, 2017

Week Readings Topics Assignments 12 4.6: Estimation

5.1: Algorithms

5.2: Three Common Types of AlgosGrowth of function, estimation targets, Properties of Big-O, Pseudocode, Precondition and postcondition, iterative algos, Functions and recursive algos, traversal algos, greedy algos, Divide and Conquer algos

To turn in:

4.6: 24,28, 32

5.1: 18, 22, 24

5.2: 16, 20, 2424-Apr 11 4.4: Discrete Probability

4.5: Counting Operations in AlgorithmsPr(X) = |A|/|U|, Expected Value, Algorithms, Pseudocode, Loops, Arrays, Sorting

To turn in:

4.4: 22,24,26

4.5: 24, 28, 3017-Apr Spring Research

Break! 10 4.1: Basic Counting Techniques

4.2: Selections and Arrangements

4.3: Counting with Functions4.1: Addition, Multiplication, Mixing Addition and Multiplication

4.2: Permutations, Combinations, The Binomial Theorem

4.3: One-to-one Correspondence, Pigeonhole Principle, The Generalized Pigeonhole Principle, Ramsey Theory

TheFourthWaytoSamplekObejctsfromaCollectionofnRamseyTheoryIsSharppdfTo turn in:

4.1: 18--26, even

4.2: 18,20,24,28

4.3: 24, 28, 30, 323-Apr 9 3.4: Proof by Induction

3.5: Recursive Data Stuctures3.4: Proof by Induction

3.5: Recursive Data StucturesM15-C1_2Test

To turn in:

3.4: 18, 22, 24

3.5: 14-24,even27-Mar 8 3.1, 3.2Closed Form Solutions and Induction

3.3: Recursive Definitions3 .2: Closed Form Solutions and Induction M15-HW3_2solns

3.3: Recursive Definitions

M15-C1_2Test

To turn in: 3.1: 18,20,22

M15-HW3_1solns

and: 3.2: 14,18,22,24

M15-HW3_2solns

and: 3.3: 20,22,24

20-Mar 7 Review Review Review

13-Mar 6 2.6: Graph Theory Isomorphism of graphs, degree counting, euler paths and circuits, Hamiltonian paths and circuits, trees

New and improved link:

https://vptl.stanford.edu/events/professor-donald-knuths-22nd-annual-christmas-lecture-hamiltonian-paths-antiquity

http://www.steinertriples.fr/ncohen/tut/Graphs/#fewRead Chapters 2 and 3 in Gopalakrishnan.

6-Mar 5 2.4: Relations and Equivalences

2.5: Partially Ordered Sets (posets)

2.6: Graph Theoryequivalence relations, reflexivity, symmetry, transitivity, partition,Domain, codomain, one-to-one, onto, composition, inverse,f-graphs, r-graphs,directed,undirected graphs,equivalence relations, reflexivity, symmetry, transitivity, Hasse diagrams, topological sorting, Boolean algebras 2.4: Turn in: 26,28,32,34,36,38

M15-HW2_4solns

2.5: Turn in: 20, 22,24,28,30

M15-HW2_5solns

2.6:Turn in: 20,22,24,26,28,30

M15-HW2_6solns

27-Feb 4 2.3: Functions Domain, codomain, one-to-one, onto, composition, inverse,f-graphs, r-graphs,directed,undirected graphs, 2.3: Turn in: 18,20,28,30,32,36

M15-HW2_3solns

20-Feb 3 2.1: Graphs

2.2: Sets

DSP: 1.2 Truth Values and FunctionsGraphs, TkGate (from Discrete Structures with Python, "aka DSP")

2.1: do 2-20 even

Turn in: 22-28 even

M15-HW2_12.2: do 2-24 even

Turn in: 26-32 even

M15-HW2_2solns13-Feb 2 1.4: Logic in Mathematics

1.5: Methods of Proof

MMLogic and CodePlex

Logic Circuits and Boolean Algebra

by Clive MaxfieldAxiomatic systems, direct proof vs. proof by contradiction orcontraposition

APowerfulMethodofNonproof1.5: do 1-24, even, but don't turn in

To turn in 2/13:

1.4: 22-30 even

To Turn in 2/15: 1.5: 20,22,24 M15-HW1_5solns6-Feb

1 1.1: Formal Logic

1.2: Propositional Logic

1.3: Predicate Logic

The Penn predicate logic calculator

Lambda calculatorConnectives, propositions, truth tables, equivalences, tautologies, contradictions, derivations, proofs, forward/backward, predicates, quantifiers, translations, negations, constructions, definitions, statements, counterexamples.

1.1: 2, 6, 8, 10, 12, 16, 18, 22, 24, 26, 30, 32

1.2: 2, 6, 8, 10, 12, 14, 16, 18, 20, 22, 26

1.3: 12 -- 24 evenSOL'NS for 1.1-1.2

SOL'NS for 1.3-1.4Get started learning Python with codeacademy.com

and install Jupyter Notebook.

30-Jan