Math 302- Discrete Mathematics
Below, please find links to helpful files, including the syllabus of the course.
Below, please find other helpful links.
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
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
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. .
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
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.
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.
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.
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.
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).
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.
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.