Homework Assignments

Submit your homework through Gradescope by 11:59 pm on the due date.

Late submission will NOT be accepted!

These assignments and their due dates are subjected to revision during the term. Please check this page regularly for updates.

Homework 1 - Due Sunday October 06

Please do problems 1.5, 1.6, 1.7 (page 20-21), 2.9 and 2.12 (page 31) - PDF file

Notice: in this class, "graph" means simple graph with no loop and no multiple edge, unless indicated otherwise.

Homework 2 - Due Saturday October 19

Please do problems 2.4, 2.6, 2.13, 2.14 (page 20-21), 3.8 (page 31) - PDF file

Notice: there are additional parts (not in the textbook) for 2.4 and problem 2.6 has been altered.

Homework 3 - Due Sunday November 03

Please do problems 4.7, 4.12 (page 57-58), 5.7, 5.8, 5.13 (page 73) - PDF file

Notice:

• There is an additional part (not in the textbook) for 5.13
• For 5.7(b), do not use Dirac's Theorem!
• There is a typo in the current version of our textbook for problem 5.8. See the pdf file for the correct statement.

Homework 4- Due Saturday November 16

Please do problems 6.3, 6.9, 6.10, 6.11 (page 80-81) and 7.5 (page 98) - PDF file

Homework 5- Due Sunday December 08

Here is the PDF file. More exercises from Chapter 8 are coming over the weekend. Please check back later. The full assignment is now uploaded. There are FIVE problems in total.

Some clarifications:

• When you are doing the Art Gallery Problem on 5 or less faces, do not use the theorem!
• For Problem 1, you may use the fact that every orthogonal polygon has a convex quadrilateralization
• For Problem 4a, list all the possible flow values. Then for each value, give an example of the assignment on the arcs.

"Homework" 6 - Do not turn in

HERE are some nice problems that you can try.