Home Page

Math 113, Fall 1999

Combinatorics

• Official Information
• Virtual Office Hours
• Handouts

Daily notes

• See new on-line handout DD for solutions to sample final.
• In the last batch of homework solutions, 11.1, Problem 2, the figure given doesn't seem to match Table 11.1.
• 12/1: You may omit p. 268, Ex. 27. It's doable, but we don't have time to go over it.
• 11/18: Also in Assignment #7, p. 217, Ex. 23(d), just look at Ex. 22, guess a good "basis" of solutions for the recurrence, and set up linear equations using that basis to solve Ex. 23(d). You do not need to solve the linear equations.
• 11/16: One problem is wrong in Assignment #7, Handout V: Ex. 12, p. 216, results in a cubic equation that has no easy roots and is not solvable by methods you know. Instead, substitute this problem:
  Solve the recurrence a_n = 2 a_{n-1} + 3 a_{n-2}, a_0 = 0, a_1 = 1.
• 11/10: Office hours for the rest of the week changed as follows: Thursday 11/11: 12:30-1:30; Friday 11/12: 11:00-12:00.
• We'll index Fibonacci numbers using F0 = 0, F1 = 1, F2 = 1, F3 = 2, etc. Various formulas come out better this way, which is one off from how the text does it.
• No official office hour Thursday, Nov. 4, but I may be available briefly 3:40-3:55.
• Friday, October 29: Several people have pointed out that the solutions to the sample midterm need corrections: In 6(a), the edges and picture should be for four vertices, not five. In 6(b), G is not bipartite, since some edges were not taken into account. In 6(d), G has chromatic number 4.
• Wednesday, October 27: On the midterm, the only proofs requested will be among (1) the minimum bound on height of a binary search tree in terms of the number of nodes, as discussed in class and in Section 3.6.2 of the text, and (2) proofs that were asked for in homework problems from the text. For this exam, informal proofs are acceptable, but they should have the needed mathematical ingredients--for example, an "if and only if" proof should show implications in both directions.
• Monday, October 25: We'll use a definition of binary search tree different from the text: A binary search tree can have 0, 1, or 2 children at each node. If 1, it can branch right or left.
• Wednesday, October 20: One of you pointed out that in today's lecture I wrote Statement(n+1) incorrectly. It should have said n+1 = e+2.
• Office hours Thursday, October 21 will be 10-11. Office hours Friday, October 22 will be 11:30-12:00 only.
• In Assignment 2, p. 87, Ex. 14--just draw 10 typical graphs, rather than the whole list.
• Office hours on Thursday, October 14, will be 11-12.
• Our TA is Vrej Zarikian, Office MS 6617F, home page , email zarkian@math.ucla.edu .
• My office hour Wednesday, October 6 will be 2-3 instead of earlier.
• Correction to Handout A, last line: The TA is not the reader for this course.