08/09/2008: Exam3 solutions are now available via E-Learning.
| Announcements | Homeworks | Lecture Schedule | Prize Problems | E-Learning system |
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
08/09/2008: Exam3 solutions are now available via E-Learning.
08/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.
08/05/2008: Quiz 4,5 and Homework5 grades are now available via E-Learning.
08/05/2008: Quiz 6 solutions are now available via E-Learning.
08/04/2008: Homework 6 solutions are now available via E-Learning.
08/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 !
| 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 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.