CS 211, Fall 2005
Prelim 2 Grading Guide (Preliminary)
=========================================================
Question 1 (True/False)
2 points each; no partial credit
=========================================================
Question 2 (BSTs)
2 points each; no partial credit; no explanation is needed
=========================================================
Question 3 (Heaps)
There are two possible answers depending on the heap-building method
they choose. Either answer is worth 10 points.
-1 for a trivial copying mistake
-3 for building a min-heap instead of a max-heap
+3 if they create a valid heap using the given data even if they
don't use either heap-building algrithm
-5 if fill backwards
=========================================================
Question 4 (Big-O)
Each of the three parts is worth 5 points.
a. It should be a definition in terms of a witness pair, but there
is a version using limits that is also OK. It does not matter
whether < or <= is used.
Not mention N or C: -2
2 pts for growth rate only
b. This is pretty much all or nothing, but it's possible to make a
minor math mistake (-1 point). -2 for each N or C if no value provided.
1pt for only T/F answered
c. They should give a simple counterexample. Again, it's pretty
much all or nothing. They don't have to prove their
counterexample in detail as long as it's clear that it is a
counterexample.
1pt for only T/F answered
=========================================================
Question 5 (Inheritance)
-7 No superclass
-4 Bad declaration
-1 Wrong Method
-4 Logarithm class
-1 base in log must be double
=========================================================
Question 6 (Data Structures)
Each of the 5 parts is worth 4 points. Each part consist of two
subparts (one advantage for each data data structure), so each
advantage is worth 2 points. It's hard to break the grading down
any further to the 1 point level.
Additional note:
--Globally, initialization advantages were not counted, as the problem
specified "using" the data structures, not creating them.
--Part c) An acceptable advantage to BSTs was that they can take up less
space than a hashtable.
An unacceptable advantage was that BSTs did not have collisions.
--Part d) It was acceptable to say that heaps used less space than arrays of
lists.
=========================================================
Question 7 (Sorting)
Each of the two parts is worth 5 points.
-2 for incomplete split, merge steps
-2 If missing Splt or Meger steps
-1 for a simple copying mistake
-3 if they move everything down instead of just swapping for the
Selection Sort
=========================================================
Question 8 (Data Structure and Runtime Analysis)
+3 for explanation
+2 for runtime analysis