CS 336 Course Description Fall 2009

Course meets Tuesday and Thursday, 2:00-3:30 PM in BUR 130.

Final exam, Saturday, December 12, 7:00-10:00 pm, in PHR 2.108.

Instructor: Tandy Warnow. Office: ACES 3.428. Email: tandy@cs.utexas.edu. Office hours: TuTh 1-2 PM. (No office hours during the week of Nov. 23-27.)

Teaching Assistant: Isaac Levy. Email: ilevy@cs.utexas.edu. Office ENS 31NQ, desk 5. Office hours: M 5pm-6:30 and W 1:30pm-3. Directions: take the elevator down to "LB" (lower basement). Exit the basement and go to the right; continue down the hallway, which curves to the right. Enter 31NR (on the left), and pass through it to the smaller room, which is 31NQ. (Wednesday, September 23 office hours: instead of 1:30-3, look for Isaac Levy from 4-5:30).

Course Description: This course focuses on discrete mathematical tools of fundamental importance to the working computer scientist. Applications for these concepts will be drawn from computational problems in biology and linguistics.

There is no textbook for the course. Instead, course notes will be provided.

Tentative Syllabus

• Review of logic and set theory. 1 week.
• Algorithm Design and Analysis. 3-4 weeks.
• Proof techniques (including induction). 2 weeks
• Graph Theory. 2-3 weeks
• Intro to Combinatorics. 2-3 weeks.
• Discrete Probability and Applications. 1-2 weeks
• Recurrence Relations. 1 week.
• Program Correctness. 1 week.

Grading

• Class participation: 10%
• Class Homework: 40% (worst homework dropped)
• Quizzes 30% (worst three quizzes dropped)
• Final exam 20%.

Policies

• Homeworks may be done in groups of two or three students, but you must write up the solutions to the homeworks yourself. Failures to do this have been observed. Please do your colleagues the courtesy of acknowledging their assistance, and do not just copy their solutions. Homework is due at 2:15 on the due date, in class. No late homeworks are accepted.
• Quizzes will be given frequently, and dates for quizzes may not always be posted. No make-ups will be given (note the increased number of drops).
• You are responsible for all the material taught in the class. If you miss a class meeting, please be sure to obtain notes from one of your fellow students. You can also download the presentation given by the instructor by the evening after the class.
• Class attendance is required. If you will not be able to attend the class for some reason that reasonably you would know about in advance (e.g., a religious holiday or sporting event in which you are a participant), you should tell me about this in the first week of class, so that I can try to accomodate your schedule. (Observed religious holidays will always be accomodated.)
• Please do not use your cellphone or laptop while in the class -- it is distracting to the other students, and unnecessary.

Additional Notes

• Course material may vary depending on student interest.

Academic honesty:

• Please see Professor Elaine Rich's discussion of academic honesty and appropriate conduct.
• Most importantly, do not, under any circumstances, submit work that is not your own work. Penalties for cheating are very serious, and cheating becomes part of your permanent university record.

Course lectures

• Day 1 (Aug 27, 2009), Introduction to the course (PPT)
• Day 2 (Sept. 1, 2009), Intro to induction proofs (PPT)
• Day 3 (Sept 3, 2009), Intro to algorithm design (PPT)
• Day 4 (Sept. 8, 2009), Intro to mathematical writing (PPT)
• Day 5 (Sept 10, 2009), More induction proofs (PPT)
• Day 6 (Sept 15, 2009), lecture by TA Isaac Levy available here.
• Day 8 (Sept 22, 2009). Dynamic programming for longest increasing subsequence (PPT).
• October 6, 2009. Big-oh: what it really means, and how to prove that functions are big-oh of other functions. (PPT)
• October 8, 2009. Practice with big-oh. Guest lecturer Dr. Shel Swenson.
• October 13, 2009. Practice with big-oh.
• October 15, 2009. Quiz on big-oh. See this write-up with practice problems.
• October 20, 2009. Intro to counting (PPT).
• October 22, 2009. More on counting.
• October 27, 2009. Review of the homework.
• October 29, 2009. We reviewed the homework, and also talked about induction proofs. We considered the following problem: Given F(n,m) defined for positive integers n and m, and with
  • F(n,m)=n+m if n or m is at most 2,
  • F(n,m)=F(n-1,m)+F(n,m-2) when both n,m are at least 3
  Prove by induction that F(n,m) is at least n+m.
• November 3, 2009. We will cover the Inclusion-Exclusion Principle. You can read about this on wikipedia, here, or at various sites (including this one). We also had a quiz (see homework #11, given below).
• November 5, 2009. We did more problems using inclusion-exclusion. We also went over how to do strong induction.
• November 10, 2009. Graph-theoretic problems: Eulerian tours, Hamiltonian cycles, max clique, maximum independent set, and shortest paths (Part I). See (PPT) for the shortest path algorithms.
• November 12, 2009. Dynamic programming algorithm for all-pairs shortest paths, part II.
• November 17, 2009. Proving programs correct, (PPT), Part I. Please see this wikipedia page for loop invariants, and this wikipedia page for Hoare logic (and Hoare triples). Finally, see this draft of a book by Robert Van de Geijn and Maggie Myers on this topic.
• November 19, 2009. Proving programs correct, Part II.
• November 24, 2009. Quiz (topics: proving programs correct and combinatorial counting, including inclusion-exclusion).
• November 26, 2009. Thanksgiving vacation.
• December 1 and 3, 2009. Review of the course.

Homework assignments.

• Homework #1, due September 8, 2009, by 2:15 (PDF) Solutions available here.
• Homework #2, due September 17, 2009, by 2:15. (PDF). Solutions available here.
• Homework #3, due September 22, 2009, by 2:15. (PDF). Solutions available here.
• Homework #4, due September 24, 2009, by 2:15. See the last page of the powerpoint presentation for Sept. 22.
• Homework #5, due October 8, 2009, by 2:15. (PDF).
• Homework #6, due October 15, 2009, by 2:15. Do all the questions on the third page of this pdf file.
• Homework #7, due October 20, 2009, by 2:15. Write up correct solutions to all problems for which you did not get full credit on the most recent quiz. (If you did not do the quiz, you need to hand in solutions to all the problems.) You can obtain the quiz here.
• Homework #8, due October 27, 2009, by 2:15. See (PDF).
• Homework #9, due October 29, by 2:15 PM. Give a proof (full detail) for $f(n)=3^n$ is $O(3^n - 2^n)$, by providing the constants, and proving that the inequality holds.
• Homework #10, due November 3, 2009, by 2:15. Write up solutions to every problem you did not get full credit on for Quiz 5, (PDF). Note: you must show *all* your work for this homework.
• Homework #11, due November 10, 2009, by 2:5. Write up solutions (in full detail) to all the problems on the last quiz for which you did not get full credit. Also enumerate solutions for n=3 for each question. Here are the questions from the quiz:
  • What is the number of 1-1 functions f from {1,2,...n} to itself?
  • What is the number of functions f from {1,2,...,n} to itself for which there is some i where f(i) is not i?
  • What is the number of functions f from {1,2,...,n} to itself for which f(i) is not i for all i?
  • What is the number of 1-1 functions f from {1,2,...,n} to itself for which f(i) is not i for at least one i?
• Homework #12, due November 24, 2009, by 2:15 in class (PDF).

Course notes.

• Please see this for some terminology (from a previous class), especially helpful for talking about graphs.
• Professor Dan Gusfield of the University of California at Davis has written a delightful and informative discussion on induction proofs called ``Why Johny can't induct". Please click here to download the pdf.