Programming Assignments for Scmp 218
Submit the link to your project by email before the deadline. Do Not modify after the deadline.
Assignment 10: Due 11:59 pm, Mon Nov 23
In this lab you are going to implement various sorting algorithms we discussed. You will also compare their performances.
Create an integer array of size 5,000. Fill in the array with random numbers. Apply each of the following sorting algorithms to sort the array
Bubble Sort
Selection Sort
Insertion Sort
Shell Sort
Merge Sort
Quick Sort with pivot as the middle element
Quick Sort with pivot as the median of the first, last and middle elements of the array
Quick Sort with pivot as a random element of the array (use the rand function to choose a random arrray index)
Before applying each algorithm, initilaize the array to the original state (randomly filled values) by saving a copy of the original array. After applying each sort function print out the first 20 elements of the array to make sure that it is really sorted (your sort algorithm is working correctly).
Also measure and report the (CPU) time each algorithm takes. (This is related to Programming Exercise 9 on pages 596 in the book). More info here about timing a piece of code. Save the output in a file (in addition to sending it to the screen). Make sure you have a good user interface (do not ask too many questions!) with output in a nice, easy-to-read format. At the end, summarize the running times of all algorithms on all array sizes in a nice tabular form.
Repeat this process for arrays of size i* 5,000 for i =1, 2, 4, 6.
Assignment 9: Due 11:59 pm, Mon Nov 16 (extended by 24 hours due to power outage and file problem)
I) Programming Project 4 on page 530. In part a), use the formula (a*m+i*b) % 100,000 for i from 0 to 999 and a = 47, m = 2743, and b = 5923 to fill the array with 1000 "random" numbers less than 100,000. Also add another part to part c: c-iii Use the plain sequential search to search for an item and also count the number of comparisons for the sequential search. You can use STL sort algorithm.
II) Programming Project 8 on page 531. To test your program, read the input from the following file in Google drive: FilesForLabs\Ch9_Ex8_data.txt
After reading info about each state, insert it to the hash table.Give the user the option of searching for a state (by name) or deleting a state from the list. Let the user repeat as long as they wish. Use a hash table of size 101 (which is the default size in the implementation given in the book) Note: The mixing of operator >> and getline function may cause problems with reading the data correctly. Use .ignore( ) function appropriately to avoid the problem.
Assignment 8, Due 11:59 pm, Mon Nov 9
I ) Implement (using queues) and test the Radix Sort Algorithm. The test function should have the following interface: Ask d (number of digits) from the user. Generate (and store in a container (e.g. array, vector)) a set of 50 random integers with at most d digits to be sorted. Print the array before it is sorted. Sort the array with the Radix Sort algorithm. Finally, print the sorted array. Format your output so that it looks neat and easy to read.
II) Do programming exercise 8 on page 496 (running customer-server simulation). You just need to complete the appropriate portions of the source code from the textbook.
Assignment 7, Due 11:59 pm, Mon Nov 2
Do the following programming exercises from Chapter 7 (pages 448-50)
Exercise 6: Let the user enter the number and program prints out the prime factors in descending order. Repeated factors must be printed. For example, if the input is 72, then the output should be 3^2*2^3
Exercise 9: Read the expressions from a file and write the results to the screen. Your input file should contain all the expressions given in the problem (as sample expressions to test on page 450) but you may add more. For simplicity, you may assume that the expressions only contain uppercase letters, white spaces, paranthesis, and the arithmetic operations +, -, * and / . (You do not have to have destructors)
Assignment 6, Due 11:59 pm, Wed Oct 21
Do programming exercise 18 at the end of chapter 6, i.e. complete the program given in the textbook to solve sudoku puzzles. Your program should take the input from a file. Let the user enter a file name. You can assume that the file is in the same folder as your program. Do not require the user to enter the entries from the keyboard. For output, send it both to the screen and to a file. Ask for the name of the output file from the user as well.
You can assume that the file you read the input from has the right format, i.e. 81 integer values between 0-9 with 0's indicating blank spaces. Test your program with a couple of sample input files (but it should be able to read from any input file specified).
Please note the following: 1) The description of the findEmptyGridSlot function given by the textbook (and source code) is misleading. A more accurate description is: This function finds the first empty square, stores its coordinates in its arguments, and returns true. If there is no empty square, then returns false. 2) The argument to open member function of a stream object must be of type C-string. In most compilers, a string object does not work but remember that the string class has a member function to convert a string object to a C-string.
Assignment 5, Due 11:59 pm, Mon Oct 12
Do the programming Exercises 2,3, 6 and 17 at the end of chapter 5. Use a single test program for all functions. Use the source code from the textbook with care. If you decide to terminate the program due to the violation of a condition (e.g, position entered is larger than the size of the list) make sure that you pause the program before exiting for the user to see the error message.
Note: As given, the source code from the textbook does not compile as is. One solution is when a derived class (such orderedLinkedList and unorderedLinkedList) inherits from the base class linkedListType<Type>, specify the type like so:
class orderedLinkedList: public linkedListType<int> as opposed to more general class orderedLinkedList: public linkedListType<Type>
There is another way to make the more general inheritance work. We will discuss this in class. If you find yet another way, let us know!
Assignment 4: Due 11:59 pm, Wed Sep 30
PartI: Do programming exercises 3, 4, 5, and 6 at the end of chapter 4. Write a single test program for all of these tasks but make sure you test each function/task separately and fully, and provide the user a good interface (that should include the option of repeating computations). Some hints:
template < class elemType>
void reverseVector(vector<elemType> &list)
{
typename vector<elemType> : : iterator Itr1,Itr2;
..... FILL IN THE REST
}
Part II: Write a program that uses the map template class from STL to compute a histogram of positive numbers entered by the user. The map's key should be the number that is entered, and the value should be a counter of the number of times the key has been entered so far. Use -1 as a sentinel value to signal the end of user input. For exampe, if the user inputs:
5,12,3,5,5,3,21
then the program should output the following (not necessarily in this order):
The number 3 occurs 2 times.
The number 5 occurs 3 times.
The number 12 occurs 1 times.
The number 21 occurs 1 times.
The program should let the user enter as many (multi)sets of numbers as they want.