Collaboration groups will be set up in Blackboard by the end of the week; however, there are nocollaborative problems on this first assignment. All solutions are to be the result of individual effort.Self-Study ProblemsAll of the following problems come from the textbook and have solutions posted on the web athttp://mitpress.mit.edu/algorithms.You are permitted to use this site to examine solutions for these problems as a means of selfchecking your solutions. These problemswill not be graded.Problems: 2.2-2, 2.3-5, 3.1-2, 12.1-2, 12.3-3, 21.2-6.Problems for Grading1. Problem 1 Chapter 220 Points TotalUse induction to prove Pn i=1 i3 = n(n2 +1)2.2. Problem 2 Parts a, b, c, d, e and f30 Points Total 5 Points EachAlthough merge sort runs in Θ(nlgn) worst-case time and insertion sort runs in Θ(n2) worst-casetime, the constant factors in insertion sort can make it faster in practice for small problem sizeson many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertionsort within merge sort when subproblems become sufficiently small. Consider a modification tomerge sort in which n/k sublists of length k are sorted using insertion sort and then mergedusing the standard merging mechanism, where k is a value to be determined.(a) Use insertion sort to sort the unsorted array . Makesure to show the array after every pass.(b) Use merge sort to sort the unsorted array . Make sureto show the steps of splitting the array then merging the array.(c) Show that insertion sort can sort the n/k sublists, each of length k, in Θ(nk) worst-case time.(d) Show how to merge the sublists in Θ(nlg(n/k)) worst-case time.(e) Given that the modified algorithm runs in Θ(nk + nlg(n/k)) worst-case time, what is thelargest value of k as a function of n for which the modified algorithm has the same running timeas standard merge sort, in terms of Θ-notation?(f) How should we choose k in practice?13. Problem 315 Points TotalWrite a Θ(m + n) algorithm that prints the in-degree and the out-degree of every vertex in anm-edge, n-vertex directed graph where the directed graph is represented using adjacency lists.4. Problem 4 Chapter 12 Binary Search Trees15 Points Total 3 Points EachExercise 12.2-1. Suppose that we have numbers between 1 and 1000 in a binary search treeand we want to search for the number 363. Which of the following sequences could not be thesequence of nodes examined?i. 2, 252, 401, 398, 330, 397, 363.ii. 924, 220, 911, 244, 898, 258, 362, 363.iii. 925, 202, 911, 240, 912, 245, 363.iv. 2, 399, 387, 219, 266, 382, 381, 278, 363.v. 935, 278, 347, 621, 299, 392, 358, 363.5. Problem 5 Chapter 12 Binary Search Trees20 PointsConsider the following algorithm for doing a postorder traversal of a binary tree with root vertexroot.Algorithm 1 Postorder TraversalPostorder(root)1 if root 6= null2 Postorder(root.left)3 Postorder(root.right)4 visit root;Prove that this algorithm runs in time Θ(n) when the input is an n-vertex binary tree.2