Programming Assignments for Math 218
Bonus: Due 11:59 pm, Fri May 6
Implement Huffman Encoding. Use the frequencies given in the Table 8.8 (first handout about Huffman codes). After constructing the tree, print out encoding of each letter, and compute the average weighted code length. Store the letters and their frequencies in a list (or vector) so that your algorithm can be modified to construct Huffman trees for a different distribution of frequencies (e.g. for a different language). If you choose to do this project put this in a folder titled Bonus (if you did the previous bonus problem, put both of these under a folder titled Bonus but with separate folders for each)
Assignment 12 Due 11:59 pm, Wed May 4
Implement and test the heap sort algorithm.
Assignment 11: Due 11:59 pm, Monday, Apr 25
Do programming exercises 1-5 on page 682. You can use the source code from the book and write implementations for a binary search tree (or for a binary tree). Write a single test program to test all of these functions.
Assignment 10: Due 11:59 pm, Monday Apr 18
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
Selection Sort
Insertion Sort
Shell Sort
Bubble 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 printout 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). Save the output in a file (in addition to sending it to the screen)
Repeat this process for arrays of size i* 5,000 for i =1, 2, 4, 6
Assignment 9: Due 11:59 pm, Monday Apr 11 (extended by 24 hours)
I) Programming Project 4 on page 530. Use the formula (a*m+i*b) % 100,000 for i between 0 and 999 and a = 47, m = 2743, and b = 5923 to fill the array with "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.
II) Programming Project 8 on page 531. To test your program, read the input from the file
P:\Class\Math\Aydin\218\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 his/her action as long as s/he wishes. Use a hash table of size 101 (which is the default size in the implementation given in the book)
Assignment 8, Due 11:59 pm, Monday April 4
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 he textbook. Please keep in mind that our compiler is having difficulty with inheritence when classes involved are template classes. One way to overcome this difficulty is to eliminate inheritance.
Assignment 7, Due 11:59 pm, Monday March 28
Do the following projects from Chapter 7 (pages 448-50)
Project 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 36, then the output should be 3 3 2 2 (or you could print it as 3^2 2^2).
Project 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 468) but you may add more. For simplicity, you may assume that the expressions only contain uppercase letters, white spaces and the arithmetic operations +, -, * and / .
Assignment 6: Due 6 pm Friday March 4 (right before spring break)
Do programming exercise 18 at the end of chapter 6, i.e. complete the program to solve sudoku puzzles. Your program should be able to take the input from a file (let the user enter a file name), in addition to taking it from the keyboard.
You can assume that the 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)
Assignment 5, Due 11:59 pm, Wed Feb 23
Part I: Programming Projects 2,3 and 17 at the end of chapter 5. Use a single test program for all functions. You can use the source code of the textbook but with care
Part II: Project 6 at the end of chapter 5.
Note: As given, the source code from the textbook did not compile in our compiler. One solution is when the classes (such orderedLinkedList and unorderedLinkedList) inherit 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>
This is perhaps not the best solution (this was not a problem in the older version of the compiler). If you can find a better solution, let us know!
Assignment 4: Due 11:59 pm, Mon Feb 14
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
}
Bonus: Do exercise 10 (stock market) at the end of chapter 4. You have until the end of the spring break to do this one. If you decide to do this exercise make a folder titled "Bonus" and put it in there. You can use the file "StockData.txt" inside the folder "FilesForLabs" for initial testing, but it would be better to use a bigger/more realistic data.
Assignment 3: Due 11:59pm, Mon Feb 7 (extended until 11:59 pm, Wed Feb 9)
Part I: Do programming exercises 1-4 in chapter 3 (page 204-5). Write a single test program to test the functions you write. You may use the source code provided (with care).
Part II: Do programming exercise 8 (page 205). Also include the ~ operator to compute the derivative of a polynomial (see exercise 7). Write a single test program to test the functions you write. You may use the source code provided (with care)
Assignment 2: Due midnight, Monday Jan 31
Part I: is on inheritance and described here
Part II: Do programming project 4 on page 125 in 2 ways: First using inheritence as described in the book. Second using composition where the class circleType includes the class pointType. You may use the test program in the class folder FILESFORLABS\Lab2 (for the inheritance version), or you can write a test program similar to it.
Part III: In Programming Example of section 2, Complex numbers are implemented. Extend the definition of the class complexType given in the book by overloading the following operators:
- : for subtraction
/ : for division
~ : complex conjugation
! : absolute value
(See exercises 12-15 for more detailed description). Notice that - and / are binary operators whereas ~ and ! are unary operators.
Implement - and / as non-member functions but ~ and ! as member functions. Use the pointer this in the implementations of ~ .
You may use the files given in the book, but make sure you modify the test program so that you throughly test the new operations you define.
Do programming exercises 1 and 6 at the end of chapter 1. Writing a reasonable test program with good user interface is an important part of the assignment (and this is a default requirement in most future assignments as well). For exercise 1, you can assume that the input for Roman numeral is a legal string.
Also, write up solutions for problems 6-8 in the worksheet "Practice with Big-O Notation" and turn them in class on Tuesday, Jan 25.