CS13002 PDS Lab, Spring 2003, Section 1/A

Assignment 4

1 [English sentences]

Read an English sentence from the terminal. Count and report the number of occurrences of the alphabetic letters (a through z) in it. Also report the total number of distinct alphabetic letters in the sentence. Make no distinction between upper and lower case letters, i.e., 'a' is treated the same as 'A', 'b' the same as 'B' and so on. Neglect non-alphabetic characters (digits, punctuation symbols etc.).

A typical input/output session should be as follows:

Enter an English sentence :
This is Assignment 4 for CS13002 PDS Lab, Spring 2003, Section 1/A.
The numbers of occurrences of the alphabetic letters in the sentence are :
Total number of distinct letters : 17

Test input:

Report the output of your program on the following strings:

  1. The only nation who's name begins with an "A", but doesn't end in an "A" is Afghanistan.
  2. "Go!" is the shortest complete sentence in the English language.
  3. "Dreamt" is the only English word that ends in the letters "mt".
  4. Facetious and abstemious contain all the vowels in the alphabetical order.
  5. Right-handed people live, on average, nine years longer than left-handed people do.
  6. It's impossible to sneeze with your eyes open.
  7. The quick brown fox jumps over a lazy dog.
  8. My grandfather picks up quartz and valuable onyx jewels.
  9. A mad boxer shot a quick, gloved jab to the jaw of his dizzy opponent.
  10. Franz jagt im komplett verwahrlosten Taxi quer durch Bayern. (This is a German sentence which means: `Frank rushes through Bavaria in a completely neglected taxi.' Well then! Your program should not mind if you supply it a German sentence, when it expects English. Also note that the German alphabet is a bit bigger than the English alphabet; it has four additions: ä, ö, ü and ß. But you don't have to consider that. After all, your program is geared to English sentences.)

Remark: Use the C built-in function fgets to read an entire line containing spaces. Type man fgets at your shell prompt to know how this function should be called. Supply stdin (abbreviation of `standard input' meaning `your terminal') as FILE *stream. A typical usage is as follows:

char myString[1024];   /* Declare a character string of size 1024 */

printf("Enter a sentence : \n");   /* Prompt the user */
fgets(myString,1000,stdin);        /* Read a string of length <= 1000 from the terminal */

2 [The sieve of Eratosthenes]

Write a program that reads a positive integer n and lists all primes between 1 and n. Use the sieve of Eratosthenes described below:

Use an array of n cells indexed 1 through n. Since C starts indexing from 0, one may, for the ease of referencing, use an array of n+1 cells (rather than n). Initially all the array cells are unmarked. During the process one marks the cells with composite indices. An unmarked cell holds the value 0, a marked cell holds 1. Henceforth, let us abbreviate `marking the cell at index i' as `marking i'.

Any positive integral multiple of a positive integer k, other than k itself, is called a proper multiple of k. Starting with k=2, mark all proper multiples of 2 between 1 and n. Then look at the smallest integer >2 that has not been marked. This is k=3 and must be a prime. Mark all the proper multiples of 3 and then look at the next unmarked integer -- this is k=5. Then mark the proper multiples of 5 and so on. The process need continue as long as k<=sqrt(n), since every composite integer m, 1<m<=n, must have a prime divisor <=sqrt(n).

After the loop described in the last paragraph terminates, report the indices of the unmarked cells in your array. These are precisely all the primes in the range 1,...,n.

Now adjust the bound n in order to detect the t-th prime, where t is one million plus your PC number. Report n, your PC number and the t-th prime only in the output. Report no other primes.

Remark: No credit will be given, if any method other than the sieve of Eratosthenes is used to detect the desired prime.

[Course home] [Home]