Question: 1. Consider the following sorting algorithm: ALGORITHM INPUT: array a OUTPUT: sorted array a Find the smallest element in the tail of the array ali

1. Consider the following sorting algorithm: ALGORITHM INPUT: array a OUTPUT:

1. Consider the following sorting algorithm: ALGORITHM INPUT: array a OUTPUT: sorted array a Find the smallest element in the tail of the array ali n], call it alj] Swap it with a [0], if it is smaller than a[O] Repeat this process with index 1, 2, until the whole array is sorted. (a) Write pseudocode for the given algorithm. (h) Program your pseudo(ode and attach it to this assigillient (Java. Pythonor C++, only (c) Give the best-case and worst-case running times of sort in e-notation. 2. (a) Write a recursive algorithm with worst-case running time O(log n) and best-case running time O(1) that scarches a sorted array for a given element and either returns the index of the element or -1 if it is not found in the array (b) Give the pseudocode for the algorithm in part (a). (e) Program your psendocode and attach t to this assignment (Java, Python, or C++, only (d) Prove that your algorithm meets the efficiency considerations described in part (a)

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!

Problem 1: Random Binary Search (20 points total) 1 Consider the Following Problem: Input: a sorted array A of length n, and a target number k Output: index such that A[i]-k, or no solution if none...

CS 344 Sections 1,2,3 Fall 2018 Homework 4. Due Tuesday, November 13, 11:55pm 80 points total plus extra credit Problem 1: Random Binary Search (20 points total) 1 Consider the Following Problem: ....

Data Structures Exercise 1 1. Consider the following recursive algorithm for sorting a given array A. First, find the maximal and minimal elements in A. Swap the maximal element with the last element...

2. This problem on sorting algorithms. (a) Consider the following insertion sort algorithm. Input: Array a of size n, consisting of integers. for i in range [1, n-1] f while (j 0 AND alj-1] alj]) C...

Problem 1: Random Binary Search (20 points total 1 Consider the Following Problem: Input: a sorted array A of length n, and a target number k . Output: index i such that Alf] k, or no solution if...

Exercise I (25 points) (See Appendix...) Consider two algorithms A1 and A2 that have the running times T1(n) and T2(n), respectively. T1(n)=100n2+100nlg(n)andT2(n)=0.1n2+0.1nlg(n) a) (24 points) Use...

Problem 1: Random Binary Search (20 points total) 1 Consider the Following Problem: Input: a sorted array A of length n, and a target number k Output: index i such that Ali] -k, or no solution if...

1. (10 points) (Formally) Prove or disprove T(n) = 0() by using the definitions of the notations involved or disprove it by giving a counterexample. 2. (10 Points) Given the following sorting...

Given the following sorting algorithm, Input: an array of N integers, A Output: print out a sequence of integers in an ascending order Algorithm: - While (the array is not empty) find the maximum...

I've written six functions to code for the following six sorting algorithms in C++ via headers. a. Selection Sort b. Bubble Sort c. Insertion Sort d. Merge Sort e. Quick Sort f. Heap Sort The header...

Burger Universe charges an initial franchise fee of $225,000. Upon the signing of the agreement, a payment of $25,000 is due. Thereafter, five annual payments of $40,000 are required. The credit...

Newsome Inc. buys on terms of 3/15, net 45. It does not take the discount, and it generally pays after 60 days. What is the nominal annual percentage cost of its non-free trade credit, based on a...

All of the following statement are true regarding warrants EXCEPT: The price of the warrant will vary with the price movements of the underlying stock At issuance, the exercise price of the warrant...

Question One The following water gas fuel is being burned: Analysis by volume % CO H2 56 CH 24 N2 5 CO2 3 12 Calculate the adiabatic flame temperature when A. The gas is burned with air enriched to...

Go to the website of the Federal Reserve Bank of St. Louis (http://www.stlouisfed.org) to find some information about the Fed. Find a map of the Federal Reserve districts. If you live in the United...

Suppose that the T-account for First National Bank is as follows: Assets Liabilities Reserves $100,000 Deposits $500,000 Loans 400,000 a. If the Fed requires banks to hold 5 percent of deposits as...

Imagine that you intend to buy a portfolio of ten stocks with some of your savings. Should the stocks be of companies in the same industry? Should the stocks be of companies located in the same...