Lab Assignments for Math 218

Programming Assignments for Math 218

Assignment 11 Due 11:59 pm, Fri May 2

Implement and test the heap sort algorithm.

Assignment 10:

Part I: Due 9:30 am, Wed, Apr 23

Do programming exercises 1, 2 and 4 on page 716 i.e. implement the functions nodeCount, leavesCount and singleParent for a binary tree. Write a single test program to test all 3 functions. Your test function could be something like TestLab10.cpp located in

P:\Class\Math\Aydin\218\FilesForLabs

Part II (Bonus): Due 9:30 am, Tue Apr 29

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).

Assignment 9: Due 11:50 pm, Fri 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

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. Read Programming Exercise 7 on pages 628-9 in the book for timing a program segment. 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 8: Due 11:59 pm, Fri Apr 11

I) Programming Project 4 on page 557. 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 558. 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 7: Due 9:30 am, Thu April 3

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 6 on page 522 (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 6, Due 9:30 am, Thu March 27

Do the following projects from Chapter 7 (pages 466-67)

Project 7: 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 10: 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 5, Due 5 pm, Fri Feb 29

Part I: Programming Projects 2 and 3 on page 363. Use a single test program for both.

Part II (Bonus): Projects 14 and 15, finishing the video store example. Use the source code and data files in: P:\Class\Math\Aydin\\218\SourceCode\Chapter 5 Source Code\videoStore (You just need to implement, add and test customer class)

Part III: Project 6

Assignment 4: Due 9:30 am, Wed Feb 13

Do programming exercises 3, 4 and 5 on page 270. You may write a single test program for all 3 tasks but make sure you test each function/task separately and fully. Some hints:

The algorithm library contains a generic swap function. You may want to use it for # 4. (To use it insert #include <algorithm>)
For #4, If you are goingto use iterators, then the beginning of the reverseVector function should be like this

template < class elemType>

void reverseVector(vector<elemType> &list)

{

typename vector<elemType> : : iterator Itr1,Itr2;

..... FILL IN THE REST

}

Assignment 3: Due 9:30 am, Tue Feb 5

Part I: Do programming exercises 6-8 in chapter 3 (page 214). 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 12 (page 215). Also include the ~ operator to compute the derivative of a polynomial (see exercise 11). Write a single test program to test the functions you write. You may use the source code provided (with care)

Assignment 2: Due 9:30 am, Tue Jan 29

Part I: Do programming project 4 on page 127 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 II: 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 problems 12-14 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.

Assignment1: Due 9:30 am, Tue Jan 22

(24 hour extension, due 9:30 am, Wed Jan 23)

Do programming exercises 2 and 8 at the end of chapter 1. You can use the files inside "FilesForLab1" in the class folder for exercise 8. It contains a test program with main to test your classes and also 2 input files to read some data from (about books and bookstore members). Save those files to your own directory and work from there. Note that if you use the test file without modification, the names of your classes and their members must be exactly the same as what is the test file. You should separate the definition of your classes from the implemetation (by writing separate header and implementation files).

Also, write up solutions for problems 6-8 in the worksheet "Practice with Big-O Notation" and turn them in class on Tuesday, Jan 22.