COT 3100: Applications of Discrete Structures, Spring 2012

COT 3100 Applications of Discrete Structures. Credits: 3; Prereq: MAC 2233, MAC 2311 or MAC 3472; Coreq: CIS 3020 or CIS 3023. 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) (MR)

Discrete Mathematics is to computer science as words and grammar are to English. Solving a problem in computer science without discrete math is like writing a novel with garbled grammar or a confusing plot. It just won't work. Your thinking will be muddled, and your code just won't work. Worse yet, your code will likely have hidden bugs that won't be found until an end-user complains (or explodes ...). At that point, fixing the bug is costly, or even impossible.

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.

• click here for the e-Learning class page

• Lecture (all sections): MWF 6th period (12:50pm-1:40pm) in McCarty A, room G186.
• Discussion sections:
  • 1088: Wed 9th period (4:05pm-4:55pm), in CSE E220
  • 3761: Thurs 6th period (12:50pm-1:40pm), in Turlington 2305
  • 3751: Thurs 7th period (1:55pm-2:45pm), in Pugh 120

My professional and personal background.

Office: CSE E338
Phone: 352 505 1546
Email: davis@cise.ufl.edu or DrTimothyAldenDavis@gmail.com
Web site: http://www.cise.ufl.edu/~davis
Office hours: MWF after class, until 3pm

• David Nguyen
  email: dtnguyen at cise dot ufl dot edu.
  Leads the Wednesday discussion (9th period).
  Office hours: Wednesdays 10:40am to 12:45pm, in CSE E309.
• Leila
  email: leila at cise dot ufl dot edu.
  Leads the 6th period Thursday discussion.
  Office hours: Thursdays 9:35am to 11:30am in CSE E445.
• Thang Dinh
  email: tdinh at cise dot ufl dot edu.
  Leads the 7th period Thursday discussion.
  Office hours: Tuesdas 1:55pm to 3:55 in CSE E309.
• Inchul Choi
  email incul at cise dot ufl dot edu.
  Office hours: Fridays from 3pm to 6pm in CSE E309.

	Mon	Tues	Wed	Thurs	Fri
3rd (9:35am)	-	-	-	Kalantari (CSE E445)	-
4th (10:40am)	-	-	Nguyen (CSE E309)	Kalantari (CSE E445)	-
5th (11:45am)	-	-	Nguyen (CSE E309)	-	-
6th (12:50pm)	class (McCarty A G186)	-	class (McCarty A G186)	discussion (Turl 2305)	class (McCarty A G186)
7th (1:55pm)	Davis (CSE E338)	Dinh (CSE E309)	Davis (CSE E338)	discussion (Pugh 120)	Davis (CSE E338)
8th (3pm)	-	Dinh (CSE E309)	-	-	Choi (CSE E309)
9th (4:05pm)	-	-	discussion (CSE E220)	-	Choi (CSE E309)
10th (5:10pm)	-	-	-	-	Choi (CSE E309)

The CISE Academic Tutoring Center provides tutors for COT 3100.
Time: Sunday: 3-6pm, Monday-Wednesday-Friday: 1-8pm, and Tuesday-Thursday: 12-8pm. Location: CSE E201. Note that you must bring your own textbook or course material.

• 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.

• I will be taking photos of all students in the class, so I can more easily learn your names.
• The use of laptops is stricly prohibited in class.
• You must attend the discussion section you are registered for. Taking the wrong quiz is worth zero points.
• The use of bootleg copies of the textbooks is strictly prohibited. Using bootleg books is theft, and failure to follow this policy will result in expulsion from the class.
• update: No International Edition of the book may be used. It is not the same as the US Edition.
• You must observe the Student Honor Code and Student Conduct Code

• Weekly quizzes: These will given during the Wednesday / Thursday discussion sections. They will cover the same topics as the homework that was due the previous Monday. Each discussion section will have a different quiz. You may drop one quiz. Quizzes will be curved to normalize between sections. Quizzes account for 15% of your grade.
• Weekly homework: These will typically be due each Monday, via e-Learning just before class. Solutions will be posted Monday after class so that you will have plenty of time to review them before the quiz on the same topic later that week. Homework accounts for 10% of your grade. You are strictly permitted and even encouraged to work together on homeworks. If you do that, you may even turn in a single homework with each of your names on it. If you work together on part of the homework but not all, then include a statement on the first page ("problems 1, 3, and 5 were done in collaboration with ... (name here) ...").
• Three in-class exams: February 3, March 2, and April 9, in the regular classroom. Be aware that March 2nd is the Friday before spring break (sorry, that's where the monthly sequence landed). Exams may be curved, as needed. Each exam accounts for 18.75% of your grade.
• Final exam: Thursday, May 3, from 12:30pm to 2:30pm, in the regular classroom (McCarty A, room G186). The final exam accounts for 18.75% 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). No rescheduling for quizzes unless you get my permission first.

Topics in the book in grey (like this) will not be covered. These greyed-out sections do not appear in the coursepack or e-book.

• 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. We will cover sections 2.1 to 2.4 and 2.6 very quickly, since most of it should be a review. Section 2.5 will likely be new to you and we will cover it at a normal pace.
  • 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
  • 10.1 Introduction to Trees
  • 10.2 Applications of Trees
  • 10.3 Tree Traversal
  • 10.4 Spanning Trees
  • 10.5 Minimum Spanning Trees

• 12 Boolean Algebra

• 13 Modeling Computation

Grade distribution:

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.