CS 336 Course Description Spring 2012

Instructor: Tandy Warnow. Office: ACES 3.428. Email: tandy@cs.utexas.edu.

Office hours: Tuesdays (starting Jan 24) 3-5 and by appointment. Additional Office hours: April 26, 12:15-1:30, 2-3. Monday April 30: 12-2.

Teaching Assistant: Andrei Margea. Email: utistu87@cs.utexas.edu. Office hours for Andrei Thu 9:30-11 AM and Fri 2-3:30 PM, at Desk 6 of the TA stations, 5th floor of Painter Hall.

Class meets: MW 2:00-3:30, BUR 208.

Course website: http://www.cs.utexas.edu/users/tandy/336-2012.html

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.

Pre-requisites: the following courses with a grade of at least C- in each: CS 313H or 313K; 314, 314H, 315 or 315H; and M 408C, 408L, or 408S.

Textbook: Rosen, Discrete Mathematics and its applications

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

• Homework: 15%
• Exam I: 15% (Feb 8)
• Exam II: 15% (March 5)
• Exam III: 15% (approx April 11)
• Final exam 40% (May 2nd, in class)

Policies

• Homeworks are due by 2:15 PM on the day they are due, not later. Grading for homework is pass/fail for each homework. Fifteen homework assignments will be given, and you will receive full credit for each homework for which you receive a pass.
• 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 strongly recommended, but will not count towards the grade. 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.

See Course webpage for 336 from Fall 2009 for my previous 336 course.

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.

Lectures

• January 18, 2012 (PPT) (PDF)
• January 23, 2012 (PPT) (PDF)
• January 25, 2012 (PPT) (PDF)
• January 30, 2012 (PPT) (PDF)
• February 1, 2012 (PPT) (PDF)
• February 13, 2012 (PPT) (PDF)
• February 15, 2012. More about big-oh: (PDF). Dynamic programming algorithms for all-pairs shortest path (PPT) (PDF)
• February 20, 2012. Review of homework.
• February 22, 2012 Quiz on big-oh, proof by contradiction, proof by induction, and dynamic programming (PDF).
• February 27, 2012. Discussion of material from previous quiz, and preparation for Exam #2 (May 5).
• March 5, 2012: exam #2 (PDF)
• March 7, 2012: review of exam, reading and writing mathematics, and graph theory (PPT) (PDF)
• March 19, 2012: Graph Theory (PDF) (PPT)
• March 21, 2012: Introduction to Combinatorial Counting (PPT) (PDF)
• March 26, 2012: Combinatorial Counting (cont.) (PPT) (PDF)
• March 28, 2012: Introduction to Discrete Probability (PPT) (PDF)
• April 2, 2012: Quiz.
• April 4, 2012: review of quiz.
• April 9, 2012: DP algorithms on trees (PPT) (PDF)
• April 11, 2012: Preparation for Exam 3
• April 16, 2012: Exam 3.
• April 18, 2012: Exam 3 (solutions and discussion)
• April 23, 2012: Exam 3, continued discussion. More combinatorial counting.
• April 25, 2012: Program correctness (PDF) (PPT)
• April 30, 2012 (tentative): Review for final
• May 2, 2012: Final Exam

Exams

• Exam 1, solutions by Andrei Margea (PDF)
• Exam 2 (PDF)
• Exam 3 (PDF), solutions here.

Homework

• Homework #1 (Due January 23):
  Consider the rock game (described in Lecture for January 18, 2012, see above links) with each pile having 0-3 rocks. For each possible starting condition (defined by the number of rocks in each pile), determine whether the first player has a winning strategy (i.e., is able to win, no matter what the second player does). Give your reasons, not just the answer. Solutions (written by Andrei Margea) posted here.
  
  
• Homework #2 (due January 30, (Solutions, written by Andrei Margea, posted here):
  • Draw a graph that has five vertices and 3 edges
  • Draw a graph that has five vertices and 5 edges
  • Write in set theoretic notation the set of all positive integers whose square is greater than 5.
  • Write in set theoretic notation the set of all functions from the integers to the integers that have at least one fixed point
  • Write in set theoretic notation the set of all functions from the integers to the integers that have exactly one fixed point
  • Write in set theoretic notation the set of all sets of integers that have no even numbers
  • Write in set theoretic notation the set of all sets of real numbers so that the product of all its elements is greater than 100
  • Express using mathematical notation the property that a function F from a set A to a set B is one-to-one (injective)
  • Express using mathematical notation the property that a function F from a set A to a set B is surjective
  • Find a closed form solution for the following recursively defined function F (defined for all positive integers n), and prove it correct by induction on n:
    F(1) = 4, F(2) = 13, and F(n) = F(n-1) + 6n -3.
  • In the Rock Game, who has a winning strategy for the case where there are 10 rocks on one pile and 8 rocks on the other pile? How did you figure this out?
  
  
• Homework #3 (due Feb 6, solutions written by Andrei Margea posted here):
  • 1. Consider the following variant of the rock game. There are two players and two piles of rocks, and each player can take a total of up to two rocks off (distributed however that player wants); thus, in a given turn a player can take 2 rocks off of one pile, 1 rock of each pile, or 1 rock off of one pile. The player to remove the last rock wins. Determine who has a winning strategy for all cases with up to 10 rocks on each pile.
  • 2. Let f(n) be defined by f(1)=9 and f(n)=f(n-1)+4 if n>1. Prove that f(n)=4n+5 for all positive integers n.
  • 3. Let F(a,b) be defined for positive integers a and b, by
    • F(1,x)=F(x,1)=x for all x
    • F(a,b) = F(a-1,b) +F(a,b-1) for all positive integers a and b
    For this function F(.,.), do the following:
    • a. Compute F(6,6).
    • b. Give a polynomial time algorithm to compute F(a,b) for arbitrary values of a and b (so the running time must be polynomial in a and b).
  • 4. Write the following as a graph-theoretic problem: You want to divide up the class into of disjoint sets so that no two people in any set are friends, and so that you use the smallest number of sets possible. (What are the vertices, what are the edges, and what are you looking for?)
  • 5. Write the following as a graph-theoretic problem: You want to find out if it is possible to divide the students in the class into disjoint pairs (everyone in some pair, but no one in two pairs) so that for each pair you create, the two students like each other. What are the vertices, what are the edges, and what are you looking for?
  
  
• Homework #4 (due Feb 20, 2012):
  • Click here. Solutions by Andrei Margea here.
  • Read Section 3.2 in Rosen (pages 204-216) and Section 5.1 in Rosen (pages 311-329).
  
  
• Homework #5 (due Feb 27, 2012), see (PDF), solutions by Andrei Margea):
  • Do problems 32, 38, and 50 on pages 330-332.
  • Do problems 12, 16, 22, and 24 on page 216.
  • Look up Karp's 21 NP-complete problems, and find out what the problems mean (one place to find this is in Wikipedia, under http://en.wikipedia.org/wiki/Karp's _21_NP-complete_problems). Think about real world problems where these abstract problems might be appropriate. For four of these abstract ``Karp" problems, make up a ``real world" problem that could be solved by an exact algorithm for the abstract problem.
  
  
• Homework #6 (due March 5, 2012):
  • You have a choice (A or B) for this homework! Both refer to this PDF. A: Do at least half the problems in each subsection
    B: Do at least one problem in each subsection, and make sure to include at least one italicized problem in each subsection that has italicized problems.
  
  
• Homework #7 (due March 19, 2012, solutions by Andrei Margea (here)):
  • Use formal mathematical notation to state the following properties
    • A function f mapping set A to set B is an onto function.
    • A function f mapping set A to set B is not the identity function
    • A function g mapping from set B to set A is the inverse of function f from set A to set B.
    • A set X of sets does not contain any singleton sets
    • For a given set X of sets, express the property that any two elements of X are either pairwise disjoint or one contains the other.
  • Use set-builder notation to define the following sets Y:
    • For a given set X of finite subsets of the integers, the subset Y consisting of those elements of X that have the same number of negative elements as positive elements.
    • For a given set X of finite subsets of the integers, the subset Y consisting of those elements of X that do not have any positive elements.
    • For a given set X of finite subsets of the integers, the subset Y consisting of those elements of X that do not contain any squares.
    • For a given graph G = (V,E), the set Y consists of those vertices in V that have at least two neighbors
  • Let function F(a,b) be defined by
    • F(0,a)=F(a,0)=a for a=0,1,...
    • F(a,b)=2+max{F(a,b-1),F(a-1,b)}
    Prove that F(a,b) is at most 2(a+b) for all non-negative integers a,b.
  • Prove that any integer that is at least 8 can be written as 3x+5y, for some non-negative x and y. (This problem can also be stated as proving that any amount of postage of at least 8 cents can be paid for with a combination of 3 and 5 cent stamps.)
  • Prove, by contradiction, that the square root of 6 is irrational.
  • Prove, by contradiction, that no matter how you order the integers 1 to 36 in a circle, there will be three consecutive numbers in the circle that add up to 56 or larger.
  
  
• Homework #8 (due March 21, 2012, solutions by Andrei Margea here):
  • Use structural induction to prove one or more of the following:
    • A graph with maximum degree d can be properly vertex-colored using d+1 colors
    • A connected graph in which every node has even degree is Eulerian
  • Prove that for any graph G, the product of its chromatic number and its independence number is at least the number of vertices in G. (Hint: consider an optimal vertex coloring of G and the number of vertices inside any color class.)
  
  
• Homework #9 (due March 26, 2012, solutions by Andrei Margea here):.
  • Answer all the questions here.
  
  
• Homework #10 (due March 28, 2012, solutions by Andrei Margea here):
  • Use the Inclusion-Exclusion principle to solve the following problem. In a group of 50 children in the United Nations International School, the following were observed. All children spoke English. But, in addition, 30 spoke French, 18 spoke Japanese, 26 spoke Hindi, 9 spoke both French and Japanese, 16 spoke both French and Hindi, 8 spoke both Japanese and Hindi, and 47 spoke at least one of French, Japanese, and Hindi. From this we have to determine a. How many children spoke none of these three languages (French, Japanese, and Hindi)? b. How many children spoke French, Japanese, and Hindi (all three languages)?
  
  
• Homework #11 (due April 2, solutions by Andrei Margea here):
  • These problems all refer to randomly drawn hands from a normal deck of 52 cards.
    • What is the probability of getting a flush in four cards drawn randomly from a deck of 52 cards>
    • What is the probability of having four randomly drawn cards having no hearts?
    • What is the probability of having four randomly drawn cards having one heart, one diamond, one spade, and one club?
  • How many subsets of k vertices are there in a graph with n vertices?
  • Describe an exhaustive search algorithm to find a maximum clique in a graph. Give an upper bound for its running time.
  • Describe an exhaustive search algorithm to find a longest simple path in a graph. Give an upper bound for its running time.
  • Describe an algorithm to find a longest simple path in a tree (connected acyclic graph). Give an upper bound for its running time.
  
  
• Homework #13 (due April 9).
  • Do all problems here. Show all your work -- do not just write down answers. Solutions by Andrei Margea here.
  
  
• Homework #14 (due April 16) Solutions by Andrei Margea here. Note: Problem 8 on page 432 requires a particular technique that was not taught, and so will not be counted in the grade.
  • Do the following problems in Chapter 6.5 (pages 432-433): 4, 8, and 42.
  • Do the following problems in Chapter 6.6 (Supplementary Exercises, page 441): 4 and 10.
    
  • What is the probability that out of n people, no two are born on the same day of the week? Calculate this as a function of n. What is the smallest value for n for which this probability is less than 0.5?
  
  
• Homework #15 (due April 25) (solutions here).
  • Let F(n)=3F(n-1)-F(n-2) if n is at least 2, and F(0)=F(1)=1.
    • Prove that F(n) is at least F(n-1) for all n that are at least 2.
    • Prove that F(n) is positive for all n.
    • Prove that F(n) is at most 3F(n-1) for all n that are at least 2.
  • Write full solutions (with English text) to every part of problem 7 from the exam (even if you got full credit), (PDF).
  
  
• Homework #12 (yep, out of order!, due April 30), see this PDF, solutions here.