Existing Algorithms

Question 1

What is the purpose, IO and time complexity of Karatsuba’s Algorithm?

Answer 1

Purpose: multiply large numbers

INPUT: x, y are length n integers

OUTPUT: product of xy

T(n) = c if n=1

T(n) = 3T┌n/2┐ + cn otherwise –> O(n^1.59)

Question 2

What is the purpose, IO and time complexity of Prim’s Algorithm?

Answer 2

Purpose: Find Minimal Spanning Tree using priority queue (similar to Dijkstra’s)

INPUT: weighted graph G = (V, E, w)

OUTPUT: prev(v) for every node, v€V indicating a MST

T-List = O(n²)

T-BinHeap = O((m+n)log n)

T-FibHeap = O(n log n+m)

Question 3

What is the purpose of Dijkstra’s Algorithm, what data structures are used?

Answer 3

Purpose: Solves shortest path (single sourced) problem) asd creates a shortest-path tree.

Uses a priority queue where total distance determines the priority

Question 4

Kruskal’s Algorithm - What is the purpose, describe the algorithm

Answer 4

Purpose: Finds the minimal spanning tree using disjoint sets. It looks at edges and keeps the smallest edge at a time, ensuring cycles are not created

Question 5

Kruskal’s Algorithm - What is the purpose, IO and time complexity?

Answer 5

Purpose: Finds the minimal spanning tree using edges and disjoint sets.

INPUT: weighted, indirected graph G = (V, E, w)

OUTPUT: a set of x edges representing the MST

T = O(T_sort(m) + T_find(x)m + T_union(x)n)

Question 6

Strassen Algorithm - Purpose, IO and time complexity?

Answer 6

Purpose: Matrix multiplication

INPUT: two n x n matrices A & B

OUTPUT: product of AxB

T(n) = 7T(n/2) +cn² –> θ(n^{log 7}) or θ(n^2.808)

Question 7

Fractional Knapsack Algorithm - Describe

Answer 7

TBC

Question 8

Interval Selection - Describe

Answer 8

TBC

Question 9

Bellman-Ford Algorithm - Purposo, IO & Time Complexity

Answer 9

Purpose: Solves Single-source Shortest Path Problem
where the grapd has negative edges (but no negative cycles)

“Computes the shortest distance from s to all other nodes in the graph G”

I/p: Graph G & a start node s
O/p: d(u) for every node u. Denotes distance from s to u

TIme Complexity = Θ(mn)

Question 10

Floyd-Warshall Algorithm - Purpose, IO, Time Complexity

Answer 10

Purpose: Solves the All-Pair Shortest Path Problem
Where G may contain -ve edges but does not contain -ve cycles

I/p: Graph G
O/p: f(i, j) for any i, j. Denotes distance from v_i to v_j

Time Complexity: O(n³)

Question 11

Maximal increasing subarray - Describe

Answer 11

TBC

Question 12

Maximal increasing subarray - Describe

Answer 12

TBC

Question 13

What type of algorithm is Karatsuba’s algorithm?

D&C, greedy or dynamic?

Answer 13

Divide and Conquer

Halves the problem (b = n/2) and uses p₁, p₂ & p₃ to put it back together (a = 3)

Question 14

What type of algorithm is Strassen’s algorithm? D&C, greedy or dynamic?

Answer 14

Divide and Conquer - multiply two matrices

Question 15

What type of algorithm is Dijkstra’s algorithm? D&C, greedy or dynamic?

Answer 15

Greedy - always choose the node with the lowest estimated (total) distance, this find’s the shortest path through a graph.

“I will always eat the node that is closest to A.”

Question 16

What type of algorithm is Prim’s algorithm? D&C, greedy or dynamic?

Answer 16

Greedy - always choose the edge with the lowest weight and connected to the known region

“I will always eat the shortest edge attaching me with an outside node.”

Question 17

What type of algorithm is Kruskal’s algorithm? D&C, greedy or dynamic?

Answer 17

Greedy - Always choose the edge with lowest weight and not form a cycle

“I will always eat the shortest edge that does not create a cycle.”

Question 18

Describe the Fractional Knapsack algorithm? D&C, greedy or dynamic?

Answer 18

Greedy - At each step we optimise the value/weight ratio of items

Question 19

Desribe the Interval Selection algorithm? DC, greedy or dynamic?

Answer 19

Greedy - choose activity/interval which finishes first. “Make a greedy choice on the finishing time.”

Question 20

Algorithm Types - Bellman-Ford What type of algorithm is the BellmanFord algorithm? D&C, greedy or dynamic?

Answer 20

Dynamic Programming

Question 21

Algorithm Types - Floyd-Warshall What type of algorithm is the Floyd-Warshall algorithm? D&C, greedy or dynamic?

Answer 21

Dynamic Programming

Question 22

Algorithm Types - Maximal Increasing Subarray What type of algorithm is the Maximal Increasing Subarray algorithm? D&C, greedy or dynamic?

Answer 22

Dynamic Programming

Question 23

Algorithm Types - Edit Distance What type of algorithm is the Edit Distance algorithm? D&C, greedy or dynamic?

Answer 23

Dynamic Programming

Question 24

What underlying data structures are used in Dijkstra’s Algorithm?

What are their preferred use?

What are their time complexities?

Answer 24

Linked List: preferred when there are a lot of edges - O(n²)

Binary Heap: preferred when there not a lot of edges - O((m+n) log n)

Fibonacci Heap: best complextiy but compl

Question 25

What are the time complexites for DFS searches run on adjacency-matrix and -list based graphs?

Answer 25

List: O(n+m)

Matrix: O(n²)