Programming Assignments for Math 218

Implement and test the heap sort algorithm.

Assignment 10:

Part I: Due 9:30 am, Tue, Apr 25

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\Sp06\218\FilesForLabs

Part II: Due 9:30 am, Tue May 2

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

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

Repeat this process for arrays of size i* 5,000 for i =1, 2, 4, 6

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.

II) Programming Project 8 on page 558. To test your program, read the input from the file

P:\Class\Math\Aydin\Sp06\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.

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

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.

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

Project 6: Let the user enter the expression to be checked. You may use a special symbol to signify the end of the expression (such as ; )

Project 7: Let the user enter the number and program prints out the prime factors in descending order.

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

Programming Projects 2 and 3 on page 363. Use a single test program for both. Also do projects 14 and 15, finishing the video store example. Use the source code and data files in: P:\Class\Math\Aydin\Sp06\218\SourceCode\Chapter 5 Source Code\videoStore (You just need to implement, add and test customer class)

Part II: Due 9:30 am, Tue Feb 28

Programming projects 6 and 7 on page 365. Implement them as separate projects and write a test program for each.

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

}

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.

Part II: Do programming exercises 10 and 11 (page 214). Write a single test program to test the functions you write. You may use the source code provided.

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.

Do programming exercises 8 and 9 at the end of chapter 1. You can use the files inside "FilesForLab1" in the class folder. 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 24.