COMPSCI 575 – Combinatorics and Graph Theory – Fall 2024
UMass Amherst – Manning College of Information and Computer Sciences
Syllabus: class taught by Mark C. Wilson
All my syllabi should be read in conjunction with my standard FAQ for students.
LOGISTICS
- Course: COMPSCI 575 (SPIRE numbers 36132, 36133, 36708)
- Official description: This course is a basic introduction to combinatorics and graph theory for advanced undergraduates in computer science, mathematics, engineering and science. This course counts as an elective toward the CS Major. Open to juniors and seniors. Undergraduate Prerequisites: either COMPSCI 250 or MATH 455 with a grade of B or better. Modern Algebra – MATH 411 – is helpful but not required. 3 credits. Note: also open to graduate students and cross-listed (MATH 513).
- Online resource pages: Canvas (https://umamherst.instructure.com/courses/15952) ; Gradescope (access code VDBEX6) ; Piazza (see enrollment email, access code 1gjulho3y8x) ; ClassQuestion.com (make a free account with your official UMass name and email, class code BRCSQ)
- Lecture meeting times/places: see SPIRE (they can change a lot around the beginning of the semester).
TEACHING TEAM
- Instructor: Mark Wilson (he/him) ; office LGRC A217H ; email markwilson@umass.edu (only use if Piazza is not working for some reason); regular office hours Tu 230pm, Th 10am, in person, also on Zoom (https://umass-amherst.zoom.us/j/93565025289).
- Teaching Assistant: Amirmahdi Mirkhanfar ; office hours M 4-5pm, W 5-6pm, on Zoom (https://umass-amherst.zoom.us/j/2540548482)
COMMUNICATION
Details of office hours will be announced on Piazza by the first week of classes. Talking to the instructor immediately before/after lecture is usually very effective. Instructions on how best to use Piazza will be distributed by the first week of classes – it is important to follow those guidelines. We will not use individual instructor or TA/UCA emails – everything should be done via (private, if necessary) message (to “instructors” which means the instructor and TAs) on Piazza.
It is important to follow these procedures, so that your message is properly answered. For all questions involving course logistics and grading, and for special requests (excused absences/make-up exams) contact the teaching team via Piazza.
CONTENT
Topics covered include: elements of graph theory; Euler and Hamiltonian circuits; graph coloring; matching; basic counting methods; generating functions; recurrences; inclusion-exclusion; and Polya’s theory of counting. We will first cover core material thoroughly and then discuss more advanced topics as time permits.
A student passing this course should be able to:
- choose an appropriate basic counting technique to solve problems stated in words
- convert between recurrence relations and generating functions in each direction
- solve counting problems with a recursive nature via generating functions
- solve counting problems using Polya counting techniques
- fluently use the language of graph theory to model problems involving binary relations
DELIVERY
There are two scheduled 75-minute lectures per week, given by the instructor. Lectures are recorded and linked from Canvas. Lecture slides will be made available after each lecture with at most 48 hours delay, and usually much sooner. There is a recommended (but not required) textbook: A Walk through Combinatorics by Miklós Bóna (5th edition, although earlier editions will still be useful). Some copies will be available from the UMass library for short-term loan. Other resources may be available from Canvas.
ASSESSMENT
- Examinations: 1 midterm written exam (15% of final marks; date 7-9pm Oct 10; room ILC110), final written exam (35%, covers entire course but weighted more on 2nd half; 1030-1230 Dec 18, location TBA). The final exam date/location can be deduced from here: https://www.umass.edu/registrar/spring-final-exam-matrix
- Homework assignments and quizzes: 6 written homework assignments (40% total) . The lowest score will be dropped. Assignments are typically due about every two weeks on Sunday just before midnight, and released about a week before the due date.
- Participation: lectures (including online questions) up to 7%, Piazza up to 7% (10% total, so getting the maximum score is fairly easy), determined by metrics and teaching team judgment (all decisions are final and not subject to appeal).
- I do not usually give extra credit opportunities.
Most grading will be done via GradeScope and requests for regrading (because of an error by a grader) must be made on GradeScope within a week of the graded assessment item being returned. There is a deadline of two days before the final exam for students to ensure that all their other course marks are correctly recorded in Canvas.
Final grades for the class will be determined by mapping the final marks to letter grades, with no rounding, using a system to be determined later (since this is the first time I have taught the course, I need to calibrate expectations, but it will be similar to a standard UMass grading scale). But also, in order to pass the class, each student must receive a passing grade on the examinations section. Individual course assignments may be scaled if the difficulty level was inappropriate for the class. There is no preassigned final grade distribution – it is possible for everyone to get an A.
SCHEDULE (approximate, since this is the first time I am teaching the course)
| Week | Lecture 1 | Lecture 2 | OTHER |
|---|---|---|---|
| 1 | Introduction | Basic counting methods | |
| 2 | Basic counting methods | Basic counting methods | HW1 due |
| 3 | Inclusion-exclusion | Cycles in permutations | |
| 4 | Generating functions | Generating functions | HW2 due |
| 5 | Generating functions | Generating functions | |
| 6 | Graph basics | Graph basics | HW3 due |
| 7 | No class (Columbus/IP Day) | Trees | |
| 8 | Matching and coloring, bipartite graphs | Overflow: graphs, trees, matching, coloring | |
| 9 | Group actions and counting | mvGFs and probability | HW4 due |
| 10 | No class (Election Day) | Moebius function of a poset | |
| 11 | Lagrange inversion | Catalan bijections | HW5 due |
| 12 | Matrix tree theorem | Planar graphs | |
| 13 | Analytic combinatorics (not examinable) | No class (Thanksgiving) | HW6 due |
| 14 | Problem session, exam review | Problem session, exam review | |
| 15 | No class | No class |
SPECIFIC CLASS POLICIES
These will be announced on Piazza by the first week of classes, and will deal with make-up exams, excused absences, rules of student conduct in class and online, etc. It is very important to read them.
UMASS POLICIES
Equity and Inclusion Statement
We are committed to fostering a culture of diversity and inclusion, where everyone is treated with dignity and respect. This course is for everyone. This course is for you, regardless of your age, background, citizenship, disability, education, ethnicity, family status, gender identity, geographical origin, language, military experience, political views, race, religion, sexual orientation, socioeconomic status, or work experience. We bring different skills to the course and we will all be learning from and with each other. We respect everyone’s right to be addressed by the name and pronouns that they choose. You can indicate your preferred/chosen first name and pronouns on SPIRE, which appear on class rosters. A student’s chosen name and pronouns are to be respected at all times in the classroom.
In both live and online settings we all are expected to uphold and promote a welcoming environment for learning. Politeness, kindness, and tolerance are expected at all times. Respect that people have differences of opinion, and work and approach problems differently. Please keep unstructured critique to a minimum and make sure that any criticism is constructive. Try and be aware of your own biases and avoid micro-aggressions. Listen to others and let them participate; ask yourself whether you are dominating a conversation and not giving others a chance to contribute. Disruptive behavior is not welcome, and insulting, demeaning, or harassing anyone is unacceptable. We follow the university’s guidelines for classroom civility. In particular, we don’t tolerate behavior that excludes people in socially marginalized groups. If you feel you have been or are being harassed or made uncomfortable by someone in this class, please contact a member of the course staff immediately, or if you feel uncomfortable doing so, contact the Dean of Students office.
Academic Honesty Policy
The Association of Computing Machinery (ACM), the world’s largest professional computing society, has released a Code of Ethics, and with good reason. Given the dominant role of computer technology in our society, ethical lapses can have disastrous consequences. Ethical behavior begins here at UMass. The following discussion pertains to academic honesty from the perspective of this course.
All work submitted must be your own in presentation. How much outside help is allowed depends on the course component.
- For quizzes and exams, no outside help or use of materials from prior years is allowed. Any cheating on a quiz or exam is grounds for an F in the course.
- You may discuss homework with other students, in fact we encourage this as a learning experience. But again, the writeup must be your work. Copying is not allowed, and collaboration so close that it looks like copying is not allowed. In general, if we receive two identical homeworks we will accept neither of them (i.e., both get F’s) and will give you a stern warning that could lead to formal action the next time. A good practice is to divide your work into an “ideas phase” where you collaborate and a “writeup phase” where you work alone — enter the writeup phase with notes, but not written solutions.
- All work submitted by students will be generated by the students themselves, working individually or in groups. Students should not have another person/entity do the writing of any substantive portion of an assignment for them, which includes hiring a person or a company to write assignments and using artificial intelligence tools like ChatGPT.
- If you make use of a printed or on-line source for the homework, other than specific course materials such as the textbook or website, please mention it in your writeup. Of course copying a solution to a problem from the web is cheating, and this is easier for us to detect than you might think.
- As per CICS policy, no student shall post course materials online without explicit permission of the instructor. Nor shall a student provide course materials to a third party such as StudySoup or Chegg.
- For more information about what constitutes academic dishonesty, please see the Dean of Students’ website for the general UMass academic honesty policy. Since students are expected to be familiar with this policy and the commonly accepted standards of academic integrity, ignorance of such standards is not normally sufficient evidence of lack of intent. You can take a quick online quiz to check your “academic integrity quotient (AIQ)”.
Copyright
Our lectures and course materials, including slides, videos, assignments, tests, outlines and similar materials, and all course recordings, are protected by U.S. copyright laws and by university policy. We are the exclusive owner of the copyright in materials we create. You may take notes and make copies of course materials for your own use in this class. You may also share those materials with another student who is registered and enrolled in this course. You may NOT reproduce, distribute, upload, or display any lecture notes or recordings or course materials in any other way — whether or not a fee is charged — without the instructors’ express written consent. If you do so, you may be subject to disciplinary action under the UMass Code of Student Conduct. Similarly, you own the copyright to your original papers and exam essays. If we are interested in posting your answers or papers on the course web site, we will ask for your written permission.
Disability Statement
The University of Massachusetts Amherst is committed to making reasonable, effective and appropriate accommodations to meet the needs of students with disabilities and help create a barrier-free campus. If you are in need of accommodation for a documented disability, register with Disability Services to have an accommodation letter sent to the instructors. It is your responsibility to initiate these services and to communicate with the teaching staff ahead of time to manage accommodations in a timely manner. For more information, consult the Disability Services website.
Title IX Statement
UMass is committed to fostering a safe learning environment by responding promptly and effectively to complaints of all kinds of sexual misconduct. If you have been the victim of sexual violence, gender discrimination, or sexual harassment, the university can provide you with a variety of support resources and accommodations. If you experience or witness sexual misconduct and wish to report the incident, please contact the UMass Amherst Equal Opportunity (EO) Office (413-545-3464 | equalopportunity@admin.umass.edu) to request an intake meeting with EO staff. Members of the CICS community can also contact Erika Lynn Dawson Head, director of diversity and inclusive community development (erikahead@cics.umass.edu | 860-770-4770).