Fundamentals

Question 1

Explain: log_bx = n

Answer 1

n is how often I need to multiply b by itself to get x

log_bx = n​

Question 2

Name the most common runtimes.

Answer 2

• O(log(n))
• O(n)
• O(n * log(n))
• O(n²)
• O(n!)

Question 3

Runtime of binary search?

Answer 3

O(log(n))

Question 4

Runtime of linear search?

Answer 4

O(n)

Question 5

Runtime of quicksort?

Answer 5

O(n * log(n))

Question 6

Runtime of selection sort?

Answer 6

O(n²)

Question 7

Runtime of traveling salesman problem?

Answer 7

O(n!)

Question 8

How many permutations exist for n elements?

Answer 8

n!

Question 9

What is recursion?

Answer 9

When a function calls itself.

Question 10

Explain partially completed.

Answer 10

A function that calls another function is ‘paused’ until the called function returns. During this time its values are stored on the call stack in its own stack frame.

This “paused state” is called partially completed.

Question 11

Name the two cases that need to be considered in a recursive function.

Answer 11

1. Base case (for termination)
2. Recursive case (loop)

It needs to be shown that the recursive case progresses towards the base case.

Question 12

How are recursion and induction similar?

Answer 12

• both have a base case
• the recursive case corresponds to the inductive case

Question 13

What is Divide-and-Conquer?

Answer 13

A recursive technique to solve algorithmic problems.

1. Figure out a simple case as the base case
2. Figure out how to reduce the problem to the base case

e.g. Quicksort

Question 14

Name 1 Algorithm Design Strategy.

Answer 14

• Divide-and-Conquer

Question 15

What is the runtime of Breadth-First-Search?

Answer 15

O(V + E)

Question 16

How can you solve the shortest path problem?

Answer 16

Breadth-First-Search (BFS)

Question 17

Describe how Breadth-First-Search works.

Answer 17

1. Start at the start node/vertex
2. If current node == search node => end
3. Put current node in the visited set
4. Enqueue all children of the current node that are not contained in the visited set in the to search queue
5. If the search queue is empty return “not found”
6. Dequeue the next node in the search queue and go to (2)

Question 18

Name the most common FIFO data structure.

Answer 18

Queue.

Question 19

Name the most common LIFO data structure.

Answer 19

Stack.