cs2223 Problem 2

[WPI] [cs2223] [cs2223 text] [News] [Syllabus] [Problems]

cs2223, D97/98 Problem 2

Go to Solution

Problem Statement

Write a program which implements a heap of integers. Create functions for putting the data into the heap form, for adding a number, and for finding and removing a number, if it is present. For each function, calculate the number of swaps between nodes for the best and worst cases. Submit a listing of your program, sample output, and a comparision between the measured and calculated numbers (best, worst) of swaps for all three algorithms.
Write a program which uses a greedy algorithm to calculate the fewest number of "coins" necessary to pay an amount of money (your program will ask the operator to enter the amount of money to pay). Design your program so that it reads a file containing data about coin denominations (to allow switching between money systems) and don't forget to consider the possibility that sometimes greedy algorithms don't allow you to pay out every possible amount. Submit a listing of your program and sample output. Be sure your program prints out the list of coin amounts.
Write a program which performs n-digit integer multipliation using divide and conquer techniques. Submit a listing of your program, sample output, and a comparision between the number of single-digit multiplications your program peformed and the number predicted in the calculation in the text.
Write a program which performs n-digit exponentiation (int to int power) using divide and conquer techniques for both exponentiation and multiplications (the program from the last question may be useful). Submit a listing of your program, sample output, and a comparision between the number of single-digit multiplications your program performed and the number predicted in the calculation in the text.