Assignment 4
Objective: Design of dynamic data structures, recursion, traversals and insertions
Written Assignment:
16.2-4: Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car's gas tank, when full, holds enough gas to tranel n miles, and his map gives the distances between gas stations on his route. The professor wishes to make as few fas stops as possible along the way. Give an efficient method by which Professor Midas can determine at which gas stations he should stop, and prove that your strategy yields an optimal solution.
Question: The Monopoly Restaurant problem is the following: You are given a linear row of n restaurants of sizes S[1..n]. The objective is to specify merging operations so that all of the restaurants are merged into a single, very large restaurant. The merging rules are as follows:
at any step, only a pair of consecutive restaurants can be merged into a new restaurant that is the physical union of the two buildings
the size of the new restaurant is the sum of the sizes of the two restaurants being merged
the cost of a merge is equal to the size of the larger restaurant
the total cost of a sequence of n -1 mergings is the sum of the costs of the individual merging.
The problem is to give an efficient algorithm that computes the minimum total cost for creating one restaurant from the original n elements. Give an example of your algorithm in action!
Program Description: In this assignment, you will create a spell checker, implemented using a lg26n data structure similar to a binary search tree. The node still has a data section (in this case a single character), but instead of having only 2 child pointers, it will have 26, one for each letter of the alphabet (assuming only lower-case letters). Here's a simple C struct to demonstrate what I mean:
struct Node {
char data;
Node* children[26];
}Node;
The program really boils down to two major functions - add a string, and check for a string. Adding a string should not theoretically fail, and begins with the head node, whose data is ignored (it can be just about anything). The add string function will always take in a string and look at its first character. That character will map to a slot. If the slot is null, create a new node (malloc some space - whatever) for that slot, and pass it the rest of the string. If the slot was not null, pass the remaining string off to the node in that slot.
Searching for a string is similar; in this case, you will pass the string into the function, pull off the first character and map it to a slot. If that slot is ever null, you know that the string is not a word.
Words to the wise: make sure when creating a new Node that you initialize all the pointers to null. If not, you'll get some pointer problems!
Program Requirements: The program must read from a word file and insert each word into the tree. Once all the words are inserted, you must print out the total number of words, the total number of characters in all those words, and the total number of characters in the tree. Then, allow the user to:
1) Search for a word
2) Quit
If the user selects '1', the program will prompt the user for the word to validate. If the word is valid, then the program should print that the word is correctly spelled. Otherwise, it should print out that it is not a word.
If the user selects '2', obviously the program should quit.
Example: To run this assignment, you will need to save spell.exe as well as the word list in the same directory.
Extra Credit: 5 pts - in your code - comment what you believe the running time of inserting a string is, as well as searching for a string.
Program Turnin: You will show your code demo your program in class, explaining your answer.