| Contents [0/3] |
| Homework (Order of Growth, Sorting Problems) [1/3] |
| HW Answers [2/3] |
| Quiz Answers [3/3] |
(Click here for one slide per page)
| Homework (Order of Growth, Sorting Problems) [1/3] |
Re-read the section on Binary Search in Algorithms, pages 378-386.
Review Section 1.4 (Analysis of Algorithms) in the Algorithms textbook.
Read pages 244 - 257 of Section 2.1 (Elementary Comparison-Based Sorting) in the Algorithms textbook.
Also read the discussion of stability in section 2.5 (page 341).
Do Quiz 4 on D2L. Note: There is no Quiz 3, because I number the quizzes based on the week they were assigned.
Section 810 Async: Print out and do the In Class Coding Activity, which is a mini-practice exam.
In-Class Coding Activity Pop Quiz (PDF file)
You should be able to do this activity in 10 minutes or less.
I can't control whether you do it under exam conditions, but you should try to do it without reference to any external resources, just as you will have to take the Midterm.
Submit it in the appropriate folder labeled In-Class Coding Activity on D2L. Submission of this activity counts toward your participation grade for Week 4.
If you are in Section 801, and were not present at the beginning of class, you should do this activity as described above and submit it as well.
Do the homework assigned on D2L (See Submissions).
There are two parts to this homework. Do the hw4a, the programming homework, before the hw4b written homework, as the programming part should help you better understand the material in hw4b.
hw4a: Order of Growth Experiments
file:orderofgrowth.zip (Zip file)
Once you have downloaded the file, unzip it. The orderofgrowth folder inside of it should be added below the ds1.student package in IntelliJ IDEA.
Make sure you can compile all of the code in IntelliJ IDEA (no red squiggly marks).
There are a lot of files in this zip. Two of them, CountingLoops.java and CountingLoopsRecursion.java
are demos from class, which may be useful to you, but they are not necessary for this part of the homework.
There are a few other support files, which you can look at if you want to, but don't change any file not listed below. Within the files listed below, make sure you don't change anything I specifically instructed you not to in the comments.
The Java classes with instructions in the source files are as follows. Go through them in this order. Each of these have main programs. Look for the TODO comments (as usual).
Do not use recursion for any of the coding questions. Use loops.
ds1.student.orderofgrowth.max.SlowerMax
This is an example experiment with a slow implementation of finding the max. Look for TODOs and instructions to provide answers to the questions included in the file.
ds1.student.orderofgrowth.max.FasterMax
This is an example experiment with a more efficient implementation of finding the max. Look for TODOs and instructions to provide answers to the questions included in the file.
ds1.student.orderofgrowth.search.LinearSearch
This is an example experiment with an inefficient search for a value in an array. Look for TODOs and instructions to provide answers to the questions included in the file.
ds1.student.orderofgrowth.search.BinarySearch
For this Java class, you will need to actually implement binary search, write unit tests, and run some experiments. Look for TODOs and instructions to provide answers to the questions included in the file.
ds1.student.orderofgrowth.sort.DoubleArraySelectionSort
For this Java class, you will need to actually implement selection sort, write unit tests, and run some experiments. Look for TODOs and instructions to provide answers to the questions included in the file.
ds1.student.orderofgrowth.sort.DoubleArrayInsertionSort
For this class, you will need to actually implement insertion sort, write unit tests, and run some experiments. Look for TODOs and instructions to provide answers to the questions included in the file.
Hand in all six of the above listed files in the hw4a folder.
Your submissions should contain your implementations of the requested algorithms, any unit tests requested, and answers to the questions about interpreting the results in the designated comment blocks.
Important Study Note
My reason for asking you to code these algorithms yourself is because I want you to get the practice thinking through a problem and trying it out yourself. You don't even need to code the algorithms exactly as presented in the textbook. Just remember that you need to know these algorithms cold so that if I ask you to implement them on an exam, you know how to do it without consulting any external resources.
hw4b: Sorting Problems
Do these problems from Algorithms on paper, and hand them in (Word doc or PDF). The problems begin on page 264 of the Algorithms text.
2.1.1
2.1.2
2.1.4
2.1.6
2.1.7
2.1.8
2.1.15
| HW Answers [2/3] |
2.1.1
Show, in the style of the example trace with Algorithm 2.1,
how selection sort sorts the array
E A S Y Q U E S T I O N
^ *
A E S Y Q U E S T I O N
^
A E S Y Q U E S T I O N
^ *
A E E Y Q U S S T I O N
^ *
A E E I Q U S S T Y O N
^ *
A E E I N U S S T Y O Q
^ *
A E E I N O S S T Y U Q
^ *
A E E I N O Q S T Y U S
^
A E E I N O Q S T Y U S
^ *
A E E I N O Q S S Y U T
^ *
A E E I N O Q S S T U Y
^
A E E I N O Q S S T U Y
^
A E E I N O Q S S T U Y
^
2.1.2*
What is the maximum number of exchanges involving any particular item
during selection sort? What is the average number of exchanges
involving an item?
max # of exchanges for selection sort for a particular element: N
An example:
501234
051234
015234
012534
012354
012345
total # of exchanges <= N
total # of elements = N
average <= 1
2.1.4
Show, in the style of the example trace with Algorithm 2.1,
how insertion sort sorts the array
E A S Y Q U E S T I O N
^
E A S Y Q U E S T I O N
* ^
A E S Y Q U E S T I O N
^
A E S Y Q U E S T I O N
^
A E S Y Q U E S T I O N
* ^
A E S Q Y U E S T I O N
* ^
A E Q S Y U E S T I O N
* ^
A E Q S U Y E S T I O N
* ^
A E Q S U E Y S T I O N
* ^
A E Q S E U Y S T I O N
* ^
A E Q E S U Y S T I O N
* ^
A E E Q S U Y S T I O N
* ^
A E E Q S U S Y T I O N
* ^
A E E Q S S U Y T I O N
* ^
A E E Q S S U T Y I O N
* ^
A E E Q S S T U Y I O N
* ^
A E E Q S S T U I Y O N
* ^
A E E Q S S T I U Y O N
* ^
A E E Q S S I T U Y O N
* ^
A E E Q S I S T U Y O N
* ^
A E E Q I S S T U Y O N
* ^
A E E I Q S S T U Y O N
* ^
A E E I Q S S T U O Y N
* ^
A E E I Q S S T O U Y N
* ^
A E E I Q S S O T U Y N
* ^
A E E I Q S O S T U Y N
* ^
A E E I Q O S S T U Y N
* ^
A E E I O Q S S T U Y N
* ^
A E E I O Q S S T U N Y
* ^
A E E I O Q S S T N U Y
* ^
A E E I O Q S S N T U Y
* ^
A E E I O Q S N S T U Y
* ^
A E E I O Q N S S T U Y
* ^
A E E I O N Q S S T U Y
* ^
A E E I N O Q S S T U Y
^
2.1.6*
Which method runs faster for an array with all keys identical,
selection sort or insertion sort?
faster with identical keys:
insertion=N compares and 0 swaps
selection=N^2/2 compares and 0 swaps
Three important facts for this problem:
1. if all keys are identical then it's sorted
2. for a sorted array, insert sort is linear (it just checks every
element to the adjacent one)
3. for any array, selection sort does a quadratic number of comparisons.
Since the comparison pattern of selection sort is fixed, it still has
worst case performance.
2.1.7*
Which method runs faster for an array in reverse order,
selection sort or insertion sort?
faster for reversed array:
insertion=N^2/2 compares and N^2/2 swaps
selection=N^2/2 compares and N swaps
Experimentally
insertion with reversed array:
4000 15999998 4.0 [0.049 0.721]
8000 63999998 4.0 [0.173 3.531]
16000 255999998 4.0 [0.761 4.399]
32000 1023999998 4.0 [2.911 3.825]
64000 4095999998 4.0 [12.374 4.251]
selection with reversed array:
4000 8005999 4.0 [0.026 0.226]
8000 32011999 4.0 [0.115 4.423]
16000 128023999 4.0 [0.489 4.252]
32000 512047999 4.0 [1.964 4.016]
64000 2048095999 4.0 [8.282 4.217]
2.1.8*
Suppose that we use insertion sort on a randomly ordered array where items
have only one of three values. Is the running time linear, quadratic, or
something in between?
should be quadratic. Number of values does not matter, it's their distribution.
three values:
4000 5203612 3.8 [0.016 0.364]
8000 21434206 4.1 [0.053 3.313]
16000 84502719 3.9 [0.210 3.962]
32000 342564934 4.1 [0.886 4.219]
64000 1360115026 4.0 [3.488 3.937]
128000 5419985602 4.0 [12.636 3.623]
two values:
4000 4039762 4.1 [0.012 0.279]
8000 16011924 4.0 [0.041 3.417]
16000 64837772 4.0 [0.155 3.780]
32000 254433286 3.9 [0.599 3.865]
64000 1022514350 4.0 [2.537 4.235]
128000 4097713293 4.0 [9.868 3.890]
one value (therefore presorted):
4000 7998 2.0 [0.002 Infinity]
8000 15998 2.0 [0.001 0.500]
16000 31998 2.0 [0.001 1.000]
32000 63998 2.0 [0.000 0.000]
64000 127998 2.0 [0.001 Infinity]
128000 255998 2.0 [0.000 0.000]
2.1.15*
Expensive exchange. A clerk at a shipping company is charged with the task
of rearranging a number of large crates in order of the time they are to be
shipped out. Thus, the cost of compares is very low (just look at the labels)
relative to the cost of ex- changes (move the crates). The warehouse is
nearly full --- there is extra space sufficient to hold any one of the crates,
but not two. What sorting method should the clerk use?
selection sort # exchanges <= N.
| Quiz Answers [3/3] |
Selection sort
4 1 9 5 6 0 3 8 7 2
^ *
0 1 9 5 6 4 3 8 7 2
^
0 1 9 5 6 4 3 8 7 2
^ *
0 1 2 5 6 4 3 8 7 9
^ *
0 1 2 3 6 4 5 8 7 9
^ *
0 1 2 3 4 6 5 8 7 9
^...
1 2 3 4 5 6 7 8 9 0
^ *
0 2 3 4 5 6 7 8 9 1
^ *
0 1 3 4 5 6 7 8 9 2
^ *
0 1 2 4 5 6 7 8 9 3
^ *
0 1 2 3 5 6 7 8 9 4
^...
Insertion sort
4 1 9 5 6 0 3 8 7 2
^
4 1 9 5 6 0 3 8 7 2
* ^
1 4 9 5 6 0 3 8 7 2
^
1 4 9 5 6 0 3 8 7 2
* ^
1 4 5 9 6 0 3 8 7 2
* ^
1 4 5 6 9 0 3 8 7 2
* ^
1 4 5 6 0 9 3 8 7 2
* ^
1 4 5 0 6 9 3 8 7 2
* ^
1 4 0 5 6 9 3 8 7 2
* ^
1 0 4 5 6 9 3 8 7 2
* ^
0 1 4 5 6 9 3 8 7 2
^...
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
^
1 2 3 4 5 6 7 8 9 0
* ^
1 2 3 4 5 6 7 8 0 9
* ^
1 2 3 4 5 6 7 0 8 9
* ^
1 2 3 4 5 6 0 7 8 9
* ^
1 2 3 4 5 0 6 7 8 9
* ^
...