Midterm 1 Postmortem

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

Problem References

1. (In class demos of "symbol table" -- translation of binary "words" to positive and negative integers as in HW A-2, A-3.)
2. Essentials Vol I, Sec 4.4, pp 31-32.
3. cf HW B-1a, B-2a. Use "subcript" rule, given in Essentials Vol I, Sec 3.4, pp 19-20.
4. (This is mainly a test of how well one can intepret loop and if statements which also involve stack commands.)
5. HW F-1, F-2
6. HW E-3
7. (In class discussion of efficiency of Selection Sort -- O(n²) algorithm (comparisons), cf. Essentials p. 31.)
8. HW X-1, Essentials Vol I, App B, pp 95-96
9. HW E-4b
10. HW D-4

NOTES:

Some people used SIGN MAGNITUDE to interpret the negative numbers rather than ONE'S COMPLEMENT (as mentioned in the instruction).

Some people did not make reference to the "Symbol table" to intepret how the binary word should be translated -- i.e., whether the memory location referred to an integer or a character. Some people merely "printed out" the binary code.

Prob 2: Although stable sorts are most useful when resorting an already sorted array, a stable sort is not defined only in terms of a second sorting.

Prob 3: Some people used the C++ (row -- "last subscript varies fastest") rule rather than the FORTRAN (column -- "first subscript varies fastest"). In my mind (as I mentioned in class one day when discussing the homework problem), the subscript rule is the only one that always works in every dimension and is the easiest to understand.

This presupposes that a person can write down all the possible subscripts correctly, in order, without omitting any! The most difficult aspect of this problem seemed to be being able to write down all the subscripts in proper order.

Some people got confused with the maximum subscript value -- if the number of elements in some dimension is 2 or 3, then 2 sor 3 CANNOT be used as a subscript value.

Prob 4: Many people could not interpret the code correctly -- it seemed that some individuals put several items on the stack at the same time when only one was indicated.

A great number of people only put a few items on the stack rather than the 7 that the code does.

Prob 5: In part c) several people wrote out an INFIX answer rather than the requested POSTFIX answer.

Prob 6: I spoke about design issues related to implementing stacks in class one day, and that it was not really necessary to start storage in location 0. It was just as easy to start storage at the last location (in this case in place N-1).

I also spoke about the design issue of whether the "top-of-stack" pointer should point to the "last location used" or "next location available."

In the problem the code indicates that the top-of-stack pointer points to the "next location available" and, since it is decreased during a push, the first element must be placed in S[N-1].

Prob 7: The majority of work for straight selection is in the comparisons made at each pass which is of order O(n²) (the same as with bubblesort). As with the example in class, one computes a machine constant for the method using the information given (4 seconds and 50 items), and then uses that constant to determine the time for a 250 item array. Alternatively, since 250 is 5 times 50, the time should be 5² = 25 times the time it takes for 50 items, i.e., 25 times 4 or 100 seconds.

Prob 8: Many people got Problem 8 wrong because of misinterpreting the basic code.

Some people interchanged the values of m and n.

More people miscomputed the second assignment in function mystery:

    i = i+j
    p = i+k

Prob. 9: The assumption (as in examples in Essentials) is that all the input characters should end up in the output. The limitation is that only two characters could be on the stack at any one time.

Each possible output should have the same number of characters as in the input stream, namely 3, but the restriction is on the number of elements on the stack. Since 3 elements could not be on the stack at the same time, one could NOT have the output CBA (which would require all three to have been on the stack together!).

Prob. 10: Linear search (worst case) timing is n comparisons (where n is the length of the array). In this case the answer is 4096.

Binary search (worst case) timing is log₂n (or twice this depending on how one determines the comparisons in the implementation of binary search). In this case the answer is 12 (or 24).

Linear search ALWAYS will work. If the list were not sorted, it is a very viable option to sort the array first and then use binary search (which cannot be used on an unsorted list since it presupposes order).

Statistics

• High score: 80
• Low score: 23
• Range: 57 pts
• Median (middle score): 46
• Mean (average score): 49.89474
• Standard Deviation: 16.37374
• Number who took exam: 19

Distribution

           x
           x
           x
   x       x       x
   x   x   x   x   x   x
   x   x   x   x   x   x   x

  20  30  40  50  60  70  80

Number of Perfect Scores per Problem

1. 1/19
2. 0 ("Hardest")
3. 6
4. 7 ("Easiest")
5. 5
6. 1
7. 1
8. 2
9. 4
10. 6

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: 30 January 2000.