CS 117 Assignment, Due 10/23/96

For this assignment, choose two of the following problems and write Pascal programs to solve them. In the comment at the top of each program, answer the question(s) posed in the problem 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.

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 /usr/dict/words? (No need to report that "a", "b", "c", etc. are palindromes.)
3. Among the words in /usr/dict/words, 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 /usr/dict/words, 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 phrase that can be shifted by some amount to yield another English phrase.

7. How many words in the dictionary file /usr/dict/words contain all five vowels? What are they?

If you want a more complete list of words no longer than eight letters, click here. Watch out, though. This file has almost 80000 words in it.