Run the following All-Pair-Shortest-Paths algorithms on the weighted and directed graph. i. EXTEND-SHORTEST-PATHS algorithm ii. Floyd-Warshall algorithm

Define an algorithm. List three important characteristics of a good algorithm and explain why each is important.

Define Relaxation. Run the Bellman-Ford algorithm on the directed graph of the figure, using vertex "s" as the source. In each pass, relax edges in the same order as in the figure, and show the d and fl values after each pass. Now, change the weight of edge .(z,x) to 4 and run the algorithm again, using s as the source.

Define bipartite graph. Write down the algorithm of Edmonds-Karp and when we use the algorithm with appropriate example.

Sort the array [5, 1, 4, 2, 8] using bubble sort. Show the array after each full pass of comparisons and swaps.

Explain counting sort and identify when it is most efficient.

Topological sort algorithm for Directed Acyclic Graph (DAG) is a linear arrangement of vertices such that for every directed edge x-y, vertex x comes before y in the arrangement. Topological sorting is only applicable on graphs that are DAG. Now your task is to prove that from the above graph that, "There can exist more than one topological sorting for a given graph." Using i. DFS ii. Kahn's Algorithm

Consider the following adjacent list for directed graph. adj(y)= [x], adj(x) = [z], adj(z) = [y,w], adj(w)= [x], adj(s) = [z,w], adj(v) = [s,w], adj(t)=(u,v), adj(u) = [v]. i. Draw a graph from the above information. ii. Rewrite the procedure DFS, using a stack to eliminate recursion. iii. Identify the tree edge, back edge, cross edge and forward edge for the graph.

Consider the foiling weighted and undirected graph to find the path from A to every other vertexs using Dijkstra's algorithm.

Define disjoint set and answer the following questions. i. Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set. ii. During the execution of CONNECTED-COMPONENTS on an undirected graph G(V,E) with k connected components, how many times is FIND-SET called? How many times is UNION called? Express your answers in terms of IVI, |E|, and k.

Using the divide and conquer approach, explain how to find the maximum element in an array. Draw a diagram showing the recursive division of the array.

Define divide and conquer. Write down the pseudo code for finding the result of 7^54 % 8. using divide and conquer.

Find Longest Common Subsequence using Dynamic Programming Technique with illustration X={A, B, C, B,D, A,B) and Y={B,D,C,A,B,A}.

Define bipartite graph. Write down the algorithm of Edmonds-Karp and when we use the algorithm with appropriate example.

Write down the number of hits does the following string matching algorithms encounter in the text T=abahababaaba when looking for the pattern P=ababa using Finite state automata algorithm.

Run the following All-Pair-Shortest-Paths algorithms on the weighted and directed graph. i. EXTEND-SHORTEST-PATHS algorithm ii. Floyd-Warshall algorithm

What do you mean by flow network and residual network? Use the Ford-Fulkerson Algorithm to find a flow function that maximizes the flow in the below network having the capacities shown and calculate the total flow that results. List the augmenting paths that you use to get your solution in order to get full credit.

Given the following points: Perform Graham Scan step by step and list the final convex hull vertices in order.

Consider the foiling weighted and undirected graph to find the path from A to every other vertexs using Dijkstra's algorithm.

Consider the given weighted graph. i. Run Prim's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree. ii. Run Kruskal's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree.

Define Relaxation. Run the Bellman-Ford algorithm on the directed graph of the figure, using vertex "s" as the source. In each pass, relax edges in the same order as in the figure, and show the d and fl values after each pass. Now, change the weight of edge .(z,x) to 4 and run the algorithm again, using s as the source.

What do you mean by flow network and residual network? Use the Ford-Fulkerson Algorithm to find a flow function that maximizes the flow in the below network having the capacities shown and calculate the total flow that results. List the augmenting paths that you use to get your solution in order to get full credit.

Run the following All-Pair-Shortest-Paths algorithms on the weighted and directed graph. i. EXTEND-SHORTEST-PATHS algorithm ii. Floyd-Warshall algorithm

Consider the following adjacent list for directed graph. adj(y)= [x], adj(x) = [z], adj(z) = [y,w], adj(w)= [x], adj(s) = [z,w], adj(v) = [s,w], adj(t)=(u,v), adj(u) = [v]. i. Draw a graph from the above information. ii. Rewrite the procedure DFS, using a stack to eliminate recursion. iii. Identify the tree edge, back edge, cross edge and forward edge for the graph.

Consider the following adjacent list for directed graph. adj(y)= [x], adj(x) = [z], adj(z) = [y,w], adj(w)= [x], adj(s) = [z,w], adj(v) = [s,w], adj(t)=(u,v), adj(u) = [v]. i. Draw a graph from the above information. ii. Rewrite the procedure DFS, using a stack to eliminate recursion. iii. Identify the tree edge, back edge, cross edge and forward edge for the graph.

Define disjoint set and answer the following questions. i. Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set. ii. During the execution of CONNECTED-COMPONENTS on an undirected graph G(V,E) with k connected components, how many times is FIND-SET called? How many times is UNION called? Express your answers in terms of IVI, |E|, and k.

Consider a hash table of size 7 with hash function h(k) = k mod 7. Draw the table that results after inserting in the given order, the values, 15, 25, 12, 43, 17, 21, 79 for each of the scenarios below: i) When collisions are handled by separate chaining. ii) When collisions are handled by linear probing. iii) When collisions are handled by double hashing. Using a second hash function h'(k)=5-(k mod 5).

Sort the array [8, 3, 5, 4, 6] using insertion sort. Show each step of inserting elements into the sorted portion.

Topological sort algorithm for Directed Acyclic Graph (DAG) is a linear arrangement of vertices such that for every directed edge x-y, vertex x comes before y in the arrangement. Topological sorting is only applicable on graphs that are DAG. Now your task is to prove that from the above graph that, "There can exist more than one topological sorting for a given graph." Using i. DFS ii. Kahn's Algorithm

Consider the given weighted graph. i. Run Prim's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree. ii. Run Kruskal's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree.

Define a Linked List. Write a function to insert an element in the middle of a Linked List. Let consider the following linked list with 12 as the head. Now write an algorithm to insert a new node (15) in the middle of node 18 and 7.

Find Longest Common Subsequence using Dynamic Programming Technique with illustration X={A, B, C, B,D, A,B) and Y={B,D,C,A,B,A}.

Sort the following array using merge sort and show each step: [38, 27, 43, 3, 9, 82, 10]

Illustrate the operation of merge sort on the array A<41, 52, 26, 38, 57, 9, 49 >. Explain Worst case, Best case, and Average Case complexity of Insertion sort.

Consider the given weighted graph. i. Run Prim's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree. ii. Run Kruskal's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree.

Consider the given weighted graph. i. Run Prim's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree. ii. Run Kruskal's algorithm starting from vertex A. Write the edges in the order which they are added to the minimum spanning tree.

Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.

Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.

Sort the array [170, 45, 75, 90, 802, 24, 2, 66] using radix sort. Show the array after sorting by each digit place.

Define Relaxation. Run the Bellman-Ford algorithm on the directed graph of the figure, using vertex "s" as the source. In each pass, relax edges in the same order as in the figure, and show the d and fl values after each pass. Now, change the weight of edge .(z,x) to 4 and run the algorithm again, using s as the source.

Illustrate the operation of merge sort on the array A<41, 52, 26, 38, 57, 9, 49 >. Explain Worst case, Best case, and Average Case complexity of Insertion sort.

Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue.

Use Strassen's algorithm to compute the matrix product below. Show your work.

Write down the number of hits does the following string matching algorithms encounter in the text T=abahababaaba when looking for the pattern P=ababa using Finite state automata algorithm.

Compare the time complexities of O(n log n) and O(n2). For an input size of n = 16 and n = 64, calculate the approximate number of operations assuming 1 operation per unit of complexity.

Illustrate the operation of merge sort on the array A<41, 52, 26, 38, 57, 9, 49 >. Explain Worst case, Best case, and Average Case complexity of Insertion sort.

Topological sort algorithm for Directed Acyclic Graph (DAG) is a linear arrangement of vertices such that for every directed edge x-y, vertex x comes before y in the arrangement. Topological sorting is only applicable on graphs that are DAG. Now your task is to prove that from the above graph that, "There can exist more than one topological sorting for a given graph." Using i. DFS ii. Kahn's Algorithm

Represent the tower of hanoi problem using master theorem of recurrence.