COT 3100 Applications of Discrete Structures

Summer 2008

 Announcements   Homeworks   Lecture Schedule   Prize Problems   E-Learning system 

Credits: 3
Place: CSE Building, E220
Time: M W F 2 (9:30am - 10:45am)

Instructor:
Venkatakrishnan Ramaswamy
Office: CSE E522
Email: Venkat's email
Phone: TBA
Office hours: Monday 3 (11:00am - 12:15pm), Friday 7 (5:00pm - 6:15pm)

Teaching Assistant:
Xiaoke Qin
Office: CSE E309.
E-mail: xqin@cise.ufl.edu
Phone: 392-####.
Office hours: Tuesday 12:50-2:45pm, Thursday 12:50-2:45pm

Prerequisites: MAC 2233, MAC 2311 or MAC 3472.
Corequisite: CIS 3020 or CIS 3023.

Tentative list of topics to be covered: This is a tentative list, which might be adjusted due to time constraints or class interest.

Textbook: Discrete Mathematics and Its Applications, 6th Edition by Kenneth H. Rosen, McGraw-Hill, 2006. ISBN: 0072880082   errata.

Grading: The final grade will be on the curve.

Course policies:


Announcements

Please hit the REFRESH button of your browser to make sure you are not seeing an older cached version of this page.

Last modified: Wed Aug 6 15:26:52 2008

This is new08/09/2008: Exam3 solutions are now available via E-Learning.

This is new08/06/2008: Like the previous exams, Exam 3 will be closed-book, closed-notes. No calculators are allowed. A cheat sheet (one side, US letter size) is allowed. Material covered until the end of class today (i.e. till the end of Section 5.3) will be tested.

This is new08/05/2008: Quiz 4,5 and Homework5 grades are now available via E-Learning.

This is new08/05/2008: Quiz 6 solutions are now available via E-Learning.

This is new08/04/2008: Homework 6 solutions are now available via E-Learning.

This is new08/04/2008: As announced in class, there will be a quiz tomorrow during discussion.

07/30/2008: Homework 6 is now up.

07/30/2008: Venkat's office hours on Friday are advanced to 11:00am-12:15pm.

07/30/2008: Homework5 solution is available on e-learning.

07/28/2008: There will be a quiz tomorrow during discussion. Material covered so far in Chapter 4 will be tested.

07/25/2008: Homework 5 is now up.

07/22/2008: Exam2 and quiz3 grades are available on e-learning.

07/21/2008: There will be a quiz tomorrow during discussion. Material covered so far in Chapter 8 will be tested.

07/18/2008: Exam2 solutions are available on e-learning.

07/13/2008: Solutions to exercises have been up on the E-Learning system, since yesterday.

07/11/2008: Some exercises from Chapter 3 are now up. Solutions will be available tomorrow.

07/11/2008: Like Exam 1, Exam 2 will be closed-book, closed-notes. No calculators are allowed. A cheat sheet (one side, US letter size) is allowed. Material covered until the end of class today will be tested.

07/09/2008: There will be an in-class quiz on Friday. Material covered so far will be tested. In particular, see Examples 8,9 of Section 3.2 and try to prove that f(x) is O(g(x)) iff g(x) is Big Omega(f(x)).

07/09/2008: The Prize Problems may be solved for extra credit. Any extra credit you earn may be used to bump you up one letter grade if you are very close to the "border".

07/02/2008: Homework4 solution is available on e-learning.

06/30/2008: There will be an in-class quiz tomorrow during discussion.

06/30/2008: If you interpreted the last sentence of Q5 of the exam to mean ".. sum of (certain) positive integers..." as opposed to "... all positive integers ...", and lost points, please see the instructor or the TA. You will get full points on the question, if your solution is right based on either interpretation.

06/20/2008: Homework 4 is now up.

06/20/2008: Homework3 solution is available on e-learning.

06/18/2008: Exam1 grades and solutions are available on e-learning. You can pick up your exam paper during Xiaoke's office hours tomorrow.

06/13/2008: Homework 3 is now up.

06/11/2008: Xiaoke's office hours tomorrow are canceled.

06/09/2008: As previously announced, today's exam will be closed-book, closed-notes. No calculators are allowed. A cheat sheet (one side, US letter size) is allowed.

06/06/2008: The solution of "Exercises for 1.5-1.7" is available on e-learning.

06/05/2008: We don't have homework this week. But try to solve following exercises instead. You don't need to submit your solutions. Homework2 solution is available on e-learning.

05/28/2008: Homework 2 is now up. Homework1 solution is available on e-learning->CourseContent->HW solutions.

05/23/2008: Tuesday, May 27 is not holiday. We will have normal discuss section.

05/23/2008: There will be an in-class quiz on Wednesday, May 28. Material covered so far will be tested.

05/21/2008: Homework 1 is now up.

05/19/2008: The three exams will be held in MAT 51 from 8:20pm to 10:10pm on 6/9, 7/14, and 8/8.

05/14/2008: The department is phasing out the CourseworX course management tool that we had previously set up. So, the announcement (in class and below) asking you to register, is no longer applicable. Stay tuned; we will be back with a replacement soon.

05/12/2008: Please register your ID in Courseworx. Here is a page that tells you how. Courseworx will be used to post hw grades and solutions.

05/12/2008: Welcome !



Homeworks

Homeworks must be submitted on paper. Write your full name, UFID and gatorlink email address on the top right corner of your homework. Please typeset or write legibly. Unless otherwise indicated, the problems are from the exercises in the text.

Homework 6

Due Monday, August 4 2008, before the beginning of class.

For questions that ask you to determine if some statement is true, be sure to write a proof.

Section 4.1: 4, 10, 12, 24, 36, 42, 48, 56.
Section 4.2: 4, 12, 18, 30, 40.
Section 5.1: 4, 12, 26, 34.

Homework 5

Due Wednesday, July 30 2008, before the beginning of class.

For questions that ask you to determine if some statement is true, be sure to write a proof.

Section 8.1: 6bcfh, 24, 48ace, 50.
Section 8.3: 18, 36.
Section 8.4: 2, 14.
Section 8.5: 8, 10, 16, 22, 44ce, 54 (refinement is defined before Problem 49).

Exercises for 3.1-3.3

Solve but do NOT Submit the following exercises

Section 3.1: 4, 10, 11, 12, 29.
Section 3.2: 2bcef, 4, 13, 21, 27, 34, 41
Section 3.3: 1, 2, 4, 5.

Homework 4

Due Wednesday, July 2 2008, before the beginning of class.

For questions that ask you to determine if some statement is true, be sure to write a proof.

Section 2.3: 2, 4, 18, 36, 74a.
Section 2.4: 8, 12, 18bd, 20, 37, 43.

Homework 3

Due Friday, June 20 2008, before the beginning of class.

Section 2.1: 2ab, 8acef, 10, 18bd, 20.
Section 2.2: 4, 12, 26c, 34, 40, 62.

Exercises for 1.5-1.7

Solve but do NOT Submit the following exercises

Section 1.5: 3,13,19,23,27.
Section 1.6: 3,9,33,37.
Section 1.7: 7,17,31.

Homework 2

Due Wednesday, June 4 2008, before the beginning of class.

Section 1.3: 6def, 10, 30, 40cd, 46a.
Section 1.4: 6def, 12efgl, 28ghij, 32bc.

Homework 1

Due Wednesday, May 28 2008, before the beginning of class.

Section 1.1: 2, 6efgh, 10adef, 28def, 50.
Section 1.2: 4, 12d, 26(without using truth tables), 32, 40.



Summary of class activity

Date Topics covered in class Readings Other links
May 12
(Lecture 1)
Introduction, Syllabus, Barber's paradox, Naive set theory and Russell's paradox.
May 14
(Lecture 2)
Propositional logic - propositional variables, truth tables, connectives - negation, conjunction, disjunction, exclusive-or, conditional.
May 16
(Lecture 3)
Different ways of expressing a conditional statement (in English), Converse, contrapositive and inverse, equivalence of compound propositions, biconditionals.
May 19
(Lecture 4)
More on biconditionals, Truth tables of compound propositions, precedence of logical operators, tautology and contradiction, problem of proving propositional equivalences using truth tables. Section 1.1 of text
May 21
(Lecture 5)
Proving propositional equivalences without using truth tables. Section 1.2 of text
May 23
(Lecture 6)
Proving propositional equivalences without using truth tables - Examples, Predicates, universal quantifier.
May 26 MEMORIAL DAY
May 28
(Lecture 7)
Existential quantifier, examples, Other quantifiers, restricted domains.
May 30
(Lecture 8)
Precedence, Scope and binding, Logical equivalences involving quantifiers, DeMorgan's laws for quantifiers, Nested quantifiers, order of quantifiers, negating nested quantifiers. Section 1.3, 1.4 of text. Prize Problem 1
June 2
(Lecture 9)
Rules of Inference Section 1.5 of text.
June 4
(Lecture 10)
Introduction to Proofs Section 1.6 of text.
June 6
(Lecture 11)
Proof methods and Strategy Section 1.7 of text.
June 9
(Lecture 12)
Some exercises from Section 1.6,1.7.
June 9
(8:20pm-10:10pm)
Exam 1
(at MAT 51)
June 11
(Lecture 13)
Sets. Section 2.1 of text.
June 13
(Lecture 14)
Set Operations
June 16
(Lecture 15)
Sets Operations continued. Section 2.2 of text.
June 18
(Lecture 16)
Functions. Section 2.3 of text.
June 20
(Lecture 17)
Sequences and Series.
June 30
(Lecture 18)
Sequences and Series continued.
July 2
(Lecture 19)
Countability of rational numbers, Cantor's diagonalization argument, Algorithms, Motivation for study of complexity. Section 2.4 of text.
July 7
(Lecture 20)
Linear Search, Binary Search, Big-O notation. Section 3.1 of text
July 9
(Lecture 21)
Some theorems on Big-O, Big-Omega and Theta notation. Section 3.2 of text
July 11
(Lecture 22)
Analysis of time complexity of algorithms, worst-case analysis of algorithm that finds maximum element in a list, best, worst and average case analysis of linear search.
July 14
(Lecture 23)
Analysis of binary search, description and analysis of Bubble Sort, a lower bound for the search problem, motivations for computational complexity theory. Section 3.3 of text
July 14
(8:20pm-10:10pm)
Exam 2
(at MAT 51)
July 16
(Lecture 24)
Complexity classes, tractable and intractable problems, brief introduction to NP-completeness, Propositional satisfiability.
Relations, visualizing relations, relations and functions, reflexive relations.
July 18
(Lecture 25)
Symmetric and transitive relations, combining relations, composite relations. Section 8.1 of text
July 21
(Lecture 26)
Representing relations as digraphs, closures Section 8.3 of text (except matrix representations)
July 23
(Lecture 27)
Closures of Relations. Section 8.4 of text (excluding transitive closure algorithms)
July 25
(Lecture 28)
Equivalence relations, Principle of Mathematical Induction Section 8.5 of text
July 28
(Lecture 29)
Some example proofs using Mathematical Induction, Strong induction, proof of fundamental theorem of arithmetic using strong induction. Section 4.1 of text
July 30
(Lecture 30)
Proof of a result in computational geometry using strong induction. Section 4.2 of text
August 1
(Lecture 31)
Basics of Counting. Section 5.1 of text
August 4
(Lecture 32)
The Pigeonhole Principle. Section 5.2 of text
August 6
(Lecture 33)
Permutations and Combinations Section 5.3 of text
 
August 8
(8:20pm-10:10pm)
Exam 3
(at MAT 51)
 




Prize Problems

Prize problems will be problems that are more challenging than necessary for an introductory course such as this one. They will not count for credit towards the final letter grade. The first student in class to give a correct solution to the problem will get a prize, which will typically be a book, in addition to a mention here. Complete solutions (typeset or scanned handwritten) must be emailed to the instructor. Solutions must be original in that you are not allowed to look it up or discuss it with someone else. Also, if you already knew of the solution from before, you should not submit one. The idea here is to encourage original thinking.

Problem 1

In Chapter 1, we saw that given a compound proposition we could construct an equivalent truth table. Here we ask the opposite question: Given an arbitrary truth table, can we construct a compund proposition out of the connectives we have defined so far, which is equivalent to that truth table? The answer it turns out is Yes (which shows that our definitions are sufficient to express arbitrary truth tables). This problem is asking you to show that this is the case by coming up with a procedure to construct a compound proposition, given a truth table, such that the compound proposition is equivalent to the truth table. Also, show that the compund proposition you get is equivalent to the truth table by showing that it it true if and only if the truth table is true.



Valid HTML 4.01!