1) O instead of \Theta is OK. 
-1 for O(n) mentioning master theorem
-2 for O(log n) mentioning master theorem
-2 for O(n) with no explanation 
-2 for O(c^n) with a substitution method attempt
-3 for O(log n) or O((log n)^k) with no explanation. 

3a) 
-1 for mentioning a data structure with correct definition (i.e. "k keys
   <= current in a binary tree") 
-1 for "kth position in the dictionary" ("kth position in an ordered list
   of dictionary keys" is the correct way of saying this). 
-2 for "kth position in an array" 
-3 for "rank(left)+rank(right)+1 
-3 for "returns rank" with some explanation
-4 for r(left)=1, r(right)=n, and nothing else 

3b) 
-1 for modifcying R 
-1 for saying R[i] but using Select 
-2 for "select (left(R), rank (left,R))" 
Some answers did not make any sense at all, they got 1 or 2 points.  

3c) 
-1 for O(n) 
-1 for "assume select takes constant time"
-2 O(log n)
-4 constant. 



2a (5 marks)
  +2 if the rough idea is given, but not touch the key part.
2b (5 marks)
  +2 if you have wrong judegment, but find the secret in the
  funtion(that is, its range is [0,4]).
  -5 if you have wrong judgement
  -5 if you have right judgement but no reasonable explaination.


4a (5marks)
  No partial marks given
4b (5 marks)
  +1 if you count there are i elements in i steps
  +3 if you count m-i+1 in&nbsp; i steps (but 4a is wrong)
  -1 if you count m-i element in i steps
  no other patial marks
4c (5marks)
  +1 if you have the correct formula for average running time
  +2 if you have a good caculation (based on a false 4b result)
  -1 if your final result is wrong