Description
ABOUT
This assignment contains several small problems. We will need the starter code and the output (part E) provided here:
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
|
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
