12/21/2009: The Final Exam scores and the Letter grade are now available on WebCT.
| Announcements | Homeworks | Lecture Schedule | WebCT |
|
Chunglae Cho Office: CSE E309 E-mail: cot3100fa09@cise.ufl.edu Office hours: Tuesday 2pm - 4pm |
Nam Nguyen Office: CSE E309. E-mail: cot3100fa09@cise.ufl.edu Office hours: Thursday 9,10 (4:05-6:00pm) |
Siva Rajamanickam Office: CSE E309. E-mail: cot3100fa09@cise.ufl.edu Office hours: Wednesday (10:40am - 12:35pm) |
Ajit Rajwade Office: CSE E309. E-mail: cot3100fa09@cise.ufl.edu Office hours: Friday (9:35 am to 11:35 am) |
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 Dec 21 12:20:33 2009
12/21/2009: The Final Exam scores and the Letter grade are now available on WebCT.
12/14/2009: Solutions to homework 7 have been posted on WebCT.
12/10/2009: Solutions to exercises from Section 5.3 and 5.5 have been posted on WebCT.
12/10/2009: Some exercises from Section 5.3 and 5.5 have been posted. Solutions will be posted on WebCT before the end of the weekend.
12/10/2009: As announced in class, the Final Exam on Friday (12/18, 12:30pm-2:30pm) will be closed-book, closed-notes with no calculators permitted. No collaborations are allowed. A US letter size cheat sheet (both sides) is permitted as long as it is originally handwritten (i.e. a photocopy of handwritten is ok). The final exam is comprehensive, i.e. will test material covered throughout the semester, although emphasis will be on material covered since Exam 2.
12/05/2009: Chunglae will hold his office hours Tuesday 2pm-4pm, Wednesday 1-2pm, and Friday 1-2pm in the week of December 8th. He will not hold his office hours on December 15th.
12/05/2009: Quiz 5 grades are now available on WebCT. You can pick up your quiz paper in any TA's office hours. Regrading request should be directed to Chunglae Cho by meeting in his office hours or by appointment. The due for the regrading request is Friday, December 11th. There is a paper on which no name was written and another paper on which a name was not clearly written. If you think that one of them is yours, please come to see Chunglae in his office hours.
12/04/2009: Venkat's office hours today will be held 5:10pm-6:00pm, instead of 4:05pm-4:55pm.
12/04/2009: Section 4.2, Problem 24 is excluded from Homework 7.
12/02/2009: There will be an in-class quiz on Friday. Section 5.1 and 5.2 (until what was covered in class today) will be tested.
11/30/2009: Homework 7 is now up.
11/23/2009: Homework 6 solutions are posted in WebCT.
11/23/2009: Siva's office hours on Wednesday 11/25 are cancelled. Siva will hold additional office hours on Tuesday 12/01 from 4pm-6pm.
11/19/2009: Nam will not hold office hours today (Nov 19th, 09). They will be shifted to 4-6 tomorrow.
11/18/2009: Quiz 4 grades are now available on WebCT. You can pick up your quiz paper in any TA's office hours. Regrading request should be directed to Chunglae Cho by meeting in his office hours or by appointment. The due for the regrading request is Tuesday, November 24th.
11/18/2009: Quiz 4 solution is posted on WebCT.
11/16/2009: Chunglae will hold his office hours at E440 (not at E309 as usual) tomorrow (Tuesday) between 2pm and 4pm.
11/13/2009: There will be an in-class quiz on Monday. Material from Sections 3.1-3.3 will be tested.
11/13/2009: Homework 6 is now up.
11/07/2009: Exam 2 scores are now available on WebCT. Exam papers can be picked up in office hours. The due for the regrading request is November 18th. Nam graded Q1,2, Ajit graded 3,4,5, Chunglae graded 6,7, Siva graded 8,9,10a, and Venkat graded 10b, 10c.
11/04/2009: Exam 2 solutions are now available on WebCT.
10/31/2009: The solutions of the exercises for Chapter 3 are now available on WebCT.
10/31/2009: Some exercises for Chapter 3 have been posted. Solutions will be available on WebCT later today.
10/30/2009: As announced in class, Exam 2 on Monday will be closed-book, closed-notes with no calculators permitted. No collaborations are allowed. A US letter size cheat sheet (one side) is permitted as long as it is originally handwritten (i.e. a photocopy of handwritten is ok). The following material will be tested:
10/30/2009: There is a student who didn't write his/her name on the Quiz 2 paper. If you are the student, please bring your another handwritten paper to Chunglae in his office hours so that he can make sure it is yours.
10/29/2009: Chunglae will have his extra office hours from 4pm to 5pm this Friday. Next Tuesday he will have short office hours from 2pm to 3pm.
10/29/2009: Quiz 3 grades are now available on WebCT. You can pick up your quiz paper in any TA's office hours after the class hour on October 30th. Regrading request should be directed to Chunglae Cho by meeting in his office hours or by appointment. The due for the regrading request is November 6th.
10/28/2009: HW5 solutions are available on WebCT. Nam will grade this HW.
10/26/2009: HW2 and HW4 grades are now available on WebCT.
10/21/2009: HW4 Solutions are now available on WebCT. Nam will grade HW4.
10/21/2009: Exam 2 will test material taught until the end of class on Oct 30.
10/21/2009: There will be a quiz on Friday. Material covered through today will be tested with emphasis on material that was left as a reading assignment (increasing/decreasing functions, floor/ceiling functions etc).
10/21/2009: Homework 5 is now up.
10/19/2009:Homework 3 solutions are now available on WebCT. Siva will grade it.
10/14/2009: Homework 4 is up.
10/09/2009: Exam 1 scores are now available on WebCT. Exams may be picked up in office hours. You have one week to seek regrades. Siva graded Q1-5, Nam graded Q6,7, Chunglae graded 8, 9, 10 and Venkat graded 11.
10/07/2009: Homework 3 is now up.
10/05/2009: Grade for Quiz 2 is now available on WebCT. You can pick up your quiz paper in any TA's office hours. Regrading request should be directed to Chunglae Cho by meeting in his office hours or by appointment. The due for the regrading request is October 13th.
09/29/2009: As announced in class, Exam 1 will be closed-book, closed-notes with no calculators permitted. No collaborations are allowed. A US letter size cheat sheet (both sides) is permitted as long as it is originally handwritten (i.e. a photocopy of handwritten is ok). Material through Page 83 of the textbook will be tested on Exam 1.
09/26/2009:Homework 2 solutions are now available on WEBCT and will be graded by Siva.
09/26/2009:SOLUTIONS to Exercises for Section 1.6 are now available on WEBCT.
09/25/2009: Exercises for Section 1.6 are now available. These are not to be turned in. Solutions will be posted on WebCT tomorrow.
09/25/2009: There will be an in-class quiz on Monday. Material covered until today will be tested on Exam 1.
09/18/2009: Homework 2 is now up.
09/17/2009: Grade for Quiz 1 is now available on WebCT. You can pick up your quiz paper in any TA's office hours. Regrading request should be directed to Chunglae Cho by meeting in his office hours or by appointment. The due for the regrading request is September 25th.
09/16/2009: Siva's office hours today are canceled.
09/14/2009: Exam 1 has been rescheduled to Sep 30, 8:20pm to 10:10pm at CSE E119 (same place where the class meets for lecture). Material covered through Sep 25 will be tested.
If you have an exam in another course scheduled at the same time, pursuant to regulations on this matter, the higher numbered course takes priority (i.e. the instructor for the lower-numbered course assigns make-up work), except for assembly-exam courses which take priority. Please contact the appropriate instructor at the earliest to request make-up work, in this case.
09/14/2009: Grade for HW 1 is now available on WebCT.
09/11/2009: Quiz 1 Solutions are now available on WebCT.
09/11/2009: Homework1 solution is now available on WebCT and will be graded by Nam.
09/09/2009: There will be an in-class quiz on Friday. Sections 1.1 and 1.2 will be tested.
09/09/2009: In Homework 1, for problems in Section 1.2, you may use any of the equivalences listed in Tables 6-8 on Page 24/25, without proof, except in the case when you have to prove one of them, in which case except for the one in question, you may use the rest.
09/04/2009: It has been pointed out that Exam 1 is currently scheduled at the same time as the CISE Career Development Workshop. To enable students to attend both, Exam 1 will be rescheduled. Stay tuned for more information.
09/04/2009: Homework 1 is now up.
09/02/2009: The exam dates are now confirmed. The dates, times and location of each exam is noted in the lecture schedule.
08/31/2009: Ajit's office hours are now up.
08/29/2009: For the benefit of those whose don't have their textbooks yet, a scanned copy of the first two sections is now available on WebCT.
08/27/2009: All TA email must be directed to cot3100fa09@cise.ufl.edu. Please do not use a TA's individual email address.
08/26/2009: There will not be any discussion sessions during the first week.
08/22/2009: Welcome !
| Date | Topics covered in class | Readings | Other links |
| Aug 24 (Lecture 1) |
Introduction, motivation and Syllabus. | ||
| Aug 26 (Lecture 2) |
Barber's paradox, Russell's paradox, Propositions, examples. | Undergraduation | |
| Aug 28 (Lecture 3) |
Propositional variables, truth tables, compound propositions, conjunctions, disjunctions, exclusive-or, conditionals | ||
| Aug 31 (Lecture 4) |
Converse, contrapositive inverse, equivalence of compound propositions, biconditionals | ||
| Sep 2 (Lecture 5) |
Example of use of conditionals and biconditionals in definitions, precedence of logical operators, Computer bit operations, tautology, contradiction and contingency, examples. | Section 1.1 of text. | |
| Sep 4 (Lecture 6) |
Need for a new technique (different from truth tables) to prove equivalences, list of equivalences, example of an equivalence proved algebraically. | Section 1.2 of text. | Homework 1 |
| Sep 9 (Lecture 7) |
More propositional equivalences | ||
| Sep 11 (Lecture 8) |
Predicates, Quantifiers - Universal quantifier, examples. | ||
| Sep 14 (Lecture 9) |
Existential quantifier, quantifiers with restricted domains, precedence of quantifiers, binding variables, equivalences involving quantifiers. | ||
| Sep 16 (Lecture 10) |
Negating quantified statements, Nested quantifiers | Section 1.3 of text | |
| Sep 18 (Lecture 11) |
More on nested quantifiers, Rules of inference | Section 1.4 of text | Homework 2 |
| Sep 21 (Lecture 12) |
Rule of inference, using rules of inference to build arguments | ||
| Sep 23 (Lecture 13) |
Rules of inference for quantified statements, Proofs | Section 1.5 of text | |
| Sep 25 (Lecture 14) |
Direct Proofs, Indirect Proofs, Proof by contradiction | Section 1.6 of text through Page 83. | |
| Sep 28 (Lecture 15) |
Examples of proofs. | ||
| Sep 30 (Lecture 16) |
Some problems. | ||
| Sep 30 (8:20pm-10:10pm) |
Exam 1 (at CSE E119) |
||
| Oct 2 (Lecture 17) |
Equivalence proofs, counterexamples, proof by cases. | Section 1.6 of text | |
| Oct 5 (Lecture 18) |
Existence proofs - constructive and non-constructive, uniqueness proofs, proof strategies. Sets, Set Builder notation. | Section 1.7 of text | |
| Oct 7 (Lecture 19) |
Equality of sets, subsets, proper subsets, cardinality of finite sets, Power Set, examples. | Homework 3 | |
| Oct 9 (Lecture 20) |
Cartesian Product, Set notation with quantifiers, truth sets, union, intersection, set difference. | Section 2.1 of text | |
| Oct 12 (Lecture 21) |
Set identities, techniques for proving set identities, examples. | ||
| Oct 14 (Lecture 22) |
Membership tables, Functions | Section 2.2 of text. | Homework 4 |
| Oct 19 (Lecture 23) |
Image, preimage of an element and of a set, one-to-one and onto functions, bijections, inverse functions. | ||
| Oct 21 (Lecture 24) |
Composition of functions, graphs, Sequences, geometric and arithmetic progressions, summations. | Section 2.3 of text. | Homework 5 |
| Oct 23 (Lecture 25) |
Extending notions of cardinality for infinite sets - Countable sets, examples | ||
| Oct 26 (Lecture 26) |
Proof that the set of rational numbers is countably infinite, Cantor's diagonalization argument to prove that the set of real numbers in [0, 1] is not countably infinite. | Section 2.4 of text. | |
| Oct 28 (Lecture 27) |
Notion of an algorithm, Example - Algorithm to find largest element in a list. Properties of a measure of time complexity for an algorithm, Growth of functions, Big-O notation, examples. | ||
| Oct 30 (Lecture 28) |
More examples of Big-O. Definition of f(x) = Theta(g(x)): f(x) = Theta(g(x)) iff f(x) = O(g(x)) and g(x) = O(f(x)). Analysis of algorithm that finds the maximum element in a list. | ||
| Nov 2 (Lecture 29) |
Some problems and review. | ||
| Nov 2 (8:20pm-10:10pm) |
Exam 2 (at CSE E119) |
||
| Nov 4 (Lecture 30) |
Discussion of Problem 10 of exam, proof that any polynomial of degree k is O(x^k). | ||
| Nov 6 (Lecture 31) |
More theorems on Big-O, examples. | ||
| Nov 9 (Lecture 32) |
Big-Omega, Big-Theta, Best, worst and average case analysis of linear search. | Section 3.2 of text. | |
| Nov 11 |
VETERANS' DAY. | ||
| Nov 13 (Lecture 33) |
Analysis of binary search and bubble sort. | Section 3.1 and 3.3 of text. | |
| Nov 16 (Lecture 34) |
Complexity upper bounds and lower bounds on problems (as opposed to on algorithms), Proof of an Omega(n) lower bound for the problem of finding the maximum element in a list. | ||
| Nov 18 (Lecture 35) |
Principle of mathematical induction, examples of proofs using mathematical induction. | Section 4.1 of text. | |
| Nov 20 (Lecture 36) |
Strong induction, Proof of the fundamental theorem of arithmetic using strong induction, polygons, convex polygons etc. | ||
| Nov 23 (Lecture 37) |
Proof (using strong induction) that every simple polygon with n sides can be triangulated into n-2 polygons. Counting - Product rule. | Section 4.2 of text. | |
| Nov 25 (Lecture 38) |
Introduction to the Theory of Computing: Computability Theory, Post's Correspondence Problem, Complexity Theory, The Complexity classes P and NP, The P=NP? question, NP-completeness, 3CNF-SAT, 2CNF-SAT. (Note: Material covered in this lecture will not be tested in Homeworks/Quizzes/Exams for this course). | ||
| Nov 30 (Lecture 39) |
Counting - Product Rule, examples, Sum rule, examples, Pigeon-hole Principle, example. | Section 5.1 of text. | |
| Dec 2 (Lecture 40) |
Generalized Pigeon-hole principle, examples, Some elegant applications (Example 3, Theorem 3). | Section 5.2 of text. | |
| Dec 4 (Lecture 41) |
On Ramsey Theory, Ramsey numbers, Permutations | ||
| Dec 7 (Lecture 42) |
Permutations and Combinations | Section 5.3 of text. | |
| Dec 9 (Lecture 43) |
Generalized Permutations and Combinations - Permutations with repetition, Combinations with repetition. (through Page 374 of text) | Section 5.5 of text (through Page 374). | |
| Dec 18 (12:30pm-2:30pm) |
Final Exam (at CSE E119) |