Homework assignments.

Assignment #1:

Write a function ssort(ind data[], int N) that sorts the array data of the size N using the selection sort algorithm. Download the template test_sort.cpp and copy this new function in the file instead of the generic sort() function. Also modify line #118 to call the new ssort function. Save the file as the ssort file.

Run the program several times with arguments 10000, 20000, 30000. What are the average run time for each argument? Please predict the run time for N=150,000. Submit these results as an Excel spreadsheet.

Assignment #2:

Write a function bsort(ind data[], int N) that sorts the array data of the size N using the bubble sort algorithm. Download the template test_sort.cpp and copy this new function in the file instead of the generic sort() function. Also modify line #118 to call the new bsort function. Save the file as the bsort file.

Run the program several times with arguments 10000, 20000, 30000. What are the average run time for each argument? Please predict the run time for N=150,000. Submit these results as an Excel spreadsheet.

Improve the code by introducing the counter of elements you have switched on each step. Compare the performance of the new algorithm with the performance of the original one for the same values of N.

Assignment #3:

Write a function shsort(ind data[], int N) that sorts the array data of the size N using the Shell sort algorithm. For this implementation you can use any step sequence, but please mention in comments which one you picked. Download the template test_sort.cpp and copy this new function in the file instead of the generic sort() function. Also modify line #118 to call the new shsort function. Save the file as the shsort file.

Please execute the program several times for N=10,000, N=20,000, N=40,000, and N=80,000. Compare the run time with the run time of previously discussed methods (selection, bubble, insertion sorts).

Assignment #4:

Write a function merge(int data[], int first, int middle, int last) that merges two subarrays contained in the array data. The parameters first and middle specify the indeces of the first and the last element of the first sub-array and the values middle+1 and last provide the first and the last indeces of the second sub-array. This function should merge the two sub-arrays and put the elements back into the array data in the right order.

Once you implemented the function merge() write the function msort() to sort an array using the merge sort algorithm.

Assignment #5:

Write a function partition(int data[], int first, int last) that partitions a subarray of the array data. The parameters first and last specify the first and the last indeces of the sub-array to be partitioned. This function should return an integer value that contains the index of the boundary element (the element that separates two parts of the sub-array, in such a way that all elements above the boundary are less or at most equal to the boundary element and all elements below the boundary are greater or may be equal to it).

When you implemented the function partition() write the function qsort() to sort an array using the quick sort algorithm.

Assignment #6:

Sieve of Eratosthenes: print all prime numbers less than 128,000,000. Well, you do not actually need to print them of course, but you need to design a program that does it the most efficient way you can think of. Try to use as little computations as possible.
Hint: create a bitmap of 128M bits and use each bit as an indication if the corresponding number prime or not.

Assignment #7:

Write a function that computes binomial coefficients using the Dynamic Programming technique. Please remember that you need to memorize all the intermediate results you had to compute on your way to the final result.

Assignment #8:

Complete the code for the Floyd's solution of the Shortest Path problem to keep track of the paths themselves (not only the distances). Modify the floyd.cpp to print not only the best prices from each city to each other city, but also the best paths. In other words, once computations completed, your program should print the best path from each city to each other city and the price of this paths.

Assignment #9:

Rewrite the recursion implementation of the knapsack problem using the dynamic technique. Please also keep track of the items in the winning set. That is, your program should print not only the value of the optimal set, but also the numbers of items included in the set.
Hint: you may want to use the Weight Indexed Array instead of normal two dimentional array to implement your storage area.
Hint 2: you may need to think about a separate two dimentional array in order to keep track of the items included in the knapsack.

Assignment #10:

Create a program that does the following:
  1. Randomly generates a private key (a super increasing sequence of 12 elements)
  2. Generates modulus and multiplier and creates a public key for this private key.
  3. Prompts the user for a string.
  4. Ciphers the string using the public key.
  5. Prints the cipher message.
  6. Decrypts the message.
Please note that you need to operate with 12-bits coding. That is, every three symbols from the input string are to be treated as two 12-bit sequences.