[Solved] CS317 Homework 2

1. Draw a recursion tree (as shown in the notes) to sort the following array using MergeSort (5 points)

2. Sort the following array visually (as shown in the notes) using

QuickSort (indicate the position of P, L , R in each step) (5 points)

3. State 5 real world applications of Graph Theory. (5 points)

4. State the difference between an undirected and a directed graph. (4 points)

5. Identify edges and vertices in the following graphs. (4 points)

6. Represent the following graphs using Adjacency List and

Adjacency Matrix. (8 points)

7. Apply the DFS traversal algorithm on the following graph and indicate when each vertex was discovered and processed. Also state the order in which each vertex was processed. Show your stack and the traversal order. (5 points)

8. Apply the BFS traversal algorithm on the following graph and indicate when each vertex was discovered. Also state the order in which each vertex was processed. Show your queue and the traversal order. (5 points)

9. What is the efficiency for representing a graph using an adjacency matrix and adjacency list? (2 points)

10. Explain the Greedy technique in plain English. Give one example where Greedy technique works and one where it does not work.

State the generic Greedy Algorithm and the Greedy-Choice Property. (5 points)

11. What is a spanning tree? Find all spanning trees of the following graph. (4 points)

12. What is a minimum spanning tree? Give an example. (3 points)

13. Find a minimum spanning tree in the following graph using Prims and Kruskals Algorithm. Show all the steps i.e. how a vertex or edge is added in the set to form/grow a minimum spanning tree. (10+10 points)

14. Consider the following graph. List the shortest path between A and rest of the vertices using Dijkstras algorithm. Show the shortest path graph and shortest path matrix. Build the shortest path graph step by step. (10 points)

15. Encode/compress the following string using Huffman encoding technique. Show each step with min-priority queue values, and final binary Huffman tree. Give the encoding of each letter. Calculate the compression ratio over 8-bit binary representation of the string. (10 points)

TENNESSEE

16. Sort the following elements (in place) in an ascending/increasing order using HeapSort. Show step by step execution of the HeapSort algorithm. (10 points)

9,4,1,6,3,8,2,10

17. Implement QuickSort and MergeSort to sort the given input (list of numbers) accepted through the command line. Use the debugging techniques shown in the class as an aid to design your programs. Write down the steps that you took to debug your program in your favorite IDE (include screenshots). You can use any modern programming language for this assignment. You can take input from user or hard code it in your program. Input size should at least 5. (10+10 points)

Submit: Source code, debug instructions and debug screenshots

18. Implement DFS and BFS graph traversal algorithms to traverse a given graph in the form of an adjacency matrix or an adjacency list. You can decide whether your graph will be directed or undirected. Take an input from users through command line. Print the time (as in counter we use in class like 0/0) when each vertex of the graph was discovered/processed. Support taking input up to 10 nodes/vertices. You can use any modern programming language for this assignment. (10 + 10 points) Submit: Source code and output