COT3100: APPLICATIONS OF DISCRETE STRUCTURES

Announcements

Catalog Description COT 3100 Applications of Discrete Structures. Credits: 3; Prereq: MAC 2233, MAC 2311 or MAC 3472; Coreq: COP 3504 or COP 3503. Covers the mathematics of discrete events, i.e., events that involve distinct elements, finite structures of distinct elements, or finite sampled versions of continuous phenomena (such as movement). (M) Course Overview This course teaches you the fundamentals of logic, proof techniques, induction/recursion, counting, advanced counting (not as easy as it sounds!), relations, and graph theory. These mathematical tools are essential to doing and understanding computer science / computer engineering. The primary emphasis of the course is mathematical reasoning and problem solving. Equipping you with specific skills (such as tools for solving recurrence relations) is important, but only a secondary goal of this course. You won't find many plug-and-chug type of problems to solve. Many of the problems will require original thought, instead. This is true for the homeworks, quizzes, and exams. CISE Academic Tutoring Center: The CISE Academic Tutoring Center provides tutors for COT 3100. Books: click here for textbook details Required: Discrete Mathematics and its Applications, Rosen, 7th Edition, McGraw-Hill, 2012. The book sells for $159 at amazon.com. You may also use a less expensive course pack from McGraw-Hill (paper: ISBN 9781121362352 for $96.08, or eBook: ISBN 9781121353052 for $75.16). Recommended: Student Solutions Guide, Rosen, 7th Edition. Policies: You must attend the discussion section you are registered for. You must observe the Student Honor Code and Student Conduct Code Grading: Quizzes: There will be occasional quizzes on recently covered material. The quizzes will be announced two days in advanced. There will be no make up for quizzes. Quizzes account for 30% of your grade. Frequent Homeworks: You are not required to submit them as they won't be graded. You are strictly permitted and even encouraged to work together on homeworks. Two in-class exams: February 11 Wednesday , March 18 Wednesday, in the regular classroom. Exams may be curved, as needed. Each exam accounts for 20% of your grade. Final exam: Date and Location to be announced. The final exam will be comprehensive and accounts for 30% of your grade. Grading scale 90 or higher: A 87: A- 83: B+ 80: B 77: B- 73: C+ 70: C 67: C- 63: D+ 60: D 57: D- less than 57: E No rescheduling permitted for exams (unless you get a letter from a doctor or from the Dean's office). Outline of topics : We will try to cover most of the topics in the textbook. Topics in the book in grey (like this) will not likely be covered. 1 The Foundations: Logic and Proofs 1.1 Propositional Logic 1.2 Applicationcs of Propositional Logic 1.3 Propositional Equivalences 1.4 Predicates and Quantifiers 1.5 Nested Quantifiers 1.6 Rules of Inference 1.7 Introduction to Proofs 1.8 Proof Methods and Strategy 2 Basic Structures: Sets, Functions, Sequences, Sums, and Matrices. 2.1 Sets 2.2 Set Operations 2.3 Functions 2.4 Sequences and Summations 2.5 Cardinality of Sets 2.6 Matrices 3 Algorithms 3.1 Algorithms 3.2 The Growth of Functions 3.3 Complexity of Algorithms 4 Number theory and cryptography 4.1 Divisibilty and Modular Arithmetic 4.2 Integer Representation and Algorithms 4.3 Primes and Greatest Common Divisor 4.4 Solving Congruences 4.5 Applications of Congruences 4.6 Cryptography 5 Induction and Recursion 5.1 Mathematical Induction 5.2 Strong Induction and Well-Ordering 5.3 Recursive Definitions and Structural Induction 5.4 Recursive Algorithms 5.5 Program Correctness 6 Counting 6.1 The Basics of Counting 6.2 The Pigeonhole Principle 6.3 Permutations and Combinations 6.4 Binomial Coefficients and Identities 6.5 Generalized Permutations and Combinations 6.6 Generating Permutations and Combinations 7 Discrete Probability 7.1 An Introduction to Discrete Probability 7.2 Probability Theory 7.3 Bayes' Theorem 7.4 Expected Value and Variance 8 Advanced Counting Techniques 8.1 Applications of Recurrence Relations 8.2 Solving Linear Recurrence Relations 8.3 Divide-and-Conquer Algorithms and Recurrence Relations 8.4 Generating Functions 8.5 Inclusion-Exclusion 8.6 Applications of Inclusion-Exclusion 9 Relations 9.1 Relations and Their Properties 9.2 n-ary Relations and Their Applications 9.3 Representing Relations 9.4 Closures of Relations 9.5 Equivalence Relations 9.6 Partial Orderings 10 Graphs 10.1 Graphs and Graph Models 10.2 Graph Terminology and Special Types of Graphs 10.3 Representing Graphs and Graph Isomorphism 10.4 Connectivity 10.5 Euler and Hamilton Paths 10.6 Shortest-Path Problems 10.7 Planar Graphs 10.8 Graph Coloring 11 Trees 11.1 Introduction to Trees 11.2 Applications of Trees 11.3 Tree Traversal 11.4 Spanning Trees 11.5 Minimum Spanning Trees Standard UF policies for all courses: A C- will not be a qualifying grade for critical tracking courses. In order to graduate, students must have an overall GPA and an upper-division GPA of 2.0 or better (C or better). Note: a C- average is equivalent to a GPA of 1.67, and therefore, it does not satisfy this graduation requirement. For more information on grades and grading policies, click here. 1. Honesty Policy - All students admitted to the University of Florida have signed a statement of academic honesty committing themselves to be honest in all academic work and understanding that failure to comply with this commitment will result in disciplinary action. This statement is a reminder to uphold your obligation as a UF student and to be honest in all work submitted and exams taken in this course and all others. 2. Accommodation for Students with Disabilities - Students Requesting classroom accommodation must first register with the Dean of Students Office. That office will provide the student with documentation that he/she must provide to the course instructor when requesting accommodation. 3. UF Counseling Services - Resources are available on-campus for students having personal problems or lacking clear career and academic goals. The resources include: University Counseling Center, 301 Peabody Hall, 392-1575, Personal and Career Counseling. SHCC mental Health, Student Health Care Center, 392-1171, Personal and Counseling. Center for Sexual Assault/Abuse Recovery and Education (CARE), Student Health Care Center, 392-1161, sexual assault counseling. Career Resource Center, Reitz Union, 392-1601, career development assistance and counseling. 4. Software Use - All faculty, staff and student of the University are required and expected to obey the laws and legal agreements governing software use. Failure to do so can lead to monetary damages and/or criminal penalties for the individual violator. Because such violations are also against University policies and rules, disciplinary action will be taken as appropriate. We, the members of the University of Florida community, pledge to uphold ourselves and our peers to the highest standards of honesty and integrity.