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