midterm

Question 1

rehashing: when and how?

Answer 1

when the table exceeds a certain load, double the table size and round up to the nearest prime number and refill via the hashing function
cost: O(N)

Question 2

in-place sorting algorithms

Answer 2

sorting algorithms that require no auxiliary arrays

Question 3

main advantages open address hashing has over separate chaining (3)

Answer 3

no extra space for pointers, no extra time allocating nodes that make up each separate bucket, and easier spacial locating when rehashing

Question 4

insertion sort over merge sort

Answer 4

insertion is good for small scale, mostly sorted

Question 5

merge sort over insertion sort

Answer 5

merge sort is good for big and mostly sorted

Question 6

selection sort over insertion sort

Answer 6

selection sort is good for not very sorted (swaps are gonna happen anyway better be good for something)

Question 7

quick sort over merge sort

Answer 7

large elements, evenly distributed

Question 8

merge sort over quick sort

Answer 8

mostly sorted already (the less swaps the better)

Question 9

different ways to select a pivot (4)

Answer 9

median, first, last, or random

Question 10

height of a recursion tree during divide and conquer

Answer 10

lg(n)

Question 11

runtime of an algorithm depends on (4)

Answer 11

input size, processor speed, language, RAM

Question 12

order of big oh notations from best to worst

Answer 12

O(1), O(lg(n)), O(n), O(nlg(n)), O(n^2), O(n^3), O(2^n), O(n!)

Question 13

how many operations to find the max element in an unordered stack

Answer 13

the height of the stack

Question 14

big O of finding the minimum value in a hash table of size n, containing n elements where separate chaining is used and each bucket is unsorted

Answer 14

search all buckets -> O(n)
search all values in each bucket -> O(n)
O(n) + O(n) = O(n)

Question 15

big O to make a stack empty that currently contains n/2 element. implemented as an array of size n

Answer 15

O(1) (make the top point to 0)

Question 16

big O of selection sort (best, average, and worst case)

Answer 16

all O(n^2)

Question 17

big O of insertion sort (best, average, and worst case)

Answer 17

best: O(n), average & worst: O(n^2)

Question 18

big O of counting sort (best, average, and worst case)

Answer 18

all O(n)

Question 19

big O of merge sort (best, average, and worst case)

Answer 19

all O(nlgn)

Question 20

big O of quick sort (best, average, and worst case)

Answer 20

best: O(nlgn), average & worst: O(n^2)

Question 21

big O of binary search (best, average, and worst case)

Answer 21

best: O(1), average & worst: O(lgn) (recursion)

Question 22

binary search

Answer 22

(only in sorted arrays) find middle, check which side to go to, check middle of chosen side, continue until found

Question 23

big O of linear search (best, average, and worst case)

Answer 23

best: O(1), average & worst: O(n)

Question 24

load factor for linear probing hash table unsuccessful search

Answer 24

0.5(1 + 1/(1 + load_factor)^2)

Question 25

load factor for linear probing hash table successful search

Answer 25

0.5(1 + 1/(1 + load_factor))

Question 26

load factor for separate chaining hash table unsuccessful search

Answer 26

load_factor

Question 27

load factor for separate chaining hash table successful search

Answer 27

1 + load_factor/2