C-7.29 Revise the array list implementation given in Section 7.2.1 so that when the ac- tual number of elements, n, in the array goes below N/4, where N is the array capacity, the array shrinks to half its size. C-7.30 Prove that when using a dynamic array that grows and shrinks as in the previous exercise, the following series of 2n operations takes O(n) time: n insertions at the end of an initially empty list, followed by n deletions, each from the end of the list. C-7.31 Give a formal proof that any sequence of n push or pop operations (that is, in- sertions or deletions at the end) on an initially empty dynamic array takes O(n) time, if using the strategy described in Exercise C-7.29. C-7.32 Consider a variant of Exercise C-7.29, in which an array of capacity N is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/4. Give a formal proof that any sequence of n push or pop operations on an initially empty dynamic array takes O(n) time. C-7.33 Consider a variant of Exercise C-7.29, in which an array of capacity N, is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/2. Show that there exists a sequence of n push and pop operations that requires (n²) time to execute.
C-7.29 Revise the array list implementation given in Section 7.2.1 so that when the ac- tual number of elements, n, in the array goes below N/4, where N is the array capacity, the array shrinks to half its size. C-7.30 Prove that when using a dynamic array that grows and shrinks as in the previous exercise, the following series of 2n operations takes O(n) time: n insertions at the end of an initially empty list, followed by n deletions, each from the end of the list. C-7.31 Give a formal proof that any sequence of n push or pop operations (that is, in- sertions or deletions at the end) on an initially empty dynamic array takes O(n) time, if using the strategy described in Exercise C-7.29. C-7.32 Consider a variant of Exercise C-7.29, in which an array of capacity N is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/4. Give a formal proof that any sequence of n push or pop operations on an initially empty dynamic array takes O(n) time. C-7.33 Consider a variant of Exercise C-7.29, in which an array of capacity N, is resized to capacity precisely that of the number of elements, any time the number of elements in the array goes strictly below N/2. Show that there exists a sequence of n push and pop operations that requires (n²) time to execute.
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Java
Please help with question: C 7.33:
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps