Discrete Mathematics

Course Information

Textbook:Discrete Mathematics with Ducks by Sarah-Marie Belcastro

Classes: Wednesday 10am~1pm; 자2-420호

Grades: 2 Midterms (200 points), Final Exam (100 points), Homework, Quizzes and Projects (200 points)

Instructor's Office Hours: W 2~4 pm (Room 417)

Teaching Assistants: Choi, Hwan-Hyuk (최환혁) whchoi@kangwon.ac.kr (Room 415)

Announcement

• 4/10 중간고사1 (Chapters 1~6); 5/15 중간고사2 (Chapters 6~9 and generating functions); 6/19 기말고사(Chapters 10~13)
• 마지막 수업: 6/12 수요일 12~2pm

Topics covered in class

• 3/6 The Basics: counting, proofs, sets and logic
• 3/13 The Basics: graphs and functions
• 3/20 The Basics: more on graphs, Ramsey number, induction
• 3/27 The Basics: more on induction, review on Ramsey number; problems using well-ordering principle, algorithms with ciphers
• 4/3 Combinatorics: binomial coefficients and Pascal's triangle
• 4/10 Combinatorics: balls and boxes
• 4/17 Combinatorics: more on counting techniques, Stirling number of the second kind, Catalan number
• 4/24 Combinatorics: recurrences, Catalan number, Stirling number, Bell number, generating functions
• 5/1 Combinatorics: recurrences, generating functions
• 5/8 Combinatorics: recurrences, generating functions, counting and geometry
• 5/22 Graph Theory: trees, rooted trees, spanning trees, breadth-first search, depth-first search (backtracking), minimal spanning tree,
• 5/29 Graph Theory: Kruskal's algorithm, Prim's algorithm, greedy algorithm, binary trees, planar graph, Euler's formula, Euler traversal, Euler circuits, Hamiltonian paths, Hamiltonian cycles
• 6/5 Graph Theory: Petersen graph, a sufficient condition to have a Hamiltonian cycle, shortest Hamiltonian path, Dijkstra's algorithm, network flows, max-flow and min-cut theorem
• 6/12 Graph Theorey: vertex coloring, edge coloring

Homework Assignments

• Set 1 (Due 3/13) p.4 #5; p.21 #13,14,15,17,19, 20, 22, 24, 25; p.48 #1,2,3,4; Read Sections 3.1 and 3.2 and do Check Yourself problems on p.62.
• Set 2 (Due 3/20) Group project p.71 # 4~10, p.74 #1,2,3, Prove that a tree must have a leaf. p.78 #1,2,5,6,7 p.85 #4,6,8.
• Set 3 (Due 3/27) Group project #1. Prove that R(3,4)=9. #2. Prove that removing an edge from a tree makes a forest with two components.#3. Finish Example 4.2.5 p.87 #13,14,15,17,18,24,25, p.100 Try this #1,3,5, Read Section 4.46
• Set 4 (Due 4/3) Group project #1. p.108 short activity 3. #2. Prove that every tree with at least one edge has at least two leaves. #3. p.145 Related problem. Read Section 5.4, p.146 #8,10,11,12,17,19,20 Read Sections 6.1 and 6.2 and do check yourself problems on p.156
• Suggested Problems: Problems in p.180
• Set 5 (Due 4/24) Group project #1. Compute the first 5 Catalan numbers and find a pattern. #2. Find a recurrence relation for Catalan numbers. #3. Compute the explicit formula for Catalan number. Prove that for all positive integers x, xn = sum_{k=0 to n} S(n,k)(x)k, where (x)k=x(x-1)(x-2)...(x-k+1). p.214 #1,3,5,7,9,11,13,15,17,19,21,24,25; Sections 8.1~8.3 and do check yourself problems in p.224 and p.228
• Set 6 (Due 5/1) Click here!
• Set 7 (Due 5/8) Click here!
• Set 8 (Due 5/22) Read Section 10.1 and 10.2 and do Check yourself problems in p.279
• Set 9 (Due 5/29) Group project #1. Read p.284~291 so that you learn Kruskal's algorithm and Prim's algorithm; Do check your self problems in p.292 #2. Read Section 10.8 and do check your self problems in p.303 p.306 #1,2,3,4,6,7,8,9,20,21. Prove that Kruskal's algorithm is true, that is, it produces a minimal spanning tree of a weighted connected graph.
• Set 10 (Due 6/5) p.307 #14,15,16,24. Prove Theorems 11.6.1~11.6.6 and do even numbered problems in p.328~p.331. (See the definition of thickness in p.322) Do the 2 problems given during class.
• Set 11 (Due 6/12) p.343 #1 in try this!; p.351 #1,2,3; p.354~359 odd numbered problems; maximum flow and min-cut problem (Section 4.2 Exercise #2, in Applied Combinatorics by Alan Tucker)
• Suggested Problems: Problems in p.386