Solutions to Problem Set 9 (C7-C10)

Home Work 9 The problems in this problem set cover lectures C7, C8, C9 and C10 1. What is the Minimum Spanning Tree of the graph shown below using both Prim’s and Kruskal’s algorithm. Show all the steps in the computation of the MST (not just the final MST). Prim’s Algorithm Step 1. MST 1 Parent 2 Fringe Set 30 45 10 1 4 5 Step 2 2 10 MST 1 2 4 5 3 Fringe Set Step 3 10 MST 1 Fringe Set 5 2 35 25 5 30 Parent 20 2 4 3 6 1 25 20 30 1 50 Parent 6 Step 4 10 MST 1 20 2 25 5 Parent 6 5 20 35 6 4 3 Fringe Set Step 5 10 MST 1 20 2 6 20 5 25 5 35 Parent 3 Fringe Set 4 Minimum Spanning Tree 1 25 5 6 20 MST 35 10 20 2 3 4 Weight of the MST = 10 + 20 + 25 + 20 + 35 = 110 Kruskals Algorithm Initialization 2 2 45 4 5 50 35 3 1 5 4 6 3 55 30 1 20 10 20 25 6 Step 1 2 2 20 45 4 5 50 35 3 1 5 4 6 3 55 30 1 10 20 6 25 Step 2 2 2 20 4 45 5 35 3 1 5 55 30 1 10 50 6 25 4 20 6 3 Step 3 2 2 45 35 5 1 3 5 3 55 30 1 20 10 50 4 25 6 4 20 6 Step 4 2 2 45 5 35 3 1 5 3 55 30 1 10 20 50 4 6 4 20 25 6 Step 5 2 2 50 30 5 3 1 5 35 3 55 4 45 20 1 10 6 4 Weight of the MST = 10 + 20 + 20 + 25 + 35 = 110 20 6 25 2. Compute the computation complexity of the bubble sort algorithm. Show all the steps in the computation based on the algorithm. Algorithm Procedure Bubble_Sort(Input_Output_Array) N for I in 1 .. My_Array_Max loop for J in I+1 .. My_Array_Max loop if (Input_Output_Array(I) <= Input_Output_Array(J)) then Temp := Input_Output_Array(I); N-1 Input_Output_Array(I) := Input_Output_Array(J); Input_Output__Array(J) := Temp; end if; end loop; end loop; end Bubble_Sort; O(N(N-1)) = O(N2) 3. What are the best case and worst case computation complexity of: a. Inserting a node into an unsorted singly linked list Inserting into an unsorted singly linked list is carried out using the add_to_front operation. Both the best and worst case execution time is O(1). b. Inserting a node into a sorted singly linked list In the case of a sorted linked list, the list has to be traversed to find the right position. The list traversal takes O(n) in the worst case. Best case execution time is O(1) if the element being inserted is the smallest element in the list (list in ascending order) Worst case execution time is O(n) if the element being inserted is the largest element in the list (list in ascending order) 4. a. Design an Ada95 Package to: i. Read in N integers from an input file into an array. (N is user defined <=50) ii. Sort the array in ascending order iii. Perform binary search on the array. The package is designed as follows: Data Structures: type my_array is array (1 .. 50) of integer; Subprograms: -- procedure to create an array with <=50 elements -- assumes that input can be found in input_file.txt -- accepts the array -- returns array with elements read from file and the number of elements read procedure Create ( Num_Array : in out My_Array; Size : out Integer ); procedure Merge ( Input_Array : in out My_Array; Lb_1 : in Integer; Ub_1 : in Integer; Lb_2 : in Integer; Ub_2 : in Integer ); -- procedure to sort the array in ascending order -- accepts the array and the lowerbound(lb) and upperbound(ub) -- returns the sorted array procedure Merge_Sort ( Num_Array : in out My_Array; Lb : in Integer; Ub : in Integer ); --function to perform binary search on the array -- accepts the array, lb, ub and the element being searched for -- returns the index of the element if it is found -- returns -1 if the element is not found function Binary_Search ( Num_Array : My_Array; Lb : Integer; Ub : Integer; Looking_For : Integer ) return Integer; Algorithms: Create Pre-conditions: An array of 50 elements (num_array) Post-Condition: Array with a maximum of 50 elements loaded from the file, size of the array. Algorithm 1. Open the file input_file.txt 2. Initialize the counter to 0 3. While not End_Of_File (input_file) a. Increment the counter b. Read an element from the file into num_array(Counter) 4. Return num_array and Counter Merge_Sort Merge Sort is a sort algorithm that splits the items to be sorted into two groups, recursively sorts each group, and merges them into a final, sorted sequence. Pre-Conditions: An array of 1 or more elements Post-Condition : A sorted array Algorithm 1. Check if LB < UB a. Call merge sort with 1. Input Array 2. LB = LB 3. UB = (UB + LB)/2 b. Call merge sort with 1. Input Array 2. LB = (UB + LB)/2 + 1 3. UB = UB c. Call merge with 1. Merge with parameters ° Array to be sorted ° Lower bound ° (Lower bound + Upper bound) / 2 ° (Lower bound + Upper bound) / 2 +1 ° Upper bound The merge sort procedure will recursively call itself until it has only single element arrays. These are inherently sorted. It will then merge the successively larger elements until the whole sorted array is produced. Merge Pre-Conditions: An array of 1 or more elements, Legal values of Lower_Bound_1, Upper_Bound_1, Lower_Bound_2 and Upper_Bound_2, Post-Condition: A merged array that is sorted Algorithm 1. Check if a. Lower_Bound_1 < Upper_Bound_1 b. Lower_Bound_2 < Upper_Bound_2 c. Lower_Bound_1 < Lower_Bound_2 d. Upper_Bound_1 < Upper_Bound_2 2. If any of the above conditions are violated, a. Display Error b. Stop Executing the program 3. Set a. b. c. d. Index_1 := Lower_Bound_1; Index_2 := Lower_Bound_2; Index := Lower_Bound_1; Temp_Array := Input_Array 4. While (Index_1 <= Upper_Bound_1) and (Index_2 < =Upper_Bound_2) a. If (Input_Array(Index_1) < Input_Array (Index_2) i. Temp_Array(Index) := Input_Array(Index_1) ii. Index_1 := Index_1 + 1; iii. Index := Index + 1; b. Else i. Temp_Array(Index) := Input_Array(Index_2) ii. Index_2 := Index_2 + 1; iii. Index := Index + 1; 5. While (Index_1 <= Upper_Bound_1) a. Temp_Array(Index) := Input_Array(Index_1) b. Index_1 := Index_1 + 1; c. Index := Index + 1; 6. While (Index_2 <= Upper_Bound_2) a. Temp_Array(Index) := Input_Array(Index_2) b. Index_2 := Index_2 + 1; c. Index := Index + 1; 7. Input_Array := Temp_Array Binary Search Pre-Conditions: Array to be searched Item that you are searching for Post-condition: Index location of the item you are searching for Return –1 if the number is not found. Algorithm 1. Set Return_Index to –1; 2. Set Current_Index to (Upper_Bound - Lower_Bound + 1) /2. 3. Loop i. if the lower_bound > upper_bound Exit; ii. if ( Input_Array(Current_Index) = Number_to_Search) then Return_Index = Current_Index) Exit; iii. if ( Input_Array(Current_Index) > Number_to_Search) then Lower_Bound = Current_Index +1 else Upper_Bound = Current_Index – 1 4. Return Return_Index b. Write a program to test your package that will - Prompt the user for a number to search for. - If the number is found using the binary search algorithm - Display the location (index) - Display the number - If the number is not found using the binary search algorithm - Display “Number not in array to the user” ------------------------------------------------------------ program to test Home_Work_9 Package -- Programmer: Jayakanth Srinivasan -- Date Last Modified: April 06,2004 ---------------------------------------------------------with Ada.Text_Io; with Ada.Integer_Text_IO; with Home_Work_9; use Home_Work_9; procedure Test_Hw_9 is My_Test_Array : My_Array; Size : Integer; Location : Integer; Find : Integer; begin -- create the array Create(My_Test_Array,Size); -- get number to search for from user Ada.Text_Io.Put("Please Enter the Number to Search For"); Ada.Integer_Text_Io.Get(Find); -- display unsorted array to the user for I in 1..Size loop Ada.Text_Io.Put_Line(Integer'Image(My_Test_Array(I))); end loop; Ada.Text_Io.New_Line; -- sort the array using the merge sort algorithm Merge_Sort(My_Test_Array,1,Size); -- display the sorted algorithm for I in 1..Size loop Ada.Text_Io.Put_Line(Integer'Image(My_Test_Array(I))); end loop; -- perform a binary search on the array Location:= Binary_Search(My_Test_Array, 1, Size, Find); if Location /= -1 then Ada.Text_Io.Put("Found number at"); Ada.Text_Io.Put_Line(Integer'Image(Location)); Ada.Text_Io.Put_Line(Integer'Image(My_Test_Array(Location))); else Ada.Text_Io.Put_Line("Number Not Found in Array"); end if; end Test_Hw_9; 5. Implement the merge sort algorithm as an Ada95 program. Your program should - Read in N integers from an input file. (N is user defined <=50) - Sort using your merge sort implementation. - Display the sorted and unsorted inputs to the user Solved in problem 4.