Final: Algorithms Spring 2016

I _(your name)____________ did not collaborate with any person on this exam. I understand that doing so will result in a 0 for the Final Exam.

• You can use online references, but write answers in your own words! Cite any references used. Answer the question in your own words, no credit will be given for answers copied from any source.
• No collaborating with other people; a 0 will be given if any collaboration evidence is found. Ask me for a hint if you are stuck on any particular problem.
• I am looking for very specific, detailed, correct, and complete answers.

• Most answers found on the Internet (especially Wikipedia) are generic answers for people without a networking background and …show more content…
How could RSA encryption be used with it.

2 (6 Points) Divide and Conquer
a) Explain the Divide and Conquer strategy

b) How is recursion connected to Divide and Conquer

c) How does Master Method connect to Divide and Conquer 3) Dynamic Programming (10 Points)
a) Explain Dynamic Programming.

b) What advantages does Dynamic Programming give over Divide and Conquer? Give an example.

c) (Dynamic Programming Problem: Shortest Path) Give the table to find the shortest path from node 9 to every other node.

d) Part c was Dijkstra algorithm. Was it a Breath First Search Algorithm or Depth Search First Algorithm? What heap from #6 on this test is commonly used for Dijkstra’s Algorithm.

e) (Dynamic Programming Problem: LCS) Suppose you have the sequence: 3, 1, 4, 7, 9, 2, 11, 13, 14. The largest increasing subsequence is 1 4 7 9 11 13 14. Use LCS to find the largest increasing subsequence.

4) (20 Points) a) Using 3c, formulate the shortest path from node 9 to node 6. Solve with Lindo.
b) Using 3c, with the edges as capacity, formulate the max flow of the network. Solve with Lindo. …show more content…
There are other types of heaps; two other common heaps are Binomial Heaps and Fibonacci Heaps. Give an example of a Binomial Heap and a Fibonacci heap. Below are the answers we found in class for binary heap. Find the amortized time (average over n operation) for Binomial and Fibonacci heaps (cite the textbook or online reference).

Proc Binary Heap
(worst-case) Binomial
(worst-case) Binomial
(amortized) Fibonacci
(amortized)
MakeHeap Q(1) Q(1) Q(1) Q(1)
Insert Q(lg n) O(lg n) _____ _____
Minimum Q(1) O(1) Q(1) Q(1)
Extract-Min Q(lg n) O(lg n) ______ ______
Union (Merge) Q(n) O(lg n) ________ ______
Decrease Key Q(lg n) Q(lg n) ______ _____
Delete Q(lg n) Q(lg n) ______ _____

7) ( 6 points) Currently what is the fastest for the following. Give the name and running time.
a) Matrix Multiplication Algorithm?

b) Integer Multiplication Algorithm?

c) Polynomial Multiplication Algorithm?

d) Minimal Spanning Tree Algorithm?

e) Shortest Path?

f) Factoring?

8 (6 points) For shortest path we discussed BFS, Floyd-Warshall, Bellman Ford, and Dijkstra.
a. What is the running time of each?

b. What is the running time of Dijkstra on a sparse graph versus a dense