Courses

Discrete Mathematics(이산수학)

Course Information

Textbook: A walk through Combinatorics by Miklos Bona (2nd Edition)

Classes: Mon.Tr 10:30am~12pm

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

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

Teaching Assistants: Choi, Whanhyuk (최환혁) whchoi@kangwon.ac.kr (Room 415 Tue 1~3pm)

Announcement

  • 시험성적이 연구실앞에 게시되었습니다. 성적에 이상이 있거나 의문이 있을시 6월 21일 연구실 방문을 하거나 이메일로 연락하십시오.
  • 6월18일 월요일 (10:30am~12:30pm, Room 420): Final Exam covers Generating functions and Basics in Graph Theory
  • 5월17일 목요일: Midterm 2 covers Chapters 6 ~ 8 중간고사해답.
  • 4월30일 월요일 수업은 5월 1일 화요일 5시 45분~7시로 옮깁니다. 9교시 수업이 있는 두 학생은 조금 늦어도 됩니다.
  • 4월26일 목요일: Quiz 2 covers Chapters 6 and 7. Quiz 2 해답
  • 4월16일 월요일 수업은 4월 17일 화요일 5시 45분~7시로 옮깁니다. 9교시 수업이 있는 두 학생은 조금 늦어도 됩니다.
  • 4월9일 월요일: Midterm 1 covers Chapters 1 ~ 5. Sample problems 정답 중간고사해답
  • 3월22일 목요일: Quiz 1 covers Chapters 1, 2 and 3.

Topics covered in class

  • 3/5 Chapter 1 Pigeon-hole Principle (with examples in the textbook and a couple of further examples such as "In a group of six people, there will be always three people that are mutual friends or mutual strangers.")
  • 3/8 Chapter 2 Mathematical Induction (We discussed all the examples in the textbook. Several more examples will be presented in the next class.)
  • 3/12 Problems that can be solved by using Pigeon-hole Principle or Mathematical Induction were further discussed. Chapter 3. Elementary Counting Method: Permutation n!, k-Permutation nPk (=n distinct objects list of length k)
  • 3/15 Chapter 3. Elementary Counting Method continued: k-Combination nCk(= k-element subsets of [n]), Combination with repetition allowed (=k-element multisets with elements from [n]), Permutation with repetition allowed(=permutations with ni objects of type i), Words of length k from n distinct letters
  • 3/19 Chapter 3 continued: Bijections, more exercise problems, Chapter 4 Binomial coefficients and Binomial Theorem
  • 3/22 Chapter 4 Quiz 1, Chapter 4 continued on Binomial Coefficients
  • 3/26 Chapter 4 continued on Binomial Coefficients, Multinomial Coefficients, General Binomial Coefficients
  • 3/29 Chapter 5 Compositions; Set partitions; Stirling Number
  • 4/2 Chapter 5 Bell number; Integer Partitions
  • 4/5 Chapter 5 Integer Partitions
  • 4/9 Midterm 1
  • 4/12 Chapter 6 Cylces in permutations; signless Stirling number of the first kind; Stirling number f the first kind
  • 4/17 Chapter 6 Inverse relations between Stirling numbers of the 1st kind and 2nd kind; permutations with restricted cycle structure
  • 4/19 More problems for Chapter 6; Chapter 7 Sieve
  • 4/23 Chapter 7 Application of Sieve formula
  • 4/26 Quiz 2
  • 5/1 Chapter 8 Ordinary generating functions; products of generating functions
  • 5/3 Chapter 8 Ordinary generating functions continued; partition generating functions
  • 5/7 Chapter 8 Exponential generating functions
  • 5/10 Chapter 8 Recurrence relations; Compositions of generating functions
  • 5/14 Chapter 8 Compositions of generating functions continued; more problems in Chapters 6~8
  • 5/17 Midterm 2
  • 5/21 Chapter 9~12 Graph Basics 1; vertex, edge, incidence, adjacency, loop, parallel edges, simple graph, complete graph, path, cycle, isomorphism of graphs
  • 5/24 Chapter 9~12 Graph Basics 2: isomorphism of graphs, walk, close walk, connected graph, component of graph, cut-edge, cut-vertex
  • 5/31 Chapter 11 ~p.252 (Graph Basics 3: bipartitie, complete bipartite, matching)
  • 6/4 Chapter 13 ~p.291 Graph Basics 4: deletion, induced subgraph, clique, independent set, introduction of Ramsey theory,
  • 6/7 Chapter 9 Graph Basics 5: Eulerian graphs, Hamiltonian cycles, Directed graphs
  • 6/11 Chapter 10 Graph Basics 6: Trees
  • 6/18 Final Exam

Homework Assignments

  • Set 1 (Due 3/8) p.11 #15,16,17,18,24,25 Solutions
  • Set 2 (Due 3/12) p.28 #22,25,27,30 Solutions
  • Set 3 (Due 3/22) p.51 #28,32,36,38,40,44 Solutions
  • Set 4 (Due 3/29) p.77 #29,30,32,33,40,48,53
  • Set 5 (Due 4/9) p.102 #16,17,20,21,23,24,26,28
  • Set 6 (Due 4/23) p.122 #26,28,29,31,32,33,35,41,42,43,46,47,48,49,50 Solutions
  • Set 7 (Due 4/30) p.139 #15,17,19,21,23
  • Set 8 (Due 5/17) p.169 #23,25,27,28,29,34,35,36,38,39,40,41,44,
  • For the week of 5/21 Suggested problems p. 196 #3,4,5(done in class),7(done in class),8,9,10,12,13,16,17,18,21(done in class)
  • For the week of 5/31 Suggested problems p. 260 #4,12,13,14.
  • For the week of 6/4 Suggested problems Show that R(1,k)=R(k,1)=1, R(2,k)=R(k,2)=k, for a natural number k. R(3,3)=6 as in the solution of Example 13.1 What about R(4,3) in Example 13.4? 그리고, 9장의 연습문제 나머지 (p.196~)
  • For the week of 6/11 Suggested problems A forest is a simple graph with no cycles. That is, each component of a forest is a tree. Try Proposition 10.6 and Corollary 10.9. p. 228 #9,10,11