o I will be away for the first week. Prof. Wheeler will substitute me for this week.
o See below for course info and the text book.
o Sep. 9: We reviewed some material about binomial coefficients and Pascal triangle. We showed number of lattice paths is given by binomial coefficients. We started to talk about Catalan numbers from Section 2.5.
o Sep. 10: HW1 posted. It is due next Wednesday in class.
o Sep. 16: We finished Chapter 2. We discussed multinomial coefficients (Sec. 2.7). We also proved the formula for the Catalan numbers (Example 2.23). We started with Chapter 2 (Induction) and gave an example of a problem whose answer can be given recursively (Sec. 3.5). As induction is familiar to most of the students we will cover it faster with emphasis on examples and recursive algorithms.
o Sep. 16: HW2 is now posted.
o Sep. 23: HW3 is posted.
o Sep. 25: We finished Chapter 4 (Combinatorial basics). Next week we talk about Graph Theory (Chapter 5).
o Sep. 28: Link to Wikipedia page of Dirichlet’s theorem about approximating a real number by a rational number . The proof was discussed in class and uses the Pigeon Hole principle.
o Sep. 28: We started with Chapter 5 and discussed 5.1 and 5.2 covering basic definitions and facts about graphs.
o Sep. 28: Link to Wikipedia page of Primality testing , if you are interested. As I mentioned in class a (deterministic) polynomial time algorithm for testing whether a given number is prime or not was found in 2002 by Indian mathematicians Manindra Agrawal, Neeraj Kayal, and Nitin Saxena.
o Midterm 1 is on October 14th in class.
o Midterm 1 covers all the material discussed in class from Chapter 2 to 5 (to the end of planar graphs).
o There will be 5 problems, one of which is to state definitions/theorems.
o Problems are similar to exercises in the text book and homework problems.
o HW5 is posted now. It is due next Friday.
o We finished with planar graphs. We started with the last topic in Chap. 5 which is counting labeled trees.
o We finished with Chapter 5. The last thing we discussed was Prufer code of a tree.
o We skipped Chapter 6 (Partially ordered sets). We covered with Principle of Inclusion-Exclusion. We didn’t cover the example of Euler’s phi function in that chapter.
o Oct. 31: We have started with Chapter 8 (Generating functions).
o Oct. 31: The second midterm will be on Friday November 20th during the class. It focuses on material covered after the first midterm.
o Nov. 2: Solution to MT1 posted.
o Nov 15: Midterm 2 info posted.
o Nov.23: HW9 and solutions to MT2 posted.
o Dec. 5: Notes about linear programming and Max-Flow-Min-Cut theorem
o Dec. 5: HW10 posted. You can consult the above notes for linear programming formulations of max flow and min cut as well as shortest path problems.
o Dec. 12: Notes about applications of Max-Flow-Min-Cut theorem in matching theory. The first part (Bipartite matchings and covers) is about the proof of Konig’s theorem. You only need this part for the exam, rest of these notes are for further study if you are interested.
o Dec. 13: Wikipedia page of Konig’s theorem.
o Dec. 13: Wikipedia page of Hall’s marriage theorem.
o Dec. 13: Final exam info sheet is now posted.
Click here for the weekly homework.
o Solutions to Midterm 1
o Midterm 2 info
o Solutions to Midterm 2
o Final exam info sheet
Topics: Basic counting methods, generating functions and recurrence, graph theory, graph algorithms, network flows, and some linear programming and convexity.
Text: M. Keller and W. Trotter "Applied Combinatorics" (Link to the latest version of the book)
Time of lectures: Monday-Wednesday-Friday 11:00AM - 11:50AM
Location of lectures: 525 Thackeray Hall
o There will be two midterms, one final exam, and weekly homeworks.
o Homework is assigned each Wednesday and is due the Wednesday after in class. I will announce when the first homework is posted.
o Final grade is 50% final exam, 30% midterms (15% each) and 20% homework (lowest hoemwork will be dropped).
o Important dates:
Aug. 31: first class
Sep. 7: Labor Day (no class)
Oct. 19: Fall Break (no class)
Nov. 25 - 29: Thanksgiving recess (no class)
Dec. 11: last class
Oct. 14: First midterm
Nov. 20: Second midterm
Email: kavehk AT pitt.edu
Office: Thackeray #424
Office hours: 11:00AM-12:00PM Tuesdays or by appointment. You can drop by I am usually in.
Office phone: 412-624-8331