Homework Answers
1) False. In case of all the sorting algorithms more than n comparisons are required.
2) true in case of small arrays. but false in case of larger arrays.
3) true for n distinct elements there are total n! ordering possibles.
4) True . there is at least one ordering that requires nlogn comparsions. This is optimal comparison used in heapsort.
NOTE:-
1) Don't forget to upvote. For any doubts ask in comments sections.
Add Answer to:
Suppose we have an algorithm A that does comparison-based sorting. Answer true or false for each...
(f) True False Comparison-based sorting methods h e Comparison-based sorting methods have a lower bound of...
(f) True False Comparison-based sorting methods h e Comparison-based sorting methods have a lower bound of O(n logn) on their running time. (8) True False A vertex cover of a graph is a set of edges that touch every verte (h) True False We can find the largest independent set of a graph in polynomial time. (i) True False We can prove that P PSPACE. (j) True False We can reduce SAT to 3-SAT, and 3-SAT to SAT. (k) True...
Data Structures: For each of the following situations, name the best sorting algorithm we studied. (For...
Data Structures: For each of the following situations, name the best sorting algorithm we studied. (For one or two questions, there may be more than one answer deserving full credit, but you only need to give one answer for each.) (a) The array is mostly sorted already (a few elements are in the wrong place). (b) You need an O(n log n) sort even in the worst case and you cannot use any extra space except for a few local...
C++ Sorting and Searching 1. Mark the following statements as true or false. a. A sequential...
C++ Sorting and Searching 1. Mark the following statements as true or false. a. A sequential search of a list assumes that the list elements are sorted in ascending order. b. A binary search of a list assumes that the list is sorted. 2. Consider the following list: 63 45 32 98 46 57 28 100 Using a sequential search, how many comparisons are required to determine whether the following items are in the list or not? (Recall that comparisons...
1. Consider the following well-known sorting algorithm, which is studied later in the book, with a...
1. Consider the following well-known sorting algorithm, which is studied later in the book, with a counter inserted to count the number of key comparisons. ALGORITHM SortAnalysis(A[0..n − 1]) //Input: An array A[0..n − 1] of n orderable elements //Output: The total number of key comparisons made count ←0 for i ←1 to n − 1 do v ←A[i] j ←i − 1 while j ≥ 0 and A[j ]> v do count ←count + 1 A[j + 1]←A[j ]...
in C++ HeapSort Implement the heapsort algorithm for sorting an array of integers. Input structure Each...
in C++
HeapSort Implement the heapsort algorithm for sorting an array of integers. Input structure Each case starts with an integer number which indicates the number of elements to be sorted. Then, the elements follow, one per line. You can assume the input is correctly structured (i.e., no data are missing Output structure Output the sorted sequence separeted by";" (in non-decreasing order). Do not insert spaces or a new line at the beginning or at the end of any element.
Need help with program. I'm stuck Objectives: In this assignment, we will practice manipulating lists of...
Need help with program. I'm stuck
Objectives: In this assignment, we will
practice manipulating lists of data and arranging items in an
ascending/descending order. you will also explore storing
lists/arrays using different sorting algorithms including, the
selection sort, bubble sort, and insertion sort algorithm.
Comparison between the three algorithms are made based on the
number of comparisons and item assignments (basic operations) each
algorithms executes.
Background: Ordering the elements of a list is
a problem that occurs in many computer...
I need the report like this (idea) *Sorting Algorithms: A sorting algorithm is an algorithm that...
I need the report like this (idea) *Sorting Algorithms: A sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists; it is also often useful for canonical zing data and for producing human-readable output. More formally, the output must satisfy...
I need help In the lecture you got acquainted with the median algorithm, which calculates the median of an unsorted array with n∈N elements in O (n). But the algorithm can actually do much more: it is...
I need help In the lecture you got acquainted with the median algorithm, which calculates the median of an unsorted array with n∈N elements in O (n). But the algorithm can actually do much more: it is not limited to finding only the median, but can generally find the ith element with 0≤i <n. Implement this generic version of the median algorithm by creating a class selector in the ads.set2.select package and implementing the following method: /** * Returns the...
algorithm TRUE OR FALSE TRUE OR FALSE Optimal substructure applies to alloptimization problems. ...
algorithm TRUE OR FALSE TRUE OR FALSE Optimal substructure applies to alloptimization problems. TRUE OR FALSE For the same problem, there might be different greedy algorithms each optimizes a different measure on its way to a solutions. TRUE OR FALSE Computing the nth Fibonacci number using dynamic programming with bottom-upiterations takes O(n) while it takes O(n2) to compute it using the top-down approach. TRUE OR FALSE Every computational problem on input size n can be...
Hello I need help with this program. Should programmed in C! Program 2: Sorting with Pointers...
Hello I need help with this program. Should programmed in C!
Program 2: Sorting with Pointers Sometimes we're given an array of data that we need to be able to view in sorted order while leaving the original order unchanged. In such cases we could sort the data set, but then we would lose the information contained in the original order. We need a better solution. One solution might be to create a duplicate of the data set, perhaps make...
(f) True False Comparison-based sorting methods h e Comparison-based sorting methods have a lower bound of O(n logn) on their running time. (8) True False A vertex cover of a graph is a set of edges that touch every verte (h) True False We can find the largest independent set of a graph in polynomial time. (i) True False We can prove that P PSPACE. (j) True False We can reduce SAT to 3-SAT, and 3-SAT to SAT. (k) True...
in C++
HeapSort Implement the heapsort algorithm for sorting an array of integers. Input structure Each case starts with an integer number which indicates the number of elements to be sorted. Then, the elements follow, one per line. You can assume the input is correctly structured (i.e., no data are missing Output structure Output the sorted sequence separeted by";" (in non-decreasing order). Do not insert spaces or a new line at the beginning or at the end of any element.
Need help with program. I'm stuck
Objectives: In this assignment, we will
practice manipulating lists of data and arranging items in an
ascending/descending order. you will also explore storing
lists/arrays using different sorting algorithms including, the
selection sort, bubble sort, and insertion sort algorithm.
Comparison between the three algorithms are made based on the
number of comparisons and item assignments (basic operations) each
algorithms executes.
Background: Ordering the elements of a list is
a problem that occurs in many computer...
Hello I need help with this program. Should programmed in C!
Program 2: Sorting with Pointers Sometimes we're given an array of data that we need to be able to view in sorted order while leaving the original order unchanged. In such cases we could sort the data set, but then we would lose the information contained in the original order. We need a better solution. One solution might be to create a duplicate of the data set, perhaps make...
Most questions answered within 3 hours.
-
QUESTION 26
The oxidation number of hydrogen in both sides of the following
reaction 2 C2H6...
asked 5 minutes ago -
An inventor proposes to utilize a surplus ship propeller of
diameter d = 2m as an...
asked 14 minutes ago -
Supply management Case on Sales Forecasts: Fact or Fiction
Vignette in Chapter 20. Be sure to...
asked 21 minutes ago -
1. What is job rationing and how does it relate to unemployment?
Explain what factors can...
asked 21 minutes ago -
How do Insult and innuendo affect workplace negativity
especially from employees?
what is emotional damping and...
asked 23 minutes ago -
Subject:Operations Management
Book: Introduction to Operations & Supply Chain Management
3rd Edition
1. We noted that...
asked 29 minutes ago -
how do psychological processes and mechanisms relate
to our relationship with God
asked 34 minutes ago -
4. Which of the following would be a logical treatment for
septic shock? Explain your reasoning...
asked 36 minutes ago -
A researcher claims that at least 10% of young children suffer
from some food allergy. A...
asked 51 minutes ago -
Describe the difference between a Change Order (CO), a
Request For Information (RFI), and submittals? Give...
asked 50 minutes ago -
Help
can you do this?
C programming
Overview
In this program, you will be taking product...
asked 1 hour ago -
The given plaintext is “Feistel
cipher structure uses the same algorithm for both encryption and
decryption”....
asked 1 hour ago