ASSIGNMENT 03 Solution

ABOUT

This assignment contains several small problems. We will need the starter code and the output (part E) provided here:




URL: http://csc220.ducta.net/Assignments/Assignment-03-Code.zip









PART A – Introduction to Sorting, 9 points




Please use this array of integers for the A.1, A.2, and A.3 problems: 9 5 9 8 3 3 6 2 9 7 6 1




Use pen & paper to show our work and answers. We can scan/snapshot our work and include the images in our report.



Use code to demonstrate our approaches and solutions. Submit code and include screenshots of output in our report.



Each of these problems is worth 3 points.



1.
Show the contents of the array each time a selection sort
changes it while sorting the array into
2.
Show the contents of the array each time an insertion sort
changes it while sorting the array into
3.
Show the contents of the array each time a Shell sort
changes it while sorting the array into



PART B –Sorting, 12 points




ascending order.




ascending order.




ascending order.



--- 2 points --- Suppose we want to find the largest entry in an unsorted array of n entries. Algorithm A searches the entire array sequentially and records the largest entry seen so far. Algorithm B sorts the array into descending order and then reports the first entry as the largest. Compare the time efficiency of the two



approaches. Coding is not required but highly recommended.
The array
is initially
1
2
3
4
5












3
4
5
1
2
2. --- 10 points --- Consider an n by n array of integer values. Write an algorithm
5
2
3
4
1
2
3
1
4
5
to sort the rows of the array by their first value.
4
2
3
1
5
The starter code for this problem is provided in the Assignment-03-Code.zip
The array
after sorting is
1
2
3
4
5
archive. Our output must be identical to the output to the right.
2
3
1
4
5












3
4
5
1
2






4
2
3
1
5
PART C – Queues, Deques, and Priority Queues, 9 points
5
2
3
4
1



--- 3 points --- After each of the following statements executes, what are the contents of the queue? Please explain.



QueueInterface<String myQueue = new LinkedQueue<(); myQueue.enqueue("Jane"); myQueue.enqueue("Jess"); myQueue.enqueue("Jon"); myQueue.enqueue(myQueue.dequeue()); myQueue.enqueue(myQueue.getFront()); myQueue.enqueue("Jim");




String name = myQueue.dequeue(); myQueue.enqueue(myQueue.getFront());






Updated: 4/6/2020 10:12 PM


CSC 220.02+.03
ASSIGNMENT 03
SPRING 2020 TA










2. --- 3 points --- After each of the following statements
3. --- 3 points --- After each of the following statements










executes, what are the contents of the deque? Please explain. executes, what are the contents of the priority queue? Please






explain.




DequeInterface<String myDeque = new


PriorityQueueInterface<String myPriorityQueue =
LinkedDeque<();


new LinkedPriorityQueue<();




myDeque.addToFront("Jim");


myPriorityQueue.add("Jim");




myDeque.addToFront("Jess");


myPriorityQueue.add("Josh");




myDeque.addToBack("Jen");


myPriorityQueue.add("Jon");




myDeque.addToBack("Josh");


myPriorityQueue.add("Jane");




String name = myDeque.removeFront();


String name = myPriorityQueue.remove();
myDeque.addToBack(name);


myPriorityQueue.add(name);




myDeque.addToBack(myDeque.getFront());


myPriorityQueue.add(myPriorityQueue.peek());
myDeque.addToFront(myDeque.removeBack());
myPriorityQueue.add("Jose");




myDeque.addToFront(myDeque.getBack());


myPriorityQueue.remove();










It is OK to assume that the alphabetically earliest string has the

highest priority.







PART D – Queue and Deque, Circular Doubly Linked Chain, 15 points




Use a circular doubly linked chain to implement the ADT deque.




In a doubly linked chain, the first and last nodes each
Empty deque: true
[FRONT] Jerry << Tom << Minnie << Mickey << ...
contain one null reference, since the first node has no previous
[BACK] Sylvester Goofy Donald ...
node and the last node has no node after it. In a circular doubly


linked chain, the first node references the last node, and the
Empty deque: true
last node references the first. Only one external reference is
Sayōnara
necessary—a reference to the first node—since we can quickly
- removeFront found deque empty
get to the last node from the first node.
- removeBack found deque empty









The code for this problem is provided in the Assignment-03-Code.zip archive. Our output must be identical to the output to the right.







PART E – Priority Queue, 15 points




The San Francisco State University’s One Stop Student Services Center asks us to recommend solutions for their service lines.




The starter code for this problem is provided in the Assignment-03-Code.zip archive.



Our output must be identical to the complete output provided in the ZIP archive: The_Complete_Sample_Run.pdf



The below is a portion of the output for preview purposes. It is NOT the complete output.



Please analyze the complete output thoroughly before programming a solution.



-------------------------------------------------------------




SFSU ONE STOP STUDENT SERVICES CENTER

-------------------------------------------------------------




Priority: default

Mickey
Mouse
1002
3.70
1
17
Minnie
Mouse
1001
3.90
10
15
Milo
Dog
1004
3.70
7
17
Goofy
Dog
1007
2.30
17
1
Daisy
Duck
1003
1.70
1
17
Pluto
Dog
1005
3.70
7
17
Donald
Duck
1006
3.10
5
2






Happy coding and Thank you!







Updated: 4/6/2020 10:12 PM