Algorithms & Computation

Question 1

What is peak finding?

Answer 1

Finding a number in a sequence that is greater in value than all its neighbors.

Question 2

How efficient are selection sort and bubble sort in the worst case scenario?

Answer 2

O(n^2).

Question 3

How does bubble sort work? What about selection sort?

Answer 3

Bubble sort compares a pair and switches their place f the first is larger. Selection sort finds the smallest in the set, moves it to the front, and then recursively repeats after the sorted element.

Question 4

For an ordered list, binary search is of the complexity

Answer 4

log(n); divide and conquer algorithms tend to be of logarithmic time complexity.

Question 5

What is merge sort and how efficient is it?

Answer 5

nlog(n) — the set is divided into singleton lists by halving (log(n) component) and then individual sorted by direct comparison (n component).

Question 6

Describe a stochastic process.

Answer 6

In a stochastic process there is an element of randomness and unpredictability. A random walk is an example of a stochastic process and models many physical systems, for example molecule diffusion. Stochastic processes are in contrast to deterministic processes.

Question 7

What is memoization?

Answer 7

Storing the solutions to subroutines in memory to avoid having to recompute them later, as part of dynamic programming.

Question 8

A technique for reducing exponential time problems to polynomial time by reducing them to subroutines whose solutions are stored and later retrieved from memory is:

Answer 8

dynamic programming.

Question 9

RAM is basically a huge array of memory, maybe 4GB these days. What is the time complexity of data access in RAM if you know the address?

Answer 9

Constant time.

Question 10

What is document distance?

Answer 10

An algorithmic approach to comparing two text documents to determine how similar they are. One way to solve document distance is to create a vector for each document representing the frequency of all the words.

Question 11

What is a method of optimizing a data structure which tracks if items are connected?

Answer 11

Creating a weighted tree, which could be modeled as an array with each entry representing the parent node. In the weighted tree, a union of nodes always attaches the smaller of the two to the larger, producing a flatter tree structure overall. The proven most optimized solution is weighted quick union with path compression, which reduces the problem from 30 years to 6 seconds. This is why algorithm design is critical, having a supercomputer would not help you much here.

Question 12

Modeling percolation experiences a phase transition at a point that cannot be calculated mathematically, but determined computationally by

Answer 12

a weighted quick union with path compression algorithm which models the connections.

Question 13

Describe how the scientific method can be applied to algorithmic design.

Answer 13

Mathematical or conceptual theory can form a basis for design which can then be tested and evaluated empirically to determine performance and then iteratively improved.

Question 14

Algorithms that divide the input in half progressively are typically characterized by what order of growth?

Answer 14

logarithmic; log(n)

Question 15

A simple looping algorithm has what time complexity?

Answer 15

Linear, O(n)

Question 16

Executing statements without any looping constructs takes place in

Answer 16

constant time, O(1)

Question 17

Divide and conquer merge sort has what time complexity?

Answer 17

Linearithmic, O(nlog(n)); log(n) for the recursive binary division of the data, n for the merge operation between all elements.

Question 18

A double for loop has what order of growth? What about a triple for loop?

Answer 18

double for loop: O(n^2)

triple for loop: O(n^3)

Question 19

What is the worst time complexity? What is the best? What is practically the ideal complexity achieved in algorithm design?

Answer 19

Exponential is the worst, constant time is the best, linear or linearithmic is typically the best achieved in a practical setting.

Question 20

Using a variable name in an inner scope that is the same as the name of a variable in an outer scope is referred to as

Answer 20

variable shadowing.

Question 21

Which sorting algorithm requires more memory in order to execute, merge sort or insertion sort?

Answer 21

Merge sort, which requires n auxiliary memory. Insertion sort functions in place.

Question 22

What is a max heap?

Answer 22

A complete binary tree in which the value of every internal node is greater than its children.

Question 23

What is an AVL tree?

Answer 23

An AVL tree is a self-balancing binary search tree. An unbalanced search tree could exist such that the height is on the order of N, rather than log(n). This is obviously a disadvantage. AVL trees are balanced using tree rotations which change the tree structure without changing its order.

Question 24

How does one-way cryptographic hashing work?

Answer 24

A password (x) is hashed to a value h(x) = Q which is stored, future authentication attempts are hashed and compared to this value ( h(x’) == h(x) ; Q’ == Q ). It is basically prohibitive to reverse the hash function to determine the original password value.

Question 25

What is the Rabin–Karp algorithm?

Answer 25

It is a string search matching algorithm using a rolling hash technique to achieve a linear running time. For string s in string t, O(n) = O(s + t).

Question 26

What is open addressing?

Answer 26

A technique for dealing with collisions in hash tables. Collisions result in probing in which alternate destinations in the array are searched (probed) until an empty slot is discovered. Subsequently, searching will invoke probing in a deterministic manner until the key or an empty slot is ofund.

Question 27

What is hash chaining?

Answer 27

A method of dealing with hash collisions in which multiple keys map to a specific hash value and all are stored there, for example a hash table implemented as an array could store linked lists in each array index containing all hash keys for that index. Or, a Python array of dicts.

Question 28

Name two methods of dealing with collisions produced from hash functions?

Answer 28

Chaining and open addressing.

Question 29

What is the Karatsuba Algorithm? What is an even better improvement than this?

Answer 29

The Karatsuba Algorithm is a multiplication algorithm for a number of length n which improves the classical n^2 time complexity of multiplication to n^1.585. The Toom-Cook Algorithm runs in n^1.465 time and works by breaking multiplication into smaller subroutines which allow 9 multiplications to be achieved by 5. The Schönhage–Strassen Algorithm and Furer’s Algorithm are even better than this.

Question 30

What is dynamic programming?

Answer 30

Dynamic programming is an approach to algorithm design which utilizes memoization and guessing and is often applied to optimization problems.

Question 31

What is Dijkstra’s algorithm?

Answer 31

A method for finding the shortest path between nodes in a graph.