Syllabus

Course Description

This is the introductory course to Graph Theory. Topics included: trees, walks, paths, and connectivity, cycles, matching theory, vertex and edge-coloring, planar graphs, flows and combinatorial algorithms, covering Hall’s theorems, the max-flow min-cut theorem, Euler’s formula, and the traveling salesman problem.

Prerequisites: MATH 31CH or MATH 109. Students who have not completed listed prerequisites may enroll with consent of instructor.

Textbook: We shall use the textbook by Professor Jacques Verstraete, available HERE. There is also a reference book by Robin Wilson available HERE

Important: Credit not offered for MATH 154 if MATH 158 is previously taken. If MATH 154 and MATH 158 are concurrently taken, credit is only offered for MATH 158.

Other Resources: For this class, we shall use Piazza (LINK) which is a forum (monitored by the instructional staff) for students to ask, answer, and share their resources for this class. In addition, we also use Gradescope (LINK) to manage homework assignments and exams.

Homework (20% of your course grade)

First and foremost, late homework will not be accepted and there will be no exception to this rule. If you fail to submit your homework before the deadline, then you will automatically receive a zero for that assignment. Please do not contact the instruction staff to ask for leniency!

There will be five (5) assignments in total. Homework assignments are posted on the class website under the “Assignments” tab, and due at 11:59pm on the indicated date through Gradescope.

Before the deadline, you may submit as many copies of your homework paper as you would like; however, only the most recent submission will be considered. We strongly encourage that you type your solution. Handwritten papers should be legible or your homework may not be graded. The scores and solutions to these problems will be available on Gradescope and TritonED.

Homework may be done in groups of one to three students. You are free to change group members at any time throughout the quarter. Problems should be solved together, not divided up between partners. Each group only need to submit one copy of their homework. Please remember to indicate the names of all group members in your submission.

Exams (80% of your course grade)

There will be two in-class midterms and one in-class final. No textbook, notes, calculator, or any other electronic devices will be allowed. The midterms will take place in during regular lecture times.

There will be no make up exam! It is your responsibility to ensure that you do not have a schedule conflict involving the exams.

The first midterm will be held on Monday, October 21 (Week 4), covering topics from Weeks 0 to 3
The second midterm will be held on Monday, November 18 (Week 8), covering topics from Weeks 4 to 7
The final exam will be held on Wednesday, December 11, 11:00am - 2:59pm, location TBA, covering all materials from the course.

Grade Policy

Your grade will be based on the scores of the homework assignments, two midterms, and the final exam. It will be the maximum of the following two scores (namely, you may replace the lower midterm score with that of the final) :

Score 1 = 20% HW + 25% 1st Midterm + 25% 2nd Midterm + 30% Final
Score 2 = 20% HW + 25% Best Midterm + 55% Final

You must pass the final examination (scoring at least 50%) in order to pass the course. Since there is no makeup exam, if you miss a midterm exam for any reason then your course grade will automatically be computed using the second method. The letter grade you receive at the end of the course will be based on the following scale:

The final scores may be adjusted to determine the letter grades. However, the letter grade corresponding to a given percentage will never be lower than specified by the above scale.

Regrade Policy

The scores for the individual assignments are available on WebAssign shortly after the due date. In addition, we shall scan and grade your exams using Gradescope. All graded exmas will be posted on Gradescope and later on TritonED.

If you find an error/inconsistency on any graded exam, you must immediately request a regrade through Gradescope. All regrade issues must be resolved within THREE DAYS after the score is published. Once the three-day period is over, the score will become final and any late requests will not be considered.

Only the grades posted on TritonED will be computed toward your final score percentage. You must keep all of your graded materials and check TritonED frequently to make sure that the grades on your Gradescope page match those recorded on TritonED. If there is any inconsistency in the recording of your scores, you must inform the instructor or TA before the end of the quarter to resolve recording errors. Questions regarding missing or incorrectly recorded scores will not be considered after Saturday, December 14.

Academic Honesty and Attendance Policy

As a student of UC San Diego, you have agreed to abide by the university’s academic honesty policy. Academic integrity violations will be taken seriously and reported immediately. Violation of such policy may result in failing the class, suspension, and even expulsion from the university. Students are expected to attend classes regularly. Cell-phone and all electronic devices must be turned off during lecture time, unless being used for taking note. A student who is absent for an excessive amount of times may be dropped from the class. Further information regarding Academic Integrity policy are available under the "Links" button above. You should make yourself aware of what is and is not acceptable by reading this document. Ignorance of the rules will not excuse you from any violations.

Key facts about academic integrity related to our course:

Do not discuss homework problems with people besides your homework partner(s) (except during office hours, with the instructional team).
Do not search for solutions to old homework and exam problems.
Do not share written solutions or partial solutions with other groups.

Accommodations

Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities (OSD). If you have an AFA letter, please schedule an appointment with your instructor within the first three days of class to ensure that reasonable accommodations can be arranged. For more information, see HERE.

Report abuse