COT3100: APPLICATIONS OF DISCRETE STRUCTURES | ||
| Term: Fall 2012
| ||
| Time: MWF period 8 (3:00pm-3:50pm) | ||
| Location: PUGH 170 | ||
| Catalogue number: 1096, 1097 | ||
| Discussion session: W period 7 CSE E121 (1096), W period 9 CSE E222 (1097) | ||
| Textbook: Discrete Mathematics and Its Applications, Kenneth Rosen, 7th edition | ||
| Instructor: Nam Nguyen, CSE E555, (nanguyen@cise.ufl.edu) |
| Teaching Assistants: | + Sile Hu, CSE309, (sihu@cise.ufl.edu), leading discussion sessions 1096, 1097. |
| + Yuanwen Huang, CSE309, (yuanwen@cise.ufl.edu) | |
| + Subhankar Mishra, CSE309, (mishra@cise.ufl.edu) |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Syllabus | Announcements | Schedule |
| Date | Lecture Topic | Assignments |
| Aug 22 |
Introduction, Syllabus,
Course structure. | |
| Aug 24 |
Propositional Logic
- 1.1 propositions, connectors, conditional statements, truth tables, converse, contrapositive, inverse, precedence | |
| Aug 27 |
Propositional Equivalences
- 1.3
tautology, contradiction, logically equivalent, De Morgan's Laws | |
| Aug 29 | Predicates and Quantifiers - 1.4 propositional function, universal and existential quantifiers, counterexample | |
| Aug 31 | Predicates and Quantifiers - 1.4
(cont.) propositional function, universal and existential quantifiers, counterexample | |
| Sep 3 - Labor day (no classes) | ||
| Sep 5 | Nested Quantifiers - 1.5
order of quantifiers, programming loops, translations, negations |
|
| Sep 07 | Rules of Inference- 1.6 valid arguments, fallacies, modus ponens, modus tollens, hypothetical syllogism disjunctive syllogism, simplification, addition, conjunction, resolution | |
| Sep 10 | Rules of Inference- 1.6 (cont.) valid arguments, fallacies, modus ponens, modus tollens, hypothetical syllogism disjunctive syllogism, simplification, addition, conjunction, resolution | |
| Sep 12 | Introduction to Proofs - 1.7 theorem, lemma, corollary, conjecture, proof strategies (direct, vacuous, trivial, by contraposition, by contradiction, by case, by counterexample) | |
| Sep 14 | Proof Methods
- 1.8 contradiction vs. contraposition, equivalance proofs, existence, constructive, nonconstructive, uniqueness | |
| Sep 17 | Proof Methods
- 1.8 (cont.) contradiction vs. contraposition, equivalance proofs, existence, constructive, nonconstructive, uniqueness |
|
| Sep 19 | Sets - 2.1 sets, universal set, empty set, subset, proper subset, powerset ordered pairs, Cartesian product, quantifiers and sets, union, intersection, complement, difference, symmetric difference | |
| Sep 21 | Sets - 2.1 (cont.) | |
| Sep 24 | Set Operations - 2.2 union, intersection, complement, difference, symmetric difference | HW2 due Solution |
| Sep 26 | Set Operations
- 2.2 (cont.) DeMorgan's law, Venn diagram, proving set relations |
|
| Sep 28 | Review for Midterm 1 | Quiz 4 |
| Oct 1 | MIDTERM EXAM 1 Solution | |
| Oct 3 |
Functions - 2.3 domain, codomain, range, image, preimage, mapping, transformation one-to-one (injection), onto (surjection), one-to-one correspondence (bijection) | |
| Oct 5 | Sequences and Summations - 2.4 | |
| Oct 8 | Cardinality of Sets - 2.5 | Solution |
| Oct 10 | Matrices - 2.6 | |
| Oct 12 |
Algorithms
- 3.1 searching, sorting, halting problem, linear search, binary search bubblesort, insertionsort, mergesort | |
| Oct 15 | The Growth of Functions - 3.2 Turing's theorem on halting problem, Big-Oh notation | HW4 |
| Oct 17 | The Growth of Functions (cont.)
Big-Oh or not Big-Oh, Big-Omega and Big-Theta notation upper bound vs. lower bound | |
| Oct 19 | Complexity of Algorithms
- 3.3 time vs. space complexity, worst-case complexity, average-case complexity analysis of bubble sort, linear search, binary search, and matrix multiplication constant-time, linear-time, logarithmic-time, quadratic-time algorithms | |
| Oct 22 | Complexity of Algorithms
- 3.3 time vs. space complexity, worst-case complexity, average-case complexity analysis of bubble sort, linear search, binary search, and matrix multiplication constant-time, linear-time, logarithmic-time, quadratic-time algorithms | |
| Oct 24 | Mathematical Induction
- 5.1 principle of mathematical induction, basis step, inductive step, inductive hypothesis |
HW4 due Solution |
| Oct 26 | Mathematical Induction (cont.) divisibility proof by induction, well-ordering property validity of the principle of mathematical induction, errors in proofs by induction |
|
| Oct 29 | Strong Induction
- 5.2 second principle of mathematical induction, strong induction, product of primes computational geometry and induction |
HW5 |
| Oct 31 | Recursive Definitions
- 5.3 recursive functions, factorial, recursive sequences; Fibonacci numbers recursive set definitions; recursion and induction | |
| Nov 2 | Recursive Algorithms
- 5.4 iterative vs. recursive algorithms, proof of algorithm correctness comparison of time complexity of iterative and recursive algorithms | |
| Nov 5 | Review of Chapters 2, 3, 5 | Solution |
| Nov 7 | MIDTERM EXAM 2 Solution |
|
| Nov 9 - UF Homecoming (no classes) | ||
| Nov 12 - Veterans Day (no classes) | ||
| Nov 14 | The Basics of Counting
- 6.1 counting problems, the sum rule, the product rule, inclusion-exclusion principle | |
| Nov 16 | The Basics of Counting (cont.) tree diagrams | Quiz 9 |
| Nov 19 | The Piegonhole Principle
- 6.2 the generalized pigeonhole principle | |
| Nov 21 - 23 - Thanksgiving (no classes) | Nov 26 | The Piegonhole Principle
- 6.2 (cont'd) the generalized pigeonhole principle | |
| Nov 28 | Permutations and Combination - 6.3 | |
| Nov 30 | Binomial Coefficient and Identities - 6.4 | |
| Dec 3 | Graphs, Graph Models, and Terminology
- 10.1 | Solution |
| Dec 5 | Review for final exam |
Final review |
| Dec 12 | FINAL EXAM (Group 12E) Time: 05:30pm-07:30pm, Room: PUGH 170 |
|
| Syllabus | Announcements | Schedule |