Statistics updated: all homework and tests (6-3, 1:00am)
Midterm posted (6-2, 1:40pm) DO: solve the problems by Thursday. YES, there will be class on Thursday.
Theorems covered handout (incomplete)
Problem session with instructor Monday, June 1, 4:30-5:20 pm, Ry-276. Optional; will help you prepare for the test. Come prepared with your questions.
Homework set #14 posted. Due Thursday, May 28. (Most problems have been assigned in class.)
No formal homework for Thursday, May 21. However, do solve the Quiz-4 problems and the exercises stated in class, including studying the Prüfer code to count the spanning trees of $K_n$.
Quiz-4 posted. Solve the problems on your time.
Problem session with instructor Monday, May 18, 4:30-5:20 pm, Ry-276. Optional; will help you prepare for the next quiz. Come prepared with your questions.
Homework set #12 posted. Due Thursday, May 14.
Quiz-3 statistics posted (May 12), approximate grade equivalents posted with quiz and HW statistics
HW statistics updated (May 7)
Problem session with instructor Monday, May 11, 4:30-5:20 pm, Ry-276. Optional; will help you prepare for the next quiz. Come prepared with your questions.
HW announcement (May 6): There will be no new HW due tomorrow (May 7). Please review class material (definitions, theorems, proofs) and the DO exercises of recent weeks, and also the problems on past quizzes.
Homework set #11 posted. Due Tuesday, May 12.
Quiz-3 posted.
Homework set #10 posted. Due Tuesday, May 5.
Problem session with instructor Friday, May 1, 3:30-4:30 pm, Ry-277. Optional; will help you prepare for the next quiz. Come prepared with your questions.
Homework set #9 posted. Due Thursday, April 30.
Homework set #8 posted. Due Tuesday, April 28.
Statistics updated
Homework set #7 posted. Due Thursday, April 23.
Quiz-2 posted. Solve the problems on your own time by Thursday's class (Apr 23).
Homework set #6 posted Due Tuesday, April 21.
Homework set #5 posted Due Thursday, April 16.
Homework set #4 posted (First batch: 4-9 8am, full set 11:30pm). Due Tuesday, April 14.
Quiz-1 and HW statistics posted.
Quiz-1 posted. Solve the problems on your own time by Thursday's class (Apr 9).
Test dates and grade breakdown have been posted.
Homework set #2 has been posted (4-2 8:30pm). Due Tuesday, 4-7, before class. Recall: there will be a quiz on Tuesday.
Homework set #1 has been posted (3-31 5pm). Due Thursday, 4-2, before class.
The rules and policies (last four sections on this page, starting with "Rules on HOMEWORK") have been significantly updated at 2:24 am on 3/29.
Please send email to the instructor with answers to these questions, even if you are only sitting in on the class, did not register, or have an unusual status. Your answers to these questions will help me better to plan the course. Please write "CMSC 27500 data" in the subject.
Description will be entered here.
Prerequisites: This is a heavily proof-based course, so the key prerequisite is that you be comfortable with mathematical formalism, proofs, and the discovery of proofs on your own. Most homework and test problems will ask you to prove something.
Formal prerequisites: analysis (Math 20400) or Discrete Mathematics (CMSC 27100) or consent of instructor. In particular, facility with limits and the basics of counting, discrete probability, and number theory expected. Linear algebra will be used occasionally and is only required if you aspire for an A.
Office hours: by appointment (please send e-mail)
TAs: Kai Li
lik11 [at] CS [dot] etc
Hing Yin (Joseph) Tsang hytsang [at] CS [dot] etc
Classes: TuTh 12:00 - 1:20, Ry-251
LAST CLASS: Thursday, June 4. Attendance required if you want a letter grade.
Your primary text will be your course notes, so please make sure you don't miss classes. If you do, you should copy somebody's class notes and discuss the class with them.
Main text:
J. A. Bondy and U. S. R. Murty: Graph Theory with Applications.
Print copy recommended but you can also find it online.
Additional printed references:
Douglas B. West: Introduction to Graph Theory. Prentice - Hall 1996, 2001.
J. Matoušek, J. Nešetříl: Invitation to Discrete Mathematics, published by Oxford University Press, ISBN# 098502079.
This is a beautiful introduction on the advanced undergraduate level.
(Note: the second edition of this text appeared in 2009. You may also use the first edition. The numbering of chapters has changed; I will post the correspondence when explicit reference is made.)
L. Lovász: Combinatorial Problems and Exercises.
This is a treasure trove of advanced problems that lead to central
theorems.
Reinhard Diestel: Graph Theory. Springer, 1997 (graduate text)
Online references:
Tero Harju "Lecture Notes on Graph Theory" (2007) (too easy)
Lex Schrijver: "Advanced Graph Theory" (too hard)
Instructor's Discrete Mathematics Lecture Notes (PDF) includes Graph Theory terminology and exercises; it also includes the basics of Finite Probability Spaces and Asymptotic Notation, relevant for this course
Instructor's DM Lecture Notes by Morgan Sonderegger and Lars Bergstrom (PDF) (detailed notes based on the 2007 DM class, but not proofread by instructor)
Lecture notes on linear algebra and spectral graph theory by Madhur Tulsiani and the instructor, REU 2013 for rising 2nd-years
Problem sheets from instructor's 2012 REU course for rising 2nd-years
(including linear algebra problems and "puzzle problems")
Basic prerequisites can be found in this book:
Kenneth H. Rosen:
Discrete Mathematics and its Applications
(n-th edition, n=2,3,4,5,...).
This is a basic-level introductory text.
The foundations of logic, proofs,
basic number theory and counting covered in
this text are assumed in this course.
This course is considerably more advanced than
the level of Rosen's book, but some students
may find some chapters of Rosen helpful; if so,
solving many problems from Rosen's relevant chapters
is the best way to fill those gaps in your background.
Grades are based on homework, tests, and class participation. Homework contributes 27% to your grade, the first quiz 5%, three more quizzes 7% each, a midterm 42%, class participation 5%.
The tests are closed-book; no notes permitted. The use of electronic devices is strictly forbidden.
April 7 Tuesday: first quiz
April 21 Tuesday: second quiz
May 5 Tuesday: third quiz
May 19 Tuesday: fourth quiz
June 2 Tuesday: midterm
(There will be no final exam.)
LAST CLASS: Thursday, June 4. Attendance required if you want a letter grade.
HW set #14 (due Thursday, May 28)
HW set #13 (due Tuesday, May 19) Posted 5-15 3:45pm.
HW set #12 (due Thursday, May 14) Posted 5-12 8:15pm.
HW set #11 (due Tuesday, May 12) Posted 5-8 10pm.
HW set #10 (due Tuesday, May 5) Posted 5-1 12:30am.
HW set #9 (due Thursday, April 30) Posted 4-28 2:40pm.
HW set #8 (due Tuesday, April 28) Posted 4-25 11:20am.
HW set #7 (due Thursday, April 23) First batch posted (4-22 1:30am).
HW set #6 (due Tuesday, April 21) First batch posted (4-17 4:20am).
HW set #5 (due Thursday, April 16) Posted (4-14 5:30pm).
HW set #4 (due Tuesday, April 14) first batch posted (4-9 8am, update 10:20am). Due Tuesday, April 14. More problems will be added.
("HW set #3" will refer to those problems on HW set #2 that are due April 9.)
HW set #2 (due Tuesday, April 7)
HW set #1 (due Thursday, April 2)
Errors may occur, so please recheck the website. If you suspect an error, please notify the instructor (by email) right away. If you are the first to point out an error, you may receive bonus points.
Problems come in several categories.
"DO" exercises are meant to check your understanding of the concepts. Do them but do not hand them in. If you encounter any difficulties, please let the instructor know by email.
"HW" indicates ordinary homework problems that you need to hand in.
"Bonus problems" also carry point value and have the same deadline as ordinary homework but they are not mandatory. Their point value is underrated so do the ordinary homework first. To get an "A" in this course, you need to collect at least 1/3 of the bonus homework points, and at least 1/5 for an A-.
"Challenge problems" don't have a specific deadline except they cease to be assigned once they have been discussed in class. If you are working on a challenge problem, please send email to the instructor so as to avoid discussion of the problem before you handed in the solution.
Solutions to Challenge problems earn you some bonus points, but they are significantly underrated. However, they do earn you the instructor's respect, in addition to giving you valuable experience. If at some point in the future you need a letter of recommendation, challenge problems you solve will be the primary reference.
Partial credits. On ordinary homework, a reasonable effort will typically result in partial credit. The grading of bonus problems and challenge problems is stricter, effort does not guarantee partial credit unless your work represents a significant part of a correct solution. Moreover, for bonus problems and challenge problems, only mathematically accurate work will earn partial credit. For Challenge problems, you may ask the instructor for a hint; the cost of a hint is reduced point value. Use of web-sources that explicitly solve the problem assigned or an essentially equivalent problem also results in reduced credit, see below.
Collaboration on current homework is discouraged but not prohibited. If you do collaborate, state it at the beginning of your solution (give name of collaborators, nature/content of collaboration) and mark inside the solution if an idea is not yours. Please also send email to the instructor with the same collaboration information (to make it easier for the instructor to keep track of collaborations). Please write "HW#6 collaboration" in the Subject line for HW set #6 (where, in the tradition of the ancient Greeks, "6" is a symbol for a variable; substitute the correct value). There is no penalty for acknowledged collaboration on homework as long as it does not amount to copying. DO NOT COPY someone else's solution: after the discussion, throw away any written records. Understand the ideas discussed and give your own rendering. Sharing hand-written or printed drafts or electronic files containing solutions or significant parts of solutions before submission is strictly prohibited, and will be regarded academic dishonesty.
The requirement to report sources also applies to other sources (books, the web, etc). Acknowledge all sources both in the paper and in email to the instructor. (Write "HW#6 collaboration/sources" in the Subject if you report both collaboration and sources.) See the policy on the web sources below.
The web is a useful resource but you need to read it critically: it often has errors, it often makes things look more complicated than they actually are, the web article may be targeted to a very different audience and with very different goals, and the terminology may differ from the one used in class.
The use of the web to track down solutions to homework problems is strongly discouraged. This is counterproductive; it denies you the experience of learning by discovery that this course tries to impart.
The web by now is so rich that it is virtually impossible to avoid assigning problems to which solutions are found on the web. The instructor retains the right to reduce the point value of problems during grading if it turns out that solutions exist on the web in cases when the instructor was not aware of the availability of such a solution.
While studying relevant material on the web is ok, looking up explicit solutions on the web to problems essentially identical with those assigned is considered an abuse of the web. Unfortunately to many of the most elegant and instructive problems, you can find solutions on the web. Tracking them down is not prohibited but here are the rules: