Given. Undirected graph G with positive edge weights (connected). Goal. Find a min weight set of edges that connects all of the vertices. Write a greedy algorithm to solve this problem. 1. Given a set of positive integers X={x1,x2,,xn}, and an integer B, find a subset of X that has maximum sum not exceeding B. Write a dynamic programming algorithm that returns subset of integers. Example: X: {20,30,14,70,40,50,15,25,80,60,10,95:99} Find a subset of X with maximum sum not exceeding 99 . An optimal solution: 1358 with sum 20+14+40+25=99 1. Suppose that you want to get from vertex s to vertex t in an unweighted graph G=(V,E), but you would like to stop by vertex u to eat ice-cream. Describe an efficient algorithm that would determine an optimal s-t path given your preference for stopping at u along the way. Implement DFS to solve topological sorting problem. Input: unsorted array A of n integers. Target sum t. Goal: Write an O(n) time algorithm that determines whether or not there are two numbers x,y in A with x +y=t Given Two Balanced Binary Search Trees, there are n elements in the first BST and m elements in the second BST. Write an efficient algorithm to merge two balanced binary search trees to form a third balanced Binary Search Tree with (n+m) elements. Compute your time complexity. Implement radix sort algorithm to sort n integers in the range 1 to n2 in O(n) time. Compute/explain your time complexity. Implement SELECT (A,k) algorithm that returns the k th smallest element of A. Use the pseduocodes given in the lecture notes. Run it on some example input, explain each step in your code by using a debugger. The running time of SELECT algorithm is given as a recurrence relation in the lecture notes. Solve the recurrence using Substitution Method. Explain your solution (the proof of time complexity) as part of your video. Write merge algorithm that merges 2 sorted arrays. Compute your algorithm running time as a function of n. Example input =[1,4,5,8],[2,3,6,7] output =[1,2,3, 4,5,6,7,8] Then integrate merge algorithm into mergesort algorithm shown in class. Run it on some example input, explain each step by using a debugger