COT 3100 Applications of Discrete Structures, Summer 2008

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:

Propositional and Predicate Calculus
Proof Techniques
Sets, Functions
Sequences and Series
Algorithms and Complexity
Basic Number Theory
Mathematical Induction, Recursion and Recurrence relations
Counting
Discrete Probability
Relations
Graphs, trees and graph algorithms
Basic Computation Theory

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:

Homeworks - 25%
3 exams - 20% each
Quizzes - 15%

The final grade will be on the curve.

Course policies:

Attendance and Class Demeanor: Attendance is highly recommended but not required. However, you are responsible for all the material covered in class. Cell phones and other electronic devices must be completely silent during class. And, no phone calls or messaging during class. Use of laptops during lecture is discouraged.
Late assignments: All homework assignments are due before the beginning of class. No late assignments will be accepted.
Collaboration: The homeworks are individual work. While you may discuss broad ideas with other students, you must formulate and write-up solutions on your own.
Regrading: All homework and exam regrade requests must be made within a week of their return.
Academic Honesty: See http://www.dso.ufl.edu/judicial/honestybrochure.htm for Academic Honesty Guidelines. All academic dishonesty cases will be handled through the University of Florida Honor Court procedures as documented by the office of Student Services, P202 Peabody Hall. You may contact them at 392-1261 for a "Student Judicial Process: Guide for Students" pamphlet.
Students With Disabilities: Students requesting classroom accommodation must first register with the Dean of Students Office. The Dean of Students Office will provide documentation to the student who must then provide this documentation to the Instructor when requesting accommodation.

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: Mon Jun 30 12:12:58 2008

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

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

This is new 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.

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

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

This is new 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.

This is new 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 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 14 (8:20pm-10:10pm)	Exam 2 (at MAT 51)


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.