Data Structures, Algorithms, and Applications in Java
No 1.
The array a[0:9] = [4, 2, 6, 7, 1, 0, 9, 8, 5, 3] is to be sorted using insertion sort(Program 2.14).
Draw a figure similar to Figure 2.5(c) to show the progress of the sort method.
No 2.
Extend the class ArrayLinearList by adding the method half().
The invocation x.half() eliminates every other element of x.
So if x.size is initially 7 and x.element[] = [2, 13, 4, 5, 17, 8, 29], then following the execution of x.half(), x.size is 4 and x.element[] = [2, 4, 17, 29].
If x.size is initially 4 and x.element[] = [2, 13, 4, 5], then following the execution of x.half(), x.size is 2 and x.element[] = [2, 4].
If x is initially empty, then is is empty following the execution of x.half().
(a) Write code for the member method half().
You should not use any of the other methods of ArrayLinearList.
The complexity of your code should be O(size).
(b) Show that the complexity of your code is, in fact, O(size).
http://www.cise.ufl.edu/~sahni/dsaaj/public/exer/c5/e21.htm
complexity 관련 참고
No 3.
(a) Extend the class Chain to include a method leftShift(i) that shifts the list elements left by i positions.
If L = [0, 1, 2, 3, 4], then L.leftShift(2) results in L = [2, 3, 4].
(b) What is the time complexity of your method?
No 4.
(a) Add a method reverse to the class Chain to reverse the order of the elements in x.
http://www.cise.ufl.edu/~sahni/dsaaj/public/exer/c6/e11.htm
No 5.
Let a and b be of type ExtendedChain. Assume that the elements of a and b are of type Comparable and are in sorted order (i.e., nondecreasing from left to right).
(a) Write a nonmember method merge to create a new sorted linear list c that contains all the elements in a and b.
Ref) Do Exercises This using doubly linked lists instead of chains.
http://www.cise.ufl.edu/~sahni/dsaaj/public/exer/c6/e15.htm
관련 참고 :
http://www.cise.ufl.edu/~sahni/dsaaj/
