# CS 3423 Assignment 4 solution

\$24.99

Original Work ?

## Description

5/5 - (1 vote)

Submit electronically on iLMS
What to submit: One zip file named -hw4.zip (replace with your
own student ID). It should contain four files:
● one PDF file named hw4.pdf for Section 1 and Section 3. Write your answers in
English. Check your spelling and grammar. Include your name and student ID.
● Section 2: Turn in
○ Section 2.1: quicksort.c, typescript1
○ Section 2.2: qsortTh.py, typescript2
○ Section 2.3: qsortTh.c, typescript3
● Section 3: (part of hw4.pdf)
1. [40 points] Problem Set
1. [20 points] Under what circumstances does a multithreaded solution using multiple
single-processor system?
2. [20 points] Which of the following components of program state are shared across
a. Register values
b. Heap memory
c. Global variables
d. Stack memory
2. [50 points] Programming Exercise
QuickSort is a popular algorithm for sorting. Even though its worst-case runtime complexity
is O(n
2
), its average complexity is O(n lg n), and in practice it is very fast because it is
in-place sorting (i.e., does not need a temporary buffer). Also, as a divide-and-conquer
algorithm, it does most of the work in the “divide” stage and no work in the “conquer” stage.
This makes it nice for parallelizing, because after forking, there is no dependency after
joining.
The following is a Python 2 implementation of Quicksort. For Python3, see the comments
def Partition(A, p, r):
x = A[r]
i = p – 1
for j in range(p, r):
def QuickSort(A, p, r):
if p < r: q = Partition(A, p, r) QuickSort(A, p, q-1) if (A[j] <= x): i = i + 1 A[i], A[j] = A[j], A[i] A[i+1], A[r] = A[r], A[i+1] return i + 1 QuickSort(A, q+1, r) if __name__ == '__main__': LEN = 10 L = range(LEN) # in Python3, do L = list(range(LEN)) instead import random random.shuffle(L) QuickSort(L, 0, len(L)-1) if L == range(LEN): # Python3 list(range(LEN)) instead of range(LEN) print("successfully sorted") else: print("sort failed: %s" % L) The test case just says to generate numbers 0..LEN-1, shuffle, and sort. If successful, it says so; otherwise, it dumps the list. 2.1 [10 points] Convert quicksort.py to C and call it quicksort.c. Turn in the source file and a typescript file named typescript1 showing how you build and run it. 1. Since you will need to measure the execution time of the code, you will need a large enough dataset. However, shuffling numbers can take a long time. Instead of shuffling numbers, have the numbers be pre-generated by the following script (genrandom.py) just once before you run your own code any number of times. import random LEN = 20000000 L = range(LEN) random.shuffle(L) fh = open("randomInt.txt", "w") # first write is the length fh.write(str(LEN)+'\n') for i in L: fh.write(str(i)+'\n') fh.close() Run this python program and it will create a text file named randomInt.txt. The first line is the number for LEN, followed by the shuffled numbers in the range 0..LEN-1. 2. You can use the following template (quicksort.c) to read in the data into array A, or feel free to write your own code: #include
#include
#include int *A; // array
int Partition(int A[], int p, int r) {
}
void* QuickSort(int A[], int p, int r) {
}
int main(int argc, char *argv[]) {
FILE* fh = fopen(“randomInt.txt”, “r”);
int len;
fscanf(fh, “%d”, &len);
A = calloc(len, sizeof(int));
#include
#include int *A; // array
int Partition(int p, int r) {
// your code from Sec. 2.1 except array param is now global A
}
void* QuickSort(void *arg) {