Discrete Structures - Spring, 2017

map syllabus grades
pytree

Calendar—Spring 2017

Week Readings Topics Assignments
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.

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 even

SOL'NS for 1.1-1.2
SOL'NS for 1.3-1.4

Get started learning Python with codeacademy.com
and install Jupyter Notebook.

30-Jan