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
Extra office hours for the final Tuesday Dec 12, 2:30 pm to 4:30 pm at Blocker 510A Lecture 12/05 Section 8.5: Inclusion-Exclusion: formula, examples. Formula for a the number of elements in the union of three sets. Using the inclusion-exclusion principle to count the number of elements on the complement of a set. Section 9.1: Relations and their properties: definition, notation, examples. Functions as relations. Relations on a set: definition, examples. Properties of relations: relexive, symmetric, antisymmetric, and transtive. Examples. Combining relations. The composite of relations. The powers of a relation on a set. Transitivity of a relation in terms of the powers of the relation. Section 9.5: Equivalence relations: definition, examples. Lecture 11/30 Section 6.4: Pascal's Triangle identity. Other identities involving binomial coefficients. Section 6.5: Generalized Permutation and Combinations: permutations with repetinions, combinations with repretitions, permutations with indistinguishable objects. Note: It would be useful if you can read the last part of Section 6.5: Distributing objects into boxes (there are different cases: distinguishable objects and distinguidhable boxes, indistinguishable objects and distinguishable boxes, distinguishable objects and indistinguishable boxes, and indistinguishable objects and indistinguishable boxes). Lecture 11/28 Section 6.2: Pigeonhole Principle: more examples. Section 6.3: Permutations and Combinations: what they count? Definitions, formulas, examples. Section 6.4: Binomial Coefficients and Identities: Binomial Theorem and applications. Pascal's Triangle identity. Lecture 11/21 Section 6.1: More examples. Tree diagrams. Section 6.2: Pigeonhole Principle: statement, proof, examples. Generalized Pigeonhole Principle: statement, proof, examples. Lecture 11/16 Section 8.3: Divide and conquer algorithms and recurrence relations: example (merge sort), Master theorem (complexity). Section 6.1: Basic of counting: cardinality of the cartesian product, cardinality of the union (exlusion-inclusion). Examples. 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. |