Final Exam Postmortem

Math 61 -- D. C. Smolarski, S.J.
Winter 2000
Santa Clara University, Department of Mathematics and Computer Science

[Return to Math 61 Homepage]
REMINDER: It is my policy to keep all finals for one quarter. You may have them at the beginning of June 2000. But you examine them and ask questions about my grading of them at any time. The answer key is posted outside my office.

Problem References

  2. Cf. HW Y-1 (2nd definition) (cf. DCS sec 11.3)
  4. Cf, HW K-6
  6. HW, V-1, V-2
  7. Midterm II
  8. Cf. HW, T-3
  9. Midterm I
  11. Cf. HW, M-1
  14. Cf. HW, Q-1
  17. Cf. Notes D
  18. Part a, Cf. HW P-1
  20. Cf. HW, O-2 (DCS sec 10.6)

NOTES:

General: I mentioned that "about half" of the problem would be based on the material not yet tested upon, that is, on the material from around the second Midterm. There were 8 problem (of the 20) based on such material, problems 2, 6, 8, 11, 14, 18, 19, 20. In addition, problems 1a and 12b were also based on this untested material.

Prob 1: (sec. a) An "almost-complete binary tree" must have both children if it has any. At each level other than level zero, the number of nodes (or leaves) must be even. Thus, added to the root node, the number of nodes is odd.

Prob 5: Many people did not understand and use the functions correctly, as given.
Several people had code which almost worked, but resulted in an infinite loop in trying to remove the last item from the queue.
The ideal, quickest solution, is as follows: in the first loop, successively, the smallest item remaining in the queue is pushed onto the stack, until nothing remains in the queue. Then, in the second loop, all items in the stack are popped off and entered one by one into the queue again. Since the smallest item was the first into the stack (and the largest the last), the first item into the queue is the largest and the last the smallest.
A few people, for some reason, included output statements.

Prob 11: Several people seemed not to remember the meaning of "lexicographically ordered" tree, and inserted elements as if they were constructing a heap.

Prob 8: Since the graph is directed, it would normally NOT be symmetric, and thus one would need both upper half and lower half (with respect to the diagonal). Also, since NO self-loops are allowed, the diagonal is NOT needed.

Prob 10: This splits the original lists into two lists.
Even though the problem explicitly mentions an "even" numnber of nodes, some people spoke about lists with an "odd" number of nodes.

Prob 13: Some people did not try to code this as a RECURSIVE routine, i.e., write the code so that "flip" calls "flip" with a different argument.
A few people, for some reason, included output statements.
Several people used treenode as if it were an identifier (variable) or the function name rather than a data-type. Some people forgot how to use the -> symbol to indicate the subsections of a pointer variable.

Prob 17: Many people seemed not to remember the information about priority queues. The concerns about a queue were that (1) one did not move items (if this could be avoided), and (2) one did not leave "gaps" in the array between the known first and known last items.
Thus, the standard "array" (rather than "heap") implementation was to insert items from the rear (but that meant putting them as close to the first location as possible!), and if any item is deleted, merely moving the last item to "plug" the hole left by the deleted item.
At no point should there be "hole" in the array of queue elements, nor should the low number indices (e.g., 1, 2, ...) be empty when there are elements in the queue.

Prob 18: Some people forgot that when given a forest, one links the roots of the individual trees together when transforming them into a binary tree by Knuthian natural correspondence.

Statistics

Scores, raw and normalized 
      final   nfinal
	231	  75
	228	  71
	225	  73
	221	  68
	209	  60
	203	  57
	196	  52
	195	  51
	188	  47
	184	  44
	184	  44
	181	  42
	172	  36
	169	  35
	154	  25
	146	  20

MAXIMUM 300      100

Distribution

             x
             x
             x         x
             x         x
   x    x    x    x    x
   x    x    x    x    x
  140- 160- 180- 200- 220-
  159  179  199  219  239

Number of Perfect Scores per Problem

  1. 2/16
  2. 9
  3. 1
  4. 7
  5. 0 Tie for "Hardest"
  6. 2
  7. 6 (on Mid II, 4/36)
  8. 3
  9. 11 (on Mid I, 14/37)
  10. 0 Tie for "Hardest"
  11. 8
  12. 15 "Easiest"
  13. 1
  14. 10
  15. 10
  16. 9
  17. 2
  18. 7
  19. 14
  20. 7

This page is maintained by Dennis C. Smolarski, S.J. dsmolarski@math.scu.edu
© Copyright 2000 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 19 March 2000.