Week 1

Question 1

What is an algorithm?

Answer 1

A step-by-step procedure for solving a problem using a computer program.

Question 2

What is a procedure?

Answer 2

Method to solve the problem.

Question 3

Is a programming language a type of procedure?

Answer 3

Nope.

Question 4

Why do we analyze algorithms?

Answer 4

To predict performance, provide guarantees and understand theoretical basis.

Question 5

What are the limitations of run-time analysis?

Answer 5

• Implementing the algorithm may be difficult.
• Doesn’t include all possible inputs.
• Only valid on same software environments and hardware.

Question 6

How much time to primitive operations take?

Answer 6

Constant time.

Question 7

If a perform a primitive operation many times what is the time taken?

Answer 7

N where N is the number of times.

Question 8

Define O(1), O(log N), O(N), O(N log N)

Answer 8

O(1) = constant time regardless of input
O(log N) = logarithmic time, proportional to the logarithmic of the input size.
O(N) = linear time, directly proportional to input size.
O(N log N) = log-linear time, proportional to the logarithmic of the input size times the input size.

Question 9

Why is Big O notation desirable?

Answer 9

Abstracts away implementation details as we expect every algorithm to have a run time proportional to its big O notation across every OS.

Question 10

What is O of O(N) + O(N^2)?

Answer 10

O(N^2)

Question 11

How can I find the value of n for which the Big-Oh notation holds? Use example 11n + 5 to explain.

Answer 11

We take the big O representation O(x) and express c * x >= 1 / 2 * (original equation). The value of n is the point where it holds.

Question 12

What does big Ω do?

Answer 12

Tells us that the time taken grows at least by this function.

Question 13

What does Θ notation do?

Answer 13

Tight bound, gives a minimum running time k1 * N and a maximum running time k2 * N.

Question 14

Summarize difference between Big Θ, Big Oh and Big Omega.

Answer 14

Θ (N^2) must have N^2 only as biggest.
O(N^2) must have N^2 or lower as biggest.
Ω (N^2) must have N^2 or larger as biggest.

Question 15

Explain briefly selection sort.

Answer 15

Iterate through the list from i to find smallest entry and swap with i. Then increment i and repeat till end of list.

Question 16

List sorting algorithms that are in-place?

Answer 16

Selection Sort
Insertion Sort
Shell Sort
Quick Sort

Question 17

List sorting algorithms that are non-recursive.

Answer 17

Selection Sort
Insertion Sort
Shell Sort

Question 18

List sorting algorithms that utilize comparisons.

Answer 18

Selection Sort
Insertion Sort
Shell Sort
Merge Sort
Quick Sort

Question 19

List sorting algorithms that are internal.

Answer 19

Selection Sort
Insertion Sort.
Shell Sort
Quick Sort

Question 20

List sorting algorithms that are external?

Answer 20

Merge Sort

Question 21

List sorting algorithms that are unstable.

Answer 21

Selection Sort
Shell Sort
Quick Sort

Question 22

Explain stability in relation to sorting algorithms.

Answer 22

Stable sorting algorithms preserve the existing relative order of elements when comparing equal keys.

Question 23

Explain internal vs external in relation to sorting algorithms.

Answer 23

• Internal sort is one where the items being sorted can be kept in main memory / RAM.
• External sort is one where the items being sorted need to use external memory.

Question 24

Explain insertion sort?

Answer 24

In iteration i, swap a[i] with each larger entry on its left. Iterate through full list until every element has been inserted in correct place.

Question 25

List Sorting algorithms that are stable.

Answer 25

Insertion Sort Merge Sort

Question 26

List best case of all the sorting algorithms.

Answer 26

Selection Sort: O(N^2) Insertion Sort: O(N) Shell Sort (3x + 1): O(N log N) Merge Sort: 1 / 2 N log N Quick Sort: N lg N

Question 27

List worst case of all the sorting algorithms.

Answer 27

Selection Sort: O(N^2) Insertion Sort: O(N^2) Shell Sort (3x + 1): O(N^(3/2)) Merge Sort: N lg N Quick Sort: 1/2 N^2

Question 28

List average case of all the sorting algorithms.

Answer 28

Selection Sort: O(N^2) Insertion Sort: O(N^2) Shell Sort (3x + 1): O(N^(3/2)) Merge Sort: N lg N Quick Sort: 2 N lg N

Question 29

Explain shell sort.

Answer 29

Elements a certain gap apart are compared and swapped if the order is incorrect. This is incremented throughout the list and then the gap is decremented. This process repeats until the gap is 1 and then a standard insertion sort is performed.

Question 30

Explain merge sort.

Answer 30

Divide array into two halves, recursively sort each half, merge two halves by comparing elements sequentially from each half and inserting into new temp array.

Question 31

List all sorting algorithms that are recursive.

Answer 31

Merge Sort Quick Sort

Question 32

List all sorting algorithms that are out of place.

Answer 32

Merge Sort

Question 33

Explain quick sort.

Answer 33

Take first / mid element of array. Place all elements greater than pivot to left of pivot and all elements less than pivot to right and then quicksort these two subarrays. What actually happens is pivot set to first element, left-mark set to 2nd element and right-mark set to last element. We advance left-mark until it finds an element that is > pivot. Then we decrement right-mark till we find element < pivot. We swap these elements and continue with left again. This process continues until left and right cross and then we swap pivot with right-mark.

Question 34

Explain Key-Indexed Counting Sort.

Answer 34

Find max value in array Make array of frequencies of size max + 1 Reconstruct array starting with smallest number adding it how many times it occurs and working up to biggest number.

Question 35

Explain radix sort.

Answer 35

Perform sort on units place of numbers, then tens and so on until the array is sorted. We get the max 'place' from the largest number.

Question 36

What is linear search?

Answer 36

Brute force approach look at every element in turn until you find the correct one.

Question 37

What is the advantage of linear search?

Answer 37

Can find in unsorted input.

Question 38

What is the worst case time complexity of linear search?

Answer 38

O(N)

Question 39

Explain binary search.

Answer 39

Selected middle element of sorted array, if target is that element return, if target is lower than that element search in lower half of array, if target is higher than that element search in higher half of array.

Question 40

What is the worst case time complexity for binary search?

Answer 40

O (log N)

Question 41

Explain Knuth-Morris-Pratt creation of lps array.

Answer 41

matching = 0 i is pattern index lps[0] = 0 if p[i] == p[matching] then matching++ lps[i] = matching i++ else if matching != 0 then matching = lps[matching - 1] (No i++ here as we must check smaller suffixs) else matching == 0 then lps[i] = 0 i++

Question 42

Explain Knuth-Morris-Pratt algorithm assuming LPS array already formed.

Answer 42

i is text index j is pattern index if i == j increment both if j == pattern.length() Pattern found set j = lps[j - 1] else if j != 0 then j = lps[j - 1] else i++

Question 43

What is the time complexity of the Knuth Morris Prath algorithm?

Answer 43

O(length of pattern + length of text)

Question 44

Time complexity of counting sort vs radix sort.

Answer 44

C: O(n+ range of input values) R: O(d * (n + k)) where n = number of elements d = number of digits in the largest number k = base (10 for decimal)

Question 45

Explain KMP with DFA style code assuming dfa already produced.

Answer 45

j = 0 current state for i to n j = dfa[text.charAt(i)][j] if j == m Pattern found at i - m + 1 j = 0 where n is length text, m is length pattern

Question 46

Explain how to create the dfs array.

Answer 46

dfa[state][character_input] int x = 0; dfa[charAt(0)][0] = 1 All values in dfa init to 0 for j = 1 to m copy values of state x into state j set matching input to progress to next state. x = dfa[matching_input][x]

Question 47

Explain how run length encoding reduces redundancy in a bitstream.

Answer 47

4-bit counts to represent alternating runs of 0's and 1's. (Will have to increases bits per count if there are ever more than 15 0's or 1's in a row.

Question 48

Explain the LZW compression algorithm.

Answer 48

Put ASCII values into dictionary String w = "" for c : input String wc = w + c if dictionary.contains(wc) w = wc else result.add(dictionary.get(w)) dictionary.put(wc, dictSize++) w = "" + c if (!w.equals("") result.add(dictionary.get(w))

Question 49

Explain the LZW decompression algorithm.

Answer 49

Simply read off dictionary made with compression algorithm.

Question 50

Explain huffman encoding.

Answer 50

Calculate frequency of every character. Make all characters leaf nodes. Combine two leafs with least frequency into a node with its value being combined frequencies of the two. Repeat until all leafs used. Going left in tree is 0, going right is 1. Construct binary encoding from root starting with MSB.

Question 51

Huffman Code assuming frequency array done.

Answer 51

MinPQ pq; for char i=0 to R if(freq[i] > 0) pq.insert(node(i, freq[i],null,null)) while (pq.size() > 1) Node x = pq.min() Node y = pq.min() Node parent = new Node("_", x.freq + y.freq, x + y) pq.insert(parent) return pq.min()