PLEASE NOTE:
Provide only the requested information and nothing more. Unreadable, unintelligible and irrelevant answers will not be considered.
You can collaborate with your TA/INSTRUCTOR ONLY and discuss the solutions of the problems.
However you have to write down the solutions on your own.
Plagiarism will not be tolerated.
Submit your answers as a single pdf le named as username-yourname-surname-hw2.pdf
◦ Example submission le name: furkanreha-furkanreha-tutas-hw2.pdf
Late submission is allowed for only 10 hours. Each hour late submission costs 10% of your grade. For example, if you submit 5 minutes late, your grade will be multiplied by 0.9, if you submit 61 minutes late, your grade will be multiplied by 0.8.
1. Consider the Radix sort that is used to sort numbers. (55pt)
(a) Explain how would you modify the Radix sort in order to sort the list of words in alpha-betical order. (20pt)
(b) Sort the following list of words using the modi ed algorithm and give the form of the array after every iteration of the main loop of the radix sort. (20pt)
[HUSNU; BERK; FURKAN; REHA]
(c) Find the time complexity of the modi ed algorithm. (15pt)
1
Homework 1
CS301
2. Consider the following algorithm, which is exactly the same algorithm we considered in the class for the selection problem with one di erence; instead of dividing the input into groups of 5 elements, we divide the input into groups of k elements, where k is a parameter of the algorithm. (45pt)
• float WCL_Select (A, first, last, i, k) {
• if (first == last) { // i=1 in this case
3return A[first];
• }
5
• Divide n elements into groups of k elements; //g1 g2 ... gn=k
7Find the median mi each group gi;
8Use WCL_Select to find the median mm of the medians of all the groups;
9mid = NewPartition(A, first, last, mm); // it partitions around mm
10 mid_and_less = mid - first + 1
11
12
13
14
15
16
17
18
19
20
if (mid_and_less == i) { // we may be lucky return A[mid];
}
if (i < mid_and_less) { // it is in the left subarray return (WCL_Select(A, first, mid-1, i, k));
}
return (WCL_Select(A, mid+1, last, i-mid_and_less, k)); }
(a) Derive the recurrence for the running time of the algorithm given above. Note that the recurrence will be parametric in k as well. After you derive this recurrence, substituting k = 5 in the recurrence should give the recurrence we had in the class. (20pt)
(b) Write the concrete recursion for k = 7. Show that running time for this recursion is still linear. (10pt)
(c) Find the largest odd integer value for k, for which the running time of this algorithm is super-linear (i.e. grows faster than linear). Write the concrete recursion for the value of k you suggest and show that running time is super-linear in this case. (15pt)
2
