Second Test

Mathematics 61

• Classes since the first midterm.
• The twelve sections of the textbook from which we have homework problems:
  • Introduction (to graph theory).    Paths and Cycles.   
  • Hamiltonian Cycles and the Traveling Salesperson Problem.   
  • A Shortest-Path Algorithm.   
  • Representation of Graphs.    Isomorphisms of Graphs.    Planar Graphs.   
  • Introduction (to trees).    Terminology and Characterizations of Trees .   
  • Spanning Trees.    Minimal Spanning Trees.    Isomorphism of Trees (to page 305 or 423).   
• Problem Set IV, Problem Set V, Problem Set VI, and Problem Set VII (answers are posted on the due dates).
• The supplementary webpage on Complexity of Decision Problems.

The general format will be similar to the first test.   The test will be mostly like the homework.   Like the homework, the test can ask both for calculations and for proofs.   (We want you to be able to reason with these concepts.)   The test can also ask for definitions.

Ground rules: Paper will be provided.   Bring pencil and eraser.   No calculators.   Closed book.   Please bring your photo ID to the tests.

Note that on Monday, I have my usual office hours.   In addition, I will hold a session for questions and problems on Tuesday (November 27) at 5:30-6:30 p.m., in Franz 2258A.   And of course our VOH site is always available.

We plan to return the tests in discussion sections December 4 and 6.

Click here for a practice test.

The maximum possible score was 100 (see the answers for the number of points for each problem).   Grades are posted on my.ucla.
mean = 81.7
median = 90.

Click here for answers to the test in pdf format.