The following is the marking scheme that was followed
for marking the midterm. The midterm was marked by myself
and a group of TAs. If you find something in your 
midterm that was not marked according to the marking
scheme, please bring it to my attention with a 
remark request. The form for a remark request can
be found on the course homepage. Also please double-check to ensure
the addition on your exam is correct.  

To adjust for the fact that some parts of the marking scheme were
slightly harsh, your midterm mark will be recorded out of 45. (The mark
on your paper is out of 48, but I am recording it out of 45.)
If your raw mark was higher than 45, your mark is still
recorded as whatever it was originally. For example, 
if you got 48, then your mark will be 48/45. This
will be treated as "bonus" marks.


Question 1.

----------
Solution: 

("Why is searching for an item in a binary search tree sometimes more efficient than searching for an item in a list?") 4 marks

In a list of size N, you potentially have to search through all N elements
in the list before finding the element you are looking for. In a binary search 
tree, you need only follow a path from the root to some leaf in order to 
determine if an element is present. If the BST is "nicely shaped" (i.e., well
balanced) then the height of the tree will be about log N, and so the number
of elements that have to be examined on a path from the root to a leaf are much 
fewer than the number of elements that have to be examined in a list. 

("Under what conditions is searching a BST no more efficient than searching a list?") 3 marks

If the BST is skewed to one side, then the height of the tree can be as large 
as N, and searching through the tree will be no more efficient than searching a list.

Diagrams (3 marks)

*** The question asked you to use diagrams. Including a diagram of a tree to
illustrate a tree skewed to one side, or a diagram to illustrate a 
well-balanced tree was worth 3 marks. You didn't need to draw both
diagrams to get the 3 marks, but you did need to include at least one. 

*** For the first part, to get full marks, you needed to say something about:
  - traversing the nodes from the root to a leaf. 
  - how the number of nodes in a path from the root to a leaf (in a "nicely 
shaped" tree) is far fewer than the number of elements that have to be 
traversed in a list. (You didn't necessarily have to say that the height of
tree should be log N, but you did need to say something about the tree being
"nicely shaped"). 


Question 2:

def payout(n):
   if n == 1:
      return 1
   if n == 3:        # this case can be omitted and function is still correct
      return 4
   if n%2 == 0:
      return payout(2n+1)
   return 3+payout(n-2)

3 marks for pointing out base cases
1 mark for correctly testing whether n is even/odd
3 marks for returning payout(2n+1) when n is even
3 marks for returning 3+payout(n-2) when n is odd

Question 3:

(a)
ABC
0

(b)
3
5

(c)
XYZ
10

(d)
XYZ

(a)-(c): 
1 mark for each correct line
-1 mark for each incorrect line
-1 if order of lines swapped but otherwise correct
-0.5 if string is contained in quotes (""). (Quotes do not appear on the screen when outputting a string). 

(d) 2 marks for the correct answer, 0 for anything else. 
   

Question 4:

                     F
                    / \
                   /   \
                  C     H
                 / \     \
                /   \     \
               A     D     K
                      \   /
                       E J
          

-2 marks for tree not being a BST
-2 marks for each node in an incorrect position

Question 5:

def size(self):
   return self.container.size()

def pop(self):
   tmpq = Queue()
   ret = self.container.dequeue()
   while not self.container.isEmpty():
      tmpq.enqueue(ret)
      ret = self.container.dequeue()

   self.container = tmpq
   return ret

Part marks were given if you were on the right track. 
If you made progress toward the solution you got about  1 - 4 marks, 
depending on how much progress you made. The
marks for this part were fairly bimodal -- either people understood what needed
to be done and got full marks, or people misunderstood the problem and got
little or no marks. 

Some common mistakes:
- simply returning the head of the queue
- copying the queue into a temporary queue and then returning the head of the
temporary queue (which is essentially the same as the previous mistake)