|
|
COT3100: APPLICATIONS OF DISCRETE STRUCTURES | ||
| Term: Spring 2007
| ||
| Time: MWF 11:45am-12:35pm | ||
| Location: TURL005 | ||
| Catalogue number: 1088, 3751, 3761, 4617 | ||
| Professor: Alper �g�, CSE430, (ungor@cise.ufl.edu) |
| Teaching Assistants: | Hale Erten, CSE309, (herten@cise.ufl.edu) |
| Ajit Rajwade, CSE309, (avr@cise.ufl.edu) | |
| Jyungryun Seo, CSE309, (jseo@cise.ufl.edu), | |
| Brian Weinrich, CSE309, (brianew@cise.ufl.edu) |
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| syllabus | announcements | schedule | courseworx | references |
| Date | Lecture Topic | Assignments |
| Jan 8 M |
Introduction, Syllabus,
Course structure. | |
| LOGIC and PROOFS | ||
| Jan 10 W |
Propositional Logic
[R06 1.1] propositions, connectors, conditional statements, truth tables, converse, contrapositive, inverse, precedence | |
| Jan 12 F |
Propositional Equivalences
[R06 1.2] tautology, contradiction, logically equivalent, De Morgan's Laws | Hw1 out |
| Jan 15 M | MLK Day (no classes) | |
| Jan 17 W | Predicates and Quantifiers
[R06 1.3] propositional function, universal and existential quantifiers, counterexample | Quiz 1 |
| Jan 19 F | Nested Quantifiers [R06 1.4] order of quantifiers, programming loops, translations, negations | HW1 due Quiz1 graded Hw2 out |
| Jan 22 M | Rules of Inference [R06 1.5] valid arguments, fallacies, modus ponens, modus tollens, hypothetical syllogism disjunctive syllogism, simplification, addition, conjunction, resolution, fallacy of affirming the conclusion, fallacy of denying the hypothesis universal instantiation and generalization, existential instantiation and generalization universal modus ponens, universal modus tollens | |
| Jan 24 W | Introduction to Proofs [R06 1.6] theorem, lemma, corollary, conjecture, proof strategies (direct, vacuous, trivial, by contraposition, by contradiction, by case, by counterexample) | Quiz 2 |
| Jan 26 F | Proof Methods
[R06 1.6-1.7] contradiction vs. contraposition, equivalance proofs existence, constructive, nonconstructive, uniqueness | HW2 due Quiz2 graded Hw3 out |
| Jan 29 M | Proof Strategies
[R06 1.7] without loss of generality, forward vs. backward reasoning, errors in proofs | |
| Jan 31 W | Recap Logic and Proofs
[R06 1.7] adapting existing proofs, tilings, Fermat's last theorem, 3x+1 conjecture | Quiz 3 |
| SETS, FUNCTIONS, SEQUENCES | ||
| Feb 2 F | Sets and Set operations
[R06 2.1-2.2] sets, universal set, empty set, subset, proper subset, powerset ordered pairs, Cartesian product, quantifiers and sets, union, intersection, complement, difference, symmetric difference | HW3 due Quiz 3 graded Hw4 out |
| Feb 5 M | Set Operations (cont.)
[R06 2.2] DeMorgan's law, Venn diagram, proving set relations | |
| Feb 7 W | Functions
[R06 2.3] domain, codomain, range, image, preimage, mapping, transformation one-to-one (injection), onto (surjection), one-to-one correspondence (bijection) |
Hw5 out Quiz 4 Hw4 graded |
| Feb 9 F | Functions (cont.)
[R06 2.3] inverse functions, composite functions | Hw4 due Quiz 4 graded |
| Feb 12 M | Sequences and Summations
[R06 2.4] sequence definition, geometric & arithmetic progressions, useful sequences summation notation: index, lower and upper limit, useful summation formulae cardinality & bijection, countable sets, uncountable sets, Cantor diagonalization argument | |
| ALGORITHMS and INTEGERS | ||
| Feb 14 W | Algorithms
[R06 3.1] searching, sorting, halting problem, linear search, binary search bubblesort, insertionsort, mergesort | Hw5 due Hw4 graded |
| Feb 16 F | MIDTERM EXAM I | |
| Feb 19 M | Algorithms (cont.)
[R06 3.1] selectionsort, algorithmic problems on sequences, change dispenser problem greedy algorithms, proof of correctness | Hw5 graded Hw6 out |
| Feb 21 W | The Growth of Functions
[R06 3.2] Turing's theorem on halting problem, Big-Oh notation | Exam I graded |
| Feb 23 F | The Growth of Functions (cont.)
[R06 3.2] Big-Oh or not Big-Oh, Big-Omega and Big-Theta notation upper bound vs. lower bound | Hw6 due Hw7 out Quiz 5 |
| Feb 26 M | Complexity of Algorithms
[R06 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 | Quiz5 graded |
| INDUCTION and RECURSION | ||
| Feb 28 W | Mathematical Induction
[R06 4.1] principle of mathematical induction, basis step, inductive step, inductive hypothesis | Hw6 graded |
| Mar 2 F | Mathematical Induction (cont.)
[R06 4.1] divisibility proof by induction, well-ordering property validity of the principle of mathematical induction, errors in proofs by induction | Hw7 due Hw8 out Quiz 6 |
| Mar 5 M | Strong Induction
[R06 4.2] second principle of mathematical induction, strong induction, product of primes computational geometry and induction | |
| Mar 7 W | Recursive Definitions
[R06 4.3] recursive functions, factorial, recursive sequences; Fibonacci numbers recursive set definitions; recursion and induction | |
| Mar 9 F | Recursive Algorithms
[R06 4.4] iterative vs. recursive algorithms, proof of algorithm correctness comparison of time complexity of iterative and recursive algorithms | Hw8 due Quiz 7 |
| Mar 12 M | SPRING BREAK | |
| Mar 14 W | ||
| Mar 16 F | ||
| COUNTING | ||
| Mar 19 M | The Basics of Counting
[R06 5.1] counting problems, the sum rule, the product rule, inclusion-exclusion principle |
Hw9 out |
| Mar 21 W | The Basics of Counting (cont.)
[R06 5.1] tree diagrams | |
| Mar 23 F | The Piegonhole Principle
[R06 5.2] the generalized pigeonhole principle | Quiz 8 HW9 due Hw10 out |
| Mar 26 M | The Pigeonhole Principle (cont.)
[R06 5.2] aplications of the counting rules and the pigeonhole principle | |
| Mar 28 W | Review of Chapters 3,4,5 | Hw10 due |
| Mar 30 F | MIDTERM EXAM II | |
| Apr 2 M | Introduction to Probability
[R06 6.1] and
[R06 6.2] finite probability, sample space, combination of events complementary event independence, birthday problem use of counting in probability | |
| RELATIONS | ||
| Apr 4 W | Relations and Their Properties
[R06 8.1] binary relations, n-ary relations, functions as relations, relations on a set properties of relations, reflexive, symmetric, antisymmetric, transitive combining relations, composite of two relations, powers of a relation |
Hw11 out |
| Apr 6 F | Representing Relations
[R06 8.3] and [R06 3.8] directed graphs (digraphs), vertices, edges, initial vertex, terminal vertex, loop | |
| Apr 9 M | Representing Relations (cont.)
[R06 8.3] and [R06 3.8] matrices, matrix operations, addition, join, meet, matrix multiplication Boolean matrices, Boolean product, matrix representations of relations | Hw11 due Quiz9 |
| GRAPHS | ||
| Apr 11 W | Graphs, Graph Models, and Terminology
[R06 9.1] and
[R06 9.2] undirected graphs, simple graphs, multiple edges, loops, multigraphs, mixed graphs internet graph, roadmap graphs, adjacent, incident, connected, degree, handshaking theorem | Quiz9 graded Hw12 out |
| Apr 13 F | Graph Terminology and Special Types of Graphs
[R06 9.2] degree summation, directed edges, initial vertex, terminal vertex, in-degree, out-degree complete graphs (cliques), cycles, wheels, n-cubes | |
| Apr 16 M | Special Types of Graphs, Representing Graphs
[R06 9.2] and
[R06 9.3] bipartite graphs, graph coloring, 2-coloring of bipartite graphs adjacency list, matrix representation | Hw12 due Quiz 10 |
| Apr 18 W | Graph Isomorphism
[R06 9.3] review of pigeonhole principle and graph vertex degree, subgraphs, isomorphism | Quiz10 graded Hw13 out |
| Apr 20 F | Paths and Connectivity
[R06 9.4] path, simple path, connected components, isomorphism and paths | Hw12 graded |
| Apr 23 M | Paths and Connectivity (cont.), Planar Graphs
[R06 9.4] and
[R06 9.7] counting the paths, applying matrix product, planar graphs, Euler's formula Nineteen proofs of Euler's formula | Hw13 due Quiz 11 |
| Apr 25 W | Planar Graphs and Coloring
[R06 9.7] and
[R06 9.8] coloring, chromatic number, coloring geographic maps, scheduling and coloring four color theorem, coloring cliques, examples of non-planar graphs 6-coloring algorithm and proof | Quiz 10 graded Hw13 graded |
| May 3 Th | FINAL EXAM (12:30pm-2:30pm) (in the classroom TURL005) | |
BooksLinks
[R06] K.~Rosen. Discrete Mathematics and its Applications, 6th Edition, McGraw-Hill, 2006.
[LL04] Lecture Notes by Lehman and Leighton
| syllabus | announcements | schedule | courseworx | references |
Alper �g�
(ungor@cise.ufl.edu)
Jan 2007