Math 302- Discrete Mathematics
Files
Below, please find links to helpful files, including the syllabus of the course. Links Below, please find other helpful links.
Announcements
Lecture 11/14 Second Midterm Lecture 11/07 Section 8.2: Solving recurrences: Review of how to solve linear homogeneous recurrence of degree k with constant coefficients. Linear non-homogeneous recurrence relations with constant coefficientes: associated homogeneous recurrence relation, particular and general solutions for the non-homogeneous recurrence. Example. Formula for solutions of linear non-homogeneous recurrece relations with constant coefficients with non-homogeneous term given by a polynomial times an exponential function. Section 8.3: Divide and conquer algorithms and recurrence relations: definition, example (binary search), complexity. Re-schedule of extra office hours for the second midterm Monday Nov 13, 10 am to 11 pm at Blocker 510A, and Monday Nov 13, 3:30 to 4:30 pm at Blocker 510A Extra office hours for the second midterm Monday Nov 13, 9 am to 11 pm at Blocker 510A Lecture 11/07 Quiz 8. Section 8.2: Solving recurrences: Review of Fibonacci (finding the formula), formula for linear homogeneous recurrence of degree k with constant coefficients. Characteristic equation of the recurrence: distinct roots vs roots with multiplicities. Solutions and approach to both cases. Examples Lecture 11/02 Section 5.3: Full binary trees: use of structural induction to prove relation between number of vertices and height. Section 8.1: Modeling recurrences: Fibonacci (using rabbits), Towers of Hanoi, Parenthesis to specify the order of the product. Homework: example of dynamic programming. Section 8.2: Solving Fibonacci. Lecture 10/31 Quiz 7. Section 5.3: Recursive definition of functions. Proof using strong induction of bound for Fibonacci numbers. Recursive definition of sets. Structural induction: examples, validtiom of the method, examples. Full binary trees: definition, examples, height and number of vertices. Lecture 10/26 Section 5.1: More examples of proofs using mathematical induction. Section 5.2: Strong mathematical induction: definition, examples of proofs using strong mathematical induction. Section 5.3: Recursive definition of functions, examples. Lecture 10/24 Quiz 6. Section 5.1: Mathematical induction: intuition, definition. Why mathematical induction works? For-loop idea. Proof using Well-ordering property. Examples of proofs using mathematical induction. Lecture 10/19 Comments about the first midterm. Section 2.5: Review of cardinality of sets. A subset of a countable set is countable. If a set has an uncountable subset then is uncontable. Real numbers are uncountable (Cantor's Diagonalization Argument). Bernstein-SchrÃ¶der's Theorem. Continuum hypothesis. Section 5.1: Mathematical induction: intuition, definition. Lecture 10/17 First Midterm Lecture 10/12 Quiz 5. Section 3.3: Worst case complexity: bubble sort vs insertion sort. Section 2.5: Cardinality of sets: definition. Countable set: definition and examples. Integer numbers and natural numbers are countable. The union of two countable sets is countable. Lecture 10/10 Section 2.4: Sequence: definition, examples. Geometric and arithmetic progression. Finite sequences. Recurrence relation: definition and examples.Finding formulas: examples. Summation: notation, examples. Formula for geoemtric series. Lecture 10/05 Quiz 4. Section 1.7: More examples of proofs. Common mistakes. Section 1.8: Proof methods and strategy. Proof by cases. Existence proofs: constructive vs non constructive. Examples. Lecture 10/03 Section 1.6: Review of the concepts introduced in the previous class: definitions, examples, and tautologies. Fallacies: of affirming the conclusion, of denying the hypothesis. Rules of inference for quantified statements: universal instantiation, universal generalization, existential instantiation, existential generalization. Combining different types of rules of inference: universal modus ponens, universal modus tollens Section 1.7: Intro to proofs: direct proof, prove the contrapositive, proof by contradiction. Examples of each type of proofs. Proofs of equivalence. Countrexamples. Common mistakes. Lecture 09/28 Quiz 3. Section 1.5: Nested quantifiers: examples, negation. Section 1.6: Rules of inference: Argument, valid argument, argument form. Modus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism, addition, simplification, conjunction, resolution. . Lecture 09/26 Section 1.3: Satisfiable and unsatisfiable propositions. Examples. Section 1.4: Predicate, Quantifiers: definition and examples. Universal and existencial quantifiers. Uniqueness quiantifier. Examples. Negation of quantifiers Lecture 09/21 Quiz 2. Section 1.1: Proposition, negation, conjunction, disjunction, inclusive vs. exclusive or, conditional: definitions, truth tables, examples. Converse, contrapositive, inverse, biconditiona: examples, truth table. Section 1.3: Tautology, contradiction. Logically equivalent. Laws: identity, domination, idempotent, double negation, commutativity, associativity, distributivity, De Morgan, absorption, negation. Examples. Lecture 09/19 Section 3.2: Growth of functions: review of big O notation and examples. More examples (n!, log(n!), log(n), among others) and techniques to compute big O. Big O of the sum and product of functions. Big omega and Big theta notation and examples. Big theta for a plynomial. Lecture 09/14 Quiz 1. Section 3.1: Review of Greedy Change-Making algorithm: proof of being optimal for quarters, dimes, nickels, and pennies. Section 3.2: Growth of functions: definition of big O notation and examples. Review of triangular inequality and other properties of absolute value and inequalities. Big O for a polynomial. Lecture 09/12 Section 3.1: Review of definition and properties of algorithms. Search algorithms: linear search (review) and binary search: pseudocode and discussion. Sorting algorithms: bubble sort and insetion sort. Examples and pseudocodes for both sorting methods. Greedy Change-Making algorithm: discussion, pseudocode, remarks and examples. Lecture 09/07 Section 2.3: Functions: domain, codomain, image. Examples. Sum and product of function. Injective, onto, and bijective functions. Examples and proofs. Inverse function. Floor and ceiling funtcions. Section 3.1: Definition and properties of algorithms. Search algorithms: linear search (pseudocode and discussion) and binary search (example). Lecture 09/05 Section 2.2: Set operations: union, intersection. Disjoint set. Set difference, complement of a set. Examples. Membership table. Collection of sets. Section 2.3: Functions. Lecture 08/31 Section 2.1: Sets: definition and examples. Description of sets: roaster method, set builder notation. Empty set and universe. Subsets: definition and examples. Finite and infinite sets; cardinality. Constructions of new sets from given ones: power set, cartesian product. |