## Clicker Questions

1: *O(n)* loop followed by another *O(n)* loop

2: *log(student wealth) / log(Bill Gates wealth)*

3: How many bits in a word on your computer?

4: Can the national debt be stored in an ` int`

5: time plot on log-log paper curves up

6: input size increases by 2, time by 8

7: What benefit does ` Integer` provide

8: ` Integer` is * immutable* ... what happens

9: Big O of `int n = myarray.length;`

10: `int [] myarray = new int[1000];` storage

11: `Integer [] myarray = new Integer[1000];` storage

11b: Are `3.0` and `0.3` represented exactly?

12: What is ` (cons '(a) '(b))` ?

13: What is ` (first '((a b) (c d)))` ?

14: What is ` (rest '((a b) (c d)))` ?

15: ` (rest (rest '((a b) (c d))))` ?

16: ` (length '((a b) (c d)) )` ?

17: ` (reverse '((a b) (c d)) )` ?

18: `lst = cons( i, lst );` in a loop

19: runtime type of ` first(lst)`

20: ` (append '(a b) '(c d))` ?

21: Big O of `Cons lst = append(x, y); `

22: ` ( lst == reverse(reverse(lst)) )`

23: `( first(lst) == first(reverse(reverse(lst))) )`

24: `lst = append( list(i), lst );` in a loop

25: Big O of `lst = append( list(i), lst );` in a loop

26: `lst = append( lst, list(i) );` in a loop

27: Big O of `lst = append( lst, list(i) );` in a loop

28: `lst = cons( i, lst );` in a loop,
`lst = nreverse(lst);`

29: Big O of the above

30: after above, type of ` first(lst)` as seen by the compiler

31: ` (intersection '(c r e a m) '(s u g a r))`

32: ` (union '(c r e a m) '(s u g a r))`

33: ` (set-difference '(c r e a m) '(s u g a r))`

34: ` (intersection '(r a t) '(f i n k))`

35: ` (set-difference '(r a t) '(f i n k))`

36: on a Stack: (push 1) (push 2) (push 3) (pop) (pop) (push 4) (pop) (pop)

37: Big O of set intersection, done well?

38: on a Queue:
(insert 1) (insert 2) (insert 3) (remove) (remove) (insert 4) (remove) (remove)

39: Big O of `sum += lst.get(i);` on `ArrayList`

40: Big O of `sum += lst.get(i);` on `LinkedList`

41: Big O of `for (Integer i : lst ) sum += i;` on `LinkedList`

41b: Is `every` thing in the empty list (`null`) a number?

41c: Is `some` thing in the empty list (`null`) a number?

42: Java corresponding to tree

43: advantages of the first-child / next-sibling representation of trees

44: Big O of finding an item in a balanced BST

45: What kind of tree is most similar to our directory tree?

46: order in which nodes of tree are visited
in depth-first order

47: order in which nodes of tree are processed
in inorder

48: order in which nodes of tree are processed
in postorder

49: order in which nodes of tree are processed
in preorder

50: Why do binary search trees need to be balanced?

51: branching factor * b* for tree with * n = 1,000,000,000* elements to have a depth * d* of 3?

52: how long does it take to read a record from a disc drive?

53: divide a 1 TB disc drive among all possible SSNs

54: ` ( list("a") == list("a") )`

55: ` (subst 'crazy 'beauty '(beauty is as beauty does))`

56: ` (sublis '((z 4) (y 3) (x 2)) '(* x y))`

57: ` ( list("a").equals(list("a")) )`

58: ` (match '(- ?x ?y) '(- w 3))`

59: ` (match '(- ?x ?x) '(- w 3))`

60: What is *not* true of ` .hashCode()` in Java?

61: load factor (fullness) *λ < 0.7* in a hash table

62: Big O of hashing when *λ < 0.7*

63: advantage of hashing with buckets

64: Big O of hashing with buckets

65: inserted into a min priority queue ` ((A, 2), (B, 3), (C, 1), (D, 2), (E, 1))`

66: advantage of heap for storing priority queue

67: data structure used for a heap

68: What is * not* true about Insertion Sort?

69: What is true about Quicksort?

70: What is true about Heapsort?

71: number of possible graphs with n nodes

72: Suppose each user of Facebook has 1000 friends. Is that graph...

73: family tree (ancestry) as a graph

74: What does Prim's algorithm guarantee?

75: What does Dijkstra's algorithm produce?

76: What advantage might A* have over Dijkstra's Algorithm?

77: What does A* assume that Dijkstra does not?

78: What is true of heuristic functions for A*?

79: What kind of problem is MapReduce good for?