Data Structures and Algorithms in Java
6th Edition
ISBN: 9781118771334
Author: Michael T. Goodrich
Publisher: WILEY
expand_more
expand_more
format_list_bulleted
Videos
Textbook Question
Chapter 7, Problem 7R
Consider an implementation of the array list ADT using a dynamic array, but instead of copying the elements into an array of double the size (that is, from N to 2N) when its capacity is reached, we copy the elements into an array with ⌈N/4⌉ additional cells, going from capacity N to N +⌈N/4⌉. Show that performing a sequence of n push operations (that is, insertions at the end) still runs in O(n) time in this case.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
implement QuickSort of ints that sorts the numbers in the non-decreasing order.
Implement the rearrange function using QuickSort ( such that the pivot is set on the extreme left and the rearrangement is carried on on two pointers) using the O(n) time algorithmThe function gets as input an array, and index of the pivot.The function rearranges the array, and returns the index of the pivot after the rearrangement. int rearrange(int* A, int n, int pivot_index);
Implement the QuickSort algorithm.
- For n<=2 the algorithm just sorts the (small) array (smaller number first).
- For n>=3 the algorithm uses the rearrange function with the pivot chosen to be the
median of A[0], A[n/2], A[n-1].
void quick_sort(int* A, int n);
Given an integer array A of size N where every element is in the range [0, 9]. When traversing
the array, one could move from index į to index (i-1), index (i+1) or index j # į such that A[i]=A[j].
For example, given A = {4, 3, 1, 6, 3, 7, 1}, one can move
• From A[0] to A[1]
• From A[1] to A[2], A[0] or A[4] (since A[4]=A[1]=3)
• From A[2] to A[3], A[1] or A[6] (since A[6]=A[2]=1)
From A[3] to A[4], A[2]
• And so on.
The task is to compute the minimum number of moves to reach to the last index of
the array starting from the first index.
Examples:
Input: A = {1, 2, 3, 4, 1, 5}
Output: 2
Explanation: First move from A[0] to A[4] and then from A[4] to A[5].
Input: A = {1, 2, 3, 4, 5, 1}
Output: 1
Explanation: Move from A[O] to A[5].
6.
Input: A = {1, 2, 3, 4, 5, 6, 7, 3, 4, 5, 4, 3, 6, 1, 5, 5, 4, 4, 7, 7}
Output: 5
Explanation: Move from A[0] to A[13], from A[13] to A[12], from A[12] to A[5], from A[5] to
A[6], from A[6] to A[19].
a) Explain how you would represent this problem as a…
Develop and implement a version of mergesort that does not rearrange the array, but returns an int[] array perm such that perm[i] is the index of the i th smallest entry in the array.
Chapter 7 Solutions
Data Structures and Algorithms in Java
Additional Engineering Textbook Solutions
Find more solutions based on key concepts
A nozzle at A discharges water with an initial velocity of 36 ft/s at an angle with the horizontal. Determine ...
Vector Mechanics For Engineers
Why is the study of database technology important?
Database Concepts (8th Edition)
How are relationships between tables expressed in a relational database?
Modern Database Management
The solid steel shaft AC has a diameter of 25 mm and is supported by smooth bearings at D and E. It is coupled ...
Mechanics of Materials (10th Edition)
What types of coolant are used in vehicles?
Automotive Technology: Principles, Diagnosis, And Service (6th Edition) (halderman Automotive Series)
How does a computers main memory differ from its auxiliary memory?
Java: An Introduction to Problem Solving and Programming (8th Edition)
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
- In an array-based implementation of a List, why does the add operation take O(n) time in the average case? Select one: a. The time it takes to shift entries over to make room in the array depends on the number of entries in the List b. The time to copy the current entries into a newly allocated, larger array depends on the number of entries in the List c. The time to access the position in the array to add the new entry depends on the number of entries in the List d. The time to access the position in the array to add the new entry depends on the capacity of the arrayarrow_forwardsolve this. In between.arrow_forwardWrite a function that gets an array of ints of length n, and a number k, and returns the longest subsequence of consecutive k’s in the array. For example - On input ([1, 1, 3, 3, 3, 1, 5, 1], 1), the function returns 3 - On input ([1, 3, 3, 2, 3, 3, 3, 3], 3), the function returns 4 - On input ([3, 5, 2, 5, 2, 5, 5], 3), the function returns 2 - On input ([1, 2, 3, 3, 3, 3], 5), the function returns 0 // returns the length of the longest subsequence // of consecutive k’s in the array int longest_seq(const int* ar, int n, int k); test for the function: void test_q1() { inta1[] = {1, 1, 3, 3, 3, 1, 5, 1}; if (longest_seq(a1, 8, 1) == 2) printf("Q1-1 ok\n"); else printf("Q1-1 ERROR\n"); inta2[] = {1,3,3,2,3,3,3,3}; if (longest_seq(a2, 8, 3) == 4) printf("Q1-2 ok\n"); else printf("Q1-2 ERROR\n"); }arrow_forward
- In searching an element in an array, linear search can be used, even though simple to implement, but not efficient, with only O(n) time complexity. Assuming the array is already in sorted order, modify the search function below, using a better algorithm, so the average time complexity for the search function is O(log n). include <iostream> using namespace std; int search(int al), int s, int v) { 1/ Modify below codes. for (int i = 0; i <s; i++) { if (a[i] = v) return i; return -1; int main() { int intArray:10] = { 5, 7, 8, 9, 10, 12, 13, 15, 20, 34); // Search for element '12' in 10-elements integer array. cout << search(intArray, 10, 12); // '5' will be printed out. // Search for element '35' in 10-elements integer array. cout << search(intArray, 10, 35); // '-1' will be printed out. // Index '-l' means that the element is not found. return 0;arrow_forwardWrite a bottom-up mergesort that makes use of the array's order by carrying out the following steps each time it needs to locate two arrays to merge: locate the first element in an array that is smaller than its predecessor, then locate the next, and finally merge them to form a sorted subarray. Consider the array size and the number of maximal ascending sequences in the array while analysing the running time of this method.arrow_forwardGive explained solution!arrow_forward
- Implement the algorithm in Python, and test itarrow_forwardGiven an array of integers arr, sort the array by performing a series of pancake flips. In one pancake flip we do the following steps: Choose an integer k where 1 <= k <= arr.length. Reverse the sub-array arr[0...k-1] (0-indexed). For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3. Print out the k-values corresponding to a sequence of pancake flips that sort arr. Example 1: Input: arr = [3,2,4,1] Output: 4, 2, 4, 3 Explanation: We perform 4 pancake flips, with k values 4, 2, 4, and 3. Starting state: arr = [3, 2, 4, 1]. After 1st flip (k = 4): arr = [1, 4, 2, 3] After 2nd flip (k = 2): arr = [4, 1, 2, 3] After 3rd flip (k = 4): arr = [3, 2, 1, 4] After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted. Another potential solution is: Output = 3, 4, 2, 3, 1, 2, 1, 1 with a similar explanation. All potential solutions that solve the problem are…arrow_forwardYou are given an array of positive integers S[1, . . . , n]. You are initially positioned at the array’s first index 1, and each element S[i] represents your maximum length of jump at position i. For example, you can jump from position i to any position among i + 1, . . . , i + S[i]. Return true if you can reach the last index, or false otherwise. Precisely define the subproblem.Provide the recurrence equation.Describe the algorithm in pseudocode to compute the optimal value.Describe the algorithm in pseudocode to print out an optimal solution.arrow_forward
- Prove that when using a dynamic array that grows and shrinks as in the</o:p> previous exercise, the following series of 2n operations takes O(n) time:</o:p> n append operations on an initially empty array, followed by n pop operations.</o:p> </o:p>arrow_forwardCreate a bottom-up mergesort that takes advantage of array order by doing the following each time it has to identify two arrays to merge: locate a sorted subarray (by incrementing a pointer until it finds an entry in the array that is smaller than its predecessor), then locate the next, and finally merge them. Examine the algorithm's running time in terms of array size and the number of maximal rising sequences in the array.arrow_forwardWrite a program that produces a best-case array (with no duplicates) for sort(). an array of N items with distinct keys having the property that every partition will produce subarrays that differ in size by at most 1 (the same subarray sizes that would happen for an array of N equal keys). (For the purposes of this exercise, ignore the initial shuffle.)arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage Learning
C++ Programming: From Problem Analysis to Program...
Computer Science
ISBN:9781337102087
Author:D. S. Malik
Publisher:Cengage Learning
Definition of Array; Author: Neso Academy;https://www.youtube.com/watch?v=55l-aZ7_F24;License: Standard Youtube License