Syllabus and course information.
Please come see me if you have any questions.
Office Hours: Tuesday and Thursday 4 pm - 6pm.
If these times are not convenient just make an appointment by email or phone!
office: E6-1 4411
email: andreash[at]kaist.edu
tlf: (+82) 42 350 7300
Solutions for final exam.
Scorelist for final exam.
CLAIMS for final exam grades will be May 26 -- 28. You can pick up your exam in my office.
Here you can download last years final exam.
Here is solution to homework 3.
Chapter 9: 2 -- 6, 9 -- 18, 21, 23 -- 29, 31 -- 40, 41.
Chapter 10: 1 -- 4, 9, 10, 11, 15 -- 18, 21 -- 25, 27 -- 31, 33, 34, 35, 38.
Chapter 11: 1 -- 4, 8, 9, 12, 13, 15, 16, 18, 19, 24, 25, 26, (27, 28).
Chapter 12: 1 -- 16, 19, 20.
Chapter 13: 1, 2, 5, 6, 7, 15 -- 32.
Topics that will be covered on the test are Chapters 9 -- 13.
Download the midterm.
Download the solution. (beware of typos!)
First Homework assignment (Posted: 2010/02/18. Due: 2010/02/26).
Second Homework assignment (Posted: 2010/03/04. Due: 2010/03/12). Solution
Third Homework assignment (Posted: 2010/04/09. Due: 2010/04/16). (two pages)
2010/02/02 : We covered chapter 1 on pigeon-hole principle with applications from number theory, graph theory, and geometry.
2010/02/04 : We covered chapter 2 on mathematical induction, and presented the solution to the problem from previous class, due to 박진강.
2010/02/09 : We covered chapter 3 on elementary counting problems: permutations, strings over finite alphabets, ordered and unordered selections.
2010/02/11 : We completed chapter 3 on elementary counting problems: Bijections and selection problems. We counted the number of multisets of size k from [n], and non-negative integer solutions to the equation x1+...xn = k.
2010/02/18 : We did chapter 4 on combinatorial identities, the binomial and multinomial theorem. First homework assignment posted online.
2010/02/23 : We started chapter 5, covering compositions and set partitions, stirling numbers and surjective functions f : [n] -> [k]
2010/02/25: We continued with chapter 5, integer partitions, Ferrers shapes and some basic identities involving conjugation.
2010/03/02: We proved Euler's partition theorem: the number of partitions of n into distinct parts equals the number of partitions of n into odd parts. We presented solution to a previous extra credit question.
2010/03/04: We covered cahpter 7 on Inclusion-Exclusion Principle. Computed the number of derangements of [n], the number of surjective functions f:[n]->[k], and the permanent of a square matrix.
2010/03/09: We started chapter 8 on generating functions. We covered basic definitions and some examples of solving recurrence relations using generating functions.
2010/03/11: We continued chapter 8 on generating functions, establishing the product rule and composition of ordinary generating functions, and covered several examples illustrating how to use these rules.
2010/03/30: We introduced some basic notions of graph theory. This included trails, paths, and cycles. Degree sequence and the handshaking lemma. Diameter of a graph.
2010/04/01: We introduced some basic classes of graphs. The empty and complete graph. The complement of a graph. k-partite graphs and the chromatics number. We showed that a graph is bipartite if and only if every cycle is of even length. We showed that a graph with at least as many edges as vertices must contain a cycle, and we used this to prove that a connected graph is Eulerian if and only if every vertex is of even degree.
2010/04/06: We gave an algorithm for finding a Eulerian cycle in a graph. We defined hamiltonian graphs and proved Ore's theorem on hamiltonian cycles.
2010/04.08: We defined forest and trees and studied some basic properties of trees. Cayley's theorem on number of labeled trees on n vertices. Greedy algorithm for finding minimum weight spanning tree in a weighted graph.
2010/04/13: We studied some matrices associated with graphs: the adjacency matrix, the incidence matrix and the Laplacian. Matrix-tree theorem.
2010/04/15: We solved several problems and exercises concerning trees.
2010/04/20: We proved Turan's theorem: for any n there is a unique graph on n vertices and maximal number of edges which does not have a complete Km subgraph.
2010/04/22: We proved Hall's marriage theorem and studied some applications: complete matchings in regular bipartite graphs, latin squares and doubly stochastic matrices.
2010/04/27:
2010/04/29:
2010/05/04:
2010/05/06:
2010/05/11:
2010/05/13:
You should try to do all the 'Supplementary Exercises' from Bóna's book! The ones selected below will be reviewed during a recitation class.
2010/02/02 : Ch. 1; Pr. 19, 20, 25, 26, 27, 28.
2010/02/04 : Ch. 3; Pr. 29, 30, 35, 43, 48.
2010/02/18 : Ch. 3; Pr. 41, 42. Ch.4; Pr. 31, 34, 50, 51.
2010/03/06 : Ch. 1; 6, 8. Ch. 5; 23, 24, 25. Ch. 7; 15, 21, 23, 26, 27.
2010/04/01 : Ch. 9 ; 2, 3, 4, 5, 10, 11, 12, 16, 25, 29, 32, 35, 39.
2010/04/22 : Ch. 10; Pr. 24, 34, 27, 37. Ch. 11; Pr. 24, 25, 26 , 27, 28.
We will have recitation classes where we solve problems from the book. These classes are NOT mandatory. Time and date will be announced in class.
2010/02/11 : Recitation class 7-8pm, room 3435
2010/03/02 : Recitation class 7-8pm, room 3435
2010/03/11 : Recitation class 7-8pm, room 3435