**Math 154 Discrete Mathematics and Graph Theory, Winter
2018**

**Instructor:** Andrew Suk

**E-mail:** asuk [@] ucsd [dot] edu

**Time and Place:** PCYNH 122, MWF 1:00-1:50pm

**Office hours:** Mon/Wed: 2-3, and by appointment, APM 6210.

**Syllabus:** here.

**Textbook:** R. Brualdi, Introductory Combinatorics, 5th edition, Pearson Prentice Hall, 2010.

**Course Description:** The aim of this course will be to cover Chapters 2-8 and 11-13. Topics include: Permutations and Combinations, The Pigeonhole Principle,
Binomial Coefficients, Inclusion-Exclusion Principle, Combinatorial design, and Graph Theory.

**Grading:** Homeworks 10%, 2 Midterms 25% each, Final exam 40%.

**Exams:** Midterm 1 on Friday, Feb 2nd in lecture. Midterm 2 on
Friday, March 2nd in lecture. **Final exam: Friday March 23, 11:30-2:30
in
Lecture room**.

**Homeworks:** Homeworks will be due on Monday is your section class.

**TA's:** Nantawat Udomchatpitak, office hours: Wed 2-4pm and Thur
3-4:50pm in
APM 5801. Shubham Sinha, office hours: Thursdays 3-5pm in APM 5412.

**Extra office hours and review session:** I will be having office
hours
on Wednesday and Thursday, 3/21 and 3/22, from 2-3pm. Shubham Sinha will
have a review session on Thursday 3/22 from 6-7pm in AP&M B402.
Nantawat Udomchatpitak will have a review session on Wednesday
3:30-4:50 in AP&M B402A. He will also have office hours from 2-3pm
on
Wednesday 3/21 and from 3-5pm on Thursday 3/22.

Homework 1. Due Wednesday Jan 17 in lecture.
Chapter 2: 1, 2, 4, 7, 11, 13, 14, 21, 38, 39, 60. Solutions are here.

Homework 2. Due Monday Jan 22 in section.
Chapter 3: 4, 5, 17, 18, 20, 22, 27. Solutions are here.

Homework 3. Due Monday Jan 29 in section.
Chapter 5: 6, 7, 9, 15, 18, 23, 25. Solutions are here.

Practice test 1 can be found here.
Additional practice problems: Chapter 5: 30, 48.

Exam 1 solutions are here.

Homework 4. Due Monday Feb 12 in section.
Chapter 6: 1, 6, 12, 15, 17, 18, 19. Slides from 2/5 and 2/7 are here. Solutions are here.

Homework 5. Due Wednesday Feb 21 in **lecture**. Chapter 7: 4, 8, 9,
14,
16, 17, 24, 25. Solutions are here.

Homework 6. Due Monday Feb 26 in section. Chapter 11: 3, 5, 7, 12, 19,
30. Solutions are here.

Practice test 2 can be found here.

Test 2 solutions are here.

Homework 7. Due Monday Mar 12 in Section. Chapter 11: 39, 40, 42, 47,
53, 54, 55. Chapter 12: 4, 5, 6. Solutions are here. More details for Problem 11.54:
Consider a walk w:v_1,v_2,...,v_n that is a closed Eulerian trail.
It has n vertices since there are n-1 edges in G. Moreover,
since G does not contain a cycle, there are no repeated
vertices in the walk. Hence
the walk is P_n. Similar argument for 11.55.

Homework 8. Optional. Chapter 12: 13, 20, 23.

Practice final can be found here.

Final Exam Solution.

HW Score, 40 points: 40(HW1 + HW2 + ... + HW7)/70

**Total Score = 400 points**

**Version 1:** (HW score = 40) + (Test1 = 100) + (Test2 = 100) +
(Final = 160)

**Version 2:** (HW score = 40) + (Max(Test1,Test2) = 100) + (Final =
260)

My Spring 2018 office hours are M/W 11-12pm. Feel free to stop by if you
want to see your final exam.