代做CMSC 351 Fall 2023 Homework 7代写C/C++语言

CMSC 351 Fall 2023 Homework 7

Due Wednesday Apr 3, 2024 by 11:59pm on Gradescope.

Directions:

.  Homework must be done on printouts of these sheets and then scanned properly, or via latex, or by downloading, writing on the PDF, and uploading.

.  Do not use your own blank paper!

.  The reason for this is that gradescope will be following this template to locate the answers to the problems so if your answers are organized differently they will not be recognized.

.  Tagging is automatic, do not manually tag.

1.  Suppose we have a sorting algorithm called Cool Sort.  The decision tree for Cool Sort is shown below, partially filled out.  In each space fill in only the corresponding inequality of the form ?  [5 pts]

Scratch Work; Not Graded:

2.  Here is non-cumulative version of POS:

index		0	1	2	3
value		1	3	2	1

(a)  How many elements are in the original list that we are sorting?                                             [4 pts]

Number of elements:

(b)  At the end, what is the sorted list? You will not need all the blanks below so only fill in    [6 pts] as far as you need!

Index

0

1

2

3

4

5

6

7

8

9

Value

3.  Here is the cumulative version of POS:

index		0	1	2	3	4	5	6
value		0	2	2	3	5	5	7

Answer the following questions:                                           [2 pts]

(a) How many 0s are in the original, unsorted list?
(b) How many 3s are in the original, unsorted list?
(c) How many 5s are in the original, unsorted list?
(d) What is the largest element of the original, unsorted list?
(e) What is the smallest element of the original, unsorted list?

4. We are using counting sort to sort the following list of numbers where some entries are missing:

index		0	1	2	3	4	5	6
value		?	?	3	0	1	?	?

(a)  Here is the non-cumulative version of POS. Fill in the missing entries:                                  [3 pts]

index		0	1	2	3
value				3

(b)  Here is the cumulative version of POS. Fill in the missing entries:                                         [3 pts]

index		0	1	2	3
value			2

5.  Running counting sort, the cumulative version of POS looks like this:

index		0	1	2	3	4
value		0	3	x	4	7

What value(s) could x be?

List all the possible values for x

6.  How could you use one or more iterations of Counting Sort to accomplish each of the following?

Answer each with at most three sentences. This doesn’t require as much detail as pseudocode - just a high-level explanation suffices.

(a)  Given a list of n distinct complex numbers of the form a + bi with a,b ∈ Z+ , sort them by real part first with ties broken by complex part. [5 pts]

(b)  Given a list of n distinct complex numbers of the form a + bi with a,b ∈ Z+ , sort them by magnitude with ties broken by real part. [5 pts]

(c)  Given a list of n distinct real numbers between −n and 2n which contain at most one digit to the right of the decimal point, sort them. [5 pts]

7. It’s possible to prove by weak induction that Counting Sort is stable.  Let’s do this formally for a list of length n ≥ 1.

(a)  Base Case: Explain why Counting Sort is stable on a list of length n = 1.                             [2 pts]

(b) Inductive Step: The inductive step is a bit delicate.  The way Counting Sort works is that the cumulative version of POS is used as a reference to build ANEW. It is this process that we prove stability via induction on. [18 pts]

For the inductive hypothesis we assume that when POS is used as a referece to build ANEW for a list of length j, the result is stable.

We must then prove that when POS is used as a reference to build ANEW for a list of length j + 1, the result is stable.

Do so!

8. We proved that for any comparison-based sorting algorithm that for any n there is at least    [10 pts] one list which will require at least nlgn comparisons and hence will take at least Cnlg n time for some constant C to sort the list.

Explain why for any sorting algorithm (not just comparison-based ones) which works by moving elements around that for any n there is at least one list which will take at least C(n − 1) time for some constant C to sort the list.

Note: This does not need to be a formal proof but should be a concise explanation.

9.  Suppose Radix Sort is used to sort the following list of strings.  Show the state of the list after each iteration of the underlying sort. [8 pts]

Start

CAT

BAT

BAN

ABE

CBA

After Iteration 1
After Iteration 2
After Iteration 3

10.  Suppose  b  =  2  is the fixed base.   Suppose  that  we have  a list of length n which contains integers between 0 and n2  inclusive.  Explain why Radix Sort with underlying Counting Sort time complexity will be Θ(nlgn). [10 pts]