$29
Problem Set 1b Solution
Advice 1 : For every problem in this class, you must justify your answer: show how you arrived at it and why it is correct. If there are assumptions you need to make along the way, state those clearly.
Advice 2 : Verbal reasoning is typically insu cient for full credit. Instead, write a logical argument, in the style of a mathematical proof.
Instructions for submitting your solution:
The solutions should be typed and we cannot accept hand-written solutions. Here’s a short intro to Latex.
You should submit your work through Gradescope only.
If you don’t have an account on it, sign up for one using your CU email. You should have gotten an email to sign up. If your name based CU email doesn’t work, try the iden-tikey@colorado.edu version.
Gradescope will only accept .pdf les (except for code les that should be submitted sep-arately on Gradescope if a problem set has them) and try to t your work in the box provided.
You cannot submit a pdf which has less pages than what we provided you as Gradescope won’t allow it.
(34 pts total) Let A = ha1; a2; : : : ; ani be an array of numbers. Let’s de ne a ’ ip’ as a
pair of distinct indices i; j 2 f1; 2; : : : ; ng such that i < j but ai aj . That is, ai and aj are out of order.
For example - In the array A = [1, 3, 5, 2, 4, 6], (3, 2), (5, 2) and (5, 4) are the only ips i.e. the total number of ips is 3. (Note that in this example the indices are the same as the actual values)
(8 pts) Write a Python code for an algorithm, which takes as input a positive integer n, randomly shu es an array of size n with elements [1; : : : ; n] and counts the total number of ips in the shu ed array.
Also, run your code on a bunch of n values from [2; 22; 23; ::::220] and present your result in a table with one column as the value of n and another as the number of ips. Alternatively, you can present your table in form of a labeled plot with the
1
Name:
ID:
CSCI 3104, Algorithms
Profs. Hoenigman & Agrawal
Problem Set 1b (44 points)
, CU-Boulder
2 columns forming the 2 axes.
Note: The .py le should run for you to get points and name the le as Lastname-Firstname-MMDD-PSXi.pdf. You need to submit the code via Canvas but the table or plot should be on the main .pdf.
Erase this before you answer - This space is NOT for the code but only for the table or plot.
2
Name:
ID:
CSCI 3104, Algorithms
Profs. Hoenigman & Agrawal
Problem Set 1b (44 points)
, CU-Boulder
(4 pts) At most, how many ips can A contain in terms of the array size n? Hint: The code you wrote in (a) can help you nd this. Explain your answer with a short statement.
3
Name:
ID:
CSCI 3104, Algorithms
Profs. Hoenigman & Agrawal
Problem Set 1b (44 points)
, CU-Boulder
(10 pts) We say that A is sorted if A has no ips. Design a sorting algorithm that, on each pass through A, examines each pair of consecutive elements. If a consecutive pair forms a ip, the algorithm swaps the elements (to x the out of order pair). So, if your array A was [4,2,7,3,6,9,10], your rst pass should swap 4 and 2, then compare (but not swap) 4 and 7, then swap 7 and 3, then swap 7 and 6, etc. Formulate pseudo-code for this algorithm, using nested for loops.
Hint: After the rst pass of the outer loop think about where the largest element would be. The second pass can then safely ignore the largest element because it’s already in it’s desired location. You should keep repeating the process for all elements not in their desired spot.
4
Name:
ID:
CSCI 3104, Algorithms
Profs. Hoenigman & Agrawal
Problem Set 1b (44 points)
, CU-Boulder
5
Name:
ID:
CSCI 3104, Algorithms
Profs. Hoenigman & Agrawal
Problem Set 1b (44 points)
, CU-Boulder
(4 pts) Your algorithm has an inner loop and an outer loop. Provide the ’useful’ loop invariant (LI) for the inner loop.You don’t need to show the complete LI proof.
6
Name:
ID:
CSCI 3104, Algorithms
Profs. Hoenigman & Agrawal
Problem Set 1b (44 points)
, CU-Boulder
(8 pts) Assume that the inner loop works correctly. Using a loop-invariant proof for the outer loop, formally prove that your pseudo-code correctly sorts the given array. Be sure that your loop invariant and proof cover the initialization, main-tenance, and termination conditions.
7
Name:
ID:
CSCI 3104, Algorithms
Profs. Hoenigman & Agrawal
Problem Set 1b (44 points)
, CU-Boulder
(6 pt) If r is a real number not equal to 1, then for every n 0,
n
(1 rn+1)
Xi
ri =
:
=0
(1
r)
Rewrite the inductive hypothesis from Q3 on PS1a and provide the inductive step to complete the proof by induction. You can refer to Q3 on PS1a to recollect the rst 2 steps.
8
Name:
ID:
CSCI 3104, Algorithms
Profs. Hoenigman & Agrawal
Problem Set 1b (44 points)
, CU-Boulder
(4 pt) Refer to Q2b on PS1a and nish the LI based proof with all the steps.
9
