Existing Algorithms Flashcards
What is the purpose, IO and time complexity of Karatsuba’s Algorithm?
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(n1.59)
What is the purpose, IO and time complexity of Prim’s Algorithm?
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(n2)
T-BinHeap = O((m+n)log n)
T-FibHeap = O(n log n+m)
What is the purpose of Dijkstra’s Algorithm, what data structures are used?
Purpose: Solves shortest path (single sourced) problem) asd creates a shortest-path tree.
Uses a priority queue where total distance determines the priority
Kruskal’s Algorithm - What is the purpose, describe the algorithm
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
Kruskal’s Algorithm - What is the purpose, IO and time complexity?
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(Tsort(m) + Tfind(x)m + Tunion(x)n)
Strassen Algorithm - Purpose, IO and time complexity?
Purpose: Matrix multiplication
INPUT: two n x n matrices A & B
OUTPUT: product of AxB
T(n) = 7T(n/2) +cn2 –> θ(nlog 7) or θ(n2.808)
Fractional Knapsack Algorithm - Describe
TBC
Interval Selection - Describe
TBC
Bellman-Ford Algorithm - Purposo, IO & Time Complexity
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)
Floyd-Warshall Algorithm - Purpose, IO, Time Complexity
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 vi to vj
Time Complexity: O(n3)
Maximal increasing subarray - Describe
TBC
Maximal increasing subarray - Describe
TBC
What type of algorithm is Karatsuba’s algorithm?
D&C, greedy or dynamic?
Divide and Conquer
Halves the problem (b = n/2) and uses p1, p2 & p3 to put it back together (a = 3)
What type of algorithm is Strassen’s algorithm? D&C, greedy or dynamic?
Divide and Conquer - multiply two matrices
What type of algorithm is Dijkstra’s algorithm? D&C, greedy or dynamic?
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.”
What type of algorithm is Prim’s algorithm? D&C, greedy or dynamic?
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.”
What type of algorithm is Kruskal’s algorithm? D&C, greedy or dynamic?
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.”
Describe the Fractional Knapsack algorithm? D&C, greedy or dynamic?
Greedy - At each step we optimise the value/weight ratio of items
Desribe the Interval Selection algorithm? DC, greedy or dynamic?
Greedy - choose activity/interval which finishes first. “Make a greedy choice on the finishing time.”
Algorithm Types - Bellman-Ford What type of algorithm is the BellmanFord algorithm? D&C, greedy or dynamic?
Dynamic Programming
Algorithm Types - Floyd-Warshall What type of algorithm is the Floyd-Warshall algorithm? D&C, greedy or dynamic?
Dynamic Programming
Algorithm Types - Maximal Increasing Subarray What type of algorithm is the Maximal Increasing Subarray algorithm? D&C, greedy or dynamic?
Dynamic Programming
Algorithm Types - Edit Distance What type of algorithm is the Edit Distance algorithm? D&C, greedy or dynamic?
Dynamic Programming
What underlying data structures are used in Dijkstra’s Algorithm?
What are their preferred use?
What are their time complexities?
Linked List: preferred when there are a lot of edges - O(n2)
Binary Heap: preferred when there not a lot of edges - O((m+n) log n)
Fibonacci Heap: best complextiy but compl
What are the time complexites for DFS searches run on adjacency-matrix and -list based graphs?
List: O(n+m)
Matrix: O(n2)
