CS 117, Spring 1998

Assignment 6: Hodgepodge

Due 5/8/98

For this assignment, choose two of the following problems and write C++ programs to solve them. In the comment at the top of your program, answer the question(s) posed in the problems you solved.

The focus here is on solving the problems. I want to see the computer programs you use to solve the problems, and those programs should be written with attention to style and organization, as always. But I really want answers to the questions, and explanations of how you obtained those answers.

Several of the problems below refer to the dictionary file /Accounts/courses/cs117-1/words.txt. You can get a copy of this file into your account by dragging its icon to your house icon, or via the UNIX command "cp /Accounts/courses/cs117-1/words.txt .". This file contains 79,339 words, one per line. It's big, so you should try not to leave copies of it lying all around your account. In fact, you can avoid copying it to your account at all, and just access it from your program like this: "myprogram < /Accounts/courses/cs117-1/words.txt".

1. A prime number is a positive integer greater than 1 (1 is not prime) whose only factors are 1 and the number itself. What percentage of the first 100 integers are prime? The first 1000? 10000? 100000?
2. A palindrome is a word or phrase that reads the same backwards as forwards (not counting capitalization and punctuation). For example, "Hannah" and "Sit on a potato pan, Otis" are palindromes. What palindromic words are contained in the dictionary file /Accounts/courses/cs117-1/words.txt?
3. Among the words in /Accounts/courses/cs117-1/words.txt, what word contains the most vowels? The most consonants? The highest vowel-to-consonant ratio, not counting the words with no consonants? (By vowel-to-consonant ratio, I mean the number of vowels divided by the number of consonants. For example, "lemur" has a VTCR of 2/3.)
4. The sentence "The quick brown fox jumps over a lazy dog" is famous as one of the shortest meaningful English sentences to contain all 26 letters. It fails the ultimate test of such sentences, though, by containing repeated letters (four o's, for example).

   In this exercise, we will score words by the following scheme: 1 point for each distinct letter, and -1 point for each repetition of a previously used letter. So, for example, "The quick brown fox jumps over a lazy dog" gains 26 points for having all 26 letters, but loses 1 point for the extra u, 3 points for the extra o's, 1 point for the extra e, 1 point for the extra r, and 1 point for the extra a, for a total score of 19. Similarly, the word "platypus" scores 6 points.

   Among all the words in the dictionary file /Accounts/courses/cs117-1/words.txt, what word has the highest score?

5. Take any positive integer N, and generate a second integer like this: if N is even, the new number is N/2, and if N is odd, the new number is 3N+1. You can generate a sequence of numbers in this way. For example: 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1,....

   Most mathematicians believe that all starting N's eventually wind up at 4, 2, 1, 4, 2, 1,..., but nobody has proven it.

   Find the N between 1 and 100 that takes the longest number of steps to get to 1.

6. A "shift substitution code" is a simple way of encoding messages by shifting the letters down the alphabet some fixed distance. For example, if you shift "no quiz today" by 1, you get "op rvja upebz," by 2, you get "pq swkb vqfca," and by 25, you get "mn pthy snczx." If you write a program to take any message and show it shifted by 0, 1, 2,..., 25, you will have an encoding and decoding machine for this kind of code.

   Find an English word at least four letters long that can be shifted by some amount to yield another English word. If you're really ambitious, try finding a whole phrase that can be shifted to another phrase.

7. How many words in the dictionary file /Accounts/courses/cs117-1/words.txt contain all five vowels? What are they?