Suppose you have an unsorted array A containing n distinct integers in the range 0 to...

Transcribed Image Text:

Suppose you have an unsorted array A containing n distinct integers in the range 0 to n, where n = 2* - 1 for some positive integer k. Each integer in the range 0 to n appears exactly once in the array, except for one missing integer. Design a Divide and Conquer algorithm to find the missing number. Argue informally that your algorithm is correct and analyze its running time. Q2. (5 points) Write a recursive Java function to print all permutations of a string. For example; all possible permutations of "abc" are: "abc", "acb", "bac", "bca", "cab", and "cba". a. (3 points) Submit the Java code for testing the function. b. (2 points) Analyze the running time of your function with explanation. Q3. (5 points) Write a recursive Java function to Binary() that convert a given decimal number to binary. a. (3 points) Submit the Java code for testing the function. b. (2 points) Analyze the running time of your function with explanation. Q4. (15 points) Binary Insertion Sort is a sorting algorithm that is similar to Insertion Sort, but instead of using linear search to find the location where to insert an element, it uses binary search. a. (10 points) Write a Java program that generates a list of N random integers and sorts them in increasing order using each of the two algorithms: Insertion Sort and Binary Insertion Sort. b. (5 points) Measure the execution time for each of the two algorithms for randomly generated lists of size N = 40000, 100000, 200000, and 400000. Present your results in a table as shown below and plot the results in a chart. For each value of N, run your program 5 times and write in the table the average of the 5 runs. Insertion Sort Binary Insertion Sort N= 40,000 Run Time (average of 5 runs) N=100,000 N=200,000 N=400,000 Important Note: For each value of N, the two algorithms must sort the same list. Make sure you keep a copy of the generated list before sorting it with one of the algorithms and use the saved original copy (not the sorted list) as input for the second algorithm. Suppose you have an unsorted array A containing n distinct integers in the range 0 to n, where n = 2* - 1 for some positive integer k. Each integer in the range 0 to n appears exactly once in the array, except for one missing integer. Design a Divide and Conquer algorithm to find the missing number. Argue informally that your algorithm is correct and analyze its running time. Q2. (5 points) Write a recursive Java function to print all permutations of a string. For example; all possible permutations of "abc" are: "abc", "acb", "bac", "bca", "cab", and "cba". a. (3 points) Submit the Java code for testing the function. b. (2 points) Analyze the running time of your function with explanation. Q3. (5 points) Write a recursive Java function to Binary() that convert a given decimal number to binary. a. (3 points) Submit the Java code for testing the function. b. (2 points) Analyze the running time of your function with explanation. Q4. (15 points) Binary Insertion Sort is a sorting algorithm that is similar to Insertion Sort, but instead of using linear search to find the location where to insert an element, it uses binary search. a. (10 points) Write a Java program that generates a list of N random integers and sorts them in increasing order using each of the two algorithms: Insertion Sort and Binary Insertion Sort. b. (5 points) Measure the execution time for each of the two algorithms for randomly generated lists of size N = 40000, 100000, 200000, and 400000. Present your results in a table as shown below and plot the results in a chart. For each value of N, run your program 5 times and write in the table the average of the 5 runs. Insertion Sort Binary Insertion Sort N= 40,000 Run Time (average of 5 runs) N=100,000 N=200,000 N=400,000 Important Note: For each value of N, the two algorithms must sort the same list. Make sure you keep a copy of the generated list before sorting it with one of the algorithms and use the saved original copy (not the sorted list) as input for the second algorithm.

Answer rating: 100% (QA)

Solution Lets break down each question and provide solutions Q1 Divide and Conquer Algorithm To find the missing number in an unsorted array we can use a Divide and Conquer algorithm Heres an informal ... View the full answer