Discrete Structures - Spring, 2017

# Calendar—Spring 2017

 Week Readings Topics Assignments 16 Review M15-Final 22-May 15 Review Turn in your work before the solutions are published!@~ To be sure the above comment pertained to the homework problems, not this set of practice problems: Math15_Test02 Math15_Test02solns 15-May 14 5.4: Bounds on Complexity 5.5: Program Verification 5.6: Loop Invariants P vs. NP, Verification vs. Testing, Verifying Recursive Algos, Seartching and Sorthing, Towers of Hanoi, Verifying iterative algos, Using invariants to design algos To turn in: 5.4: 18, 20, 22 M15-HW5_4solns 5.5: 18, 20, 22, 24 M15-HW5_5solns 5.6: 14-22 even M15-HW5_6solns 8-May 13 5.2: Three Common Types of Algos 5.3: Algorithmic Complexity 5.4: Bounds on Complexity Traversal algos, greedy algos, Divide and Conquer algos, Algorithmic Complexity, The Good the Bad and the Average, Approximate Complexity Computations, Algorithms as decisions, A Lower Bound, Searching an Array, Sorting, P vs. NP To turn in: 5.2: 16, 20, 24 M15-HW5_2solns 5.3: 18, 20, 22 M15-HW5_3solns Project Progress Report. 1-May 12 4.6: Estimation 5.1: Algorithms Growth of function, estimation targets, Properties of Big-O, Pseudocode, Precondition and postcondition, iterative algos, Functions and recursive algos To turn in: 4.6: 24,28, 32 M15-HW4_6solns 5.1: 18, 22, 24 M15-HW5_1solns 24-Apr 11 4.4: Discrete Probability 4.5: Counting Operations in Algorithms Pr(X) = |A|/|U|, Expected Value, Algorithms, Pseudocode, Loops, Arrays, Sorting To turn in: 4.4: 22,24,26 M15-HW4_4solns 4.5: 24, 28, 30 M15-HW4_5solns 17-Apr Spring Research M15-S17-Project M15-C1_2TestSolutions Break! 10 4.1: Basic Counting Techniques 4.2: Selections and Arrangements 4.3: Counting with Functions 4.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 TheFourthWaytoSamplekObejctsfromaCollectionofnRamseyTheoryIsSharppdf To turn in: 4.1: 18--26, even M15-HW4_1solns 4.2: 18,20,24,28 M15-HW4_2solns 4.3: 24, 28, 30, 32 M15-HW4_3solns 3-Apr 9 3.4: Proof by Induction 3.5: Recursive Data Stuctures 3.4: Proof by Induction 3.5: Recursive Data Stuctures M15-C1_2Test To turn in: 3.4: 18, 22, 24 M15-HW3_4solns 3.5: 14-24,even M15-HW3_5solns 27-Mar 8 3.1, 3.2Closed Form Solutions and Induction 3.3: Recursive Definitions 3 .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 M15-HW3_3solns 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/#few Read Chapters 2 and 3 in Gopalakrishnan. 6-Mar 5 2.4: Relations and Equivalences 2.5: Partially Ordered Sets (posets) 2.6: Graph Theory equivalence 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 Functions Graphs, TkGate (from Discrete Structures with Python, "aka DSP") 2.1: do 2-20 even Turn in: 22-28 even M15-HW2_1 2.2: do 2-24 even Turn in: 26-32 even M15-HW2_2solns 13-Feb 2 1.4: Logic in Mathematics 1.5: Methods of Proof MMLogic and CodePlex Logic Circuits and Boolean Algebra by Clive Maxfield Axiomatic systems, direct proof vs. proof by contradiction orcontraposition APowerfulMethodofNonproof 1.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_5solns 6-Feb 1 1.1: Formal Logic 1.2: Propositional Logic 1.3: Predicate Logic The Penn predicate logic calculator Lambda calculator Connectives, propositions, truth tables, equivalences, tautologies, contradictions, derivations, proofs, forward/backward, predicates, quantifiers, translations, negations, constructions, definitions, statements, counterexamples. Get started learning Python with codeacademy.com and install Jupyter Notebook. 30-Jan