5.11 Assignments


1. What is the difference between an abstract data type and a transparent data type?

2. What must the specification of an abstract data type include?

3. What is the difference between a built-in ordinal data type and a user-defined ordinal data type? Illustrate with an example of each, and indicate what kind of operations can be used with each.

4. Explain why one cannot write WriteString (January) where January is a value of an enumerated type MonthNames.

5. Consider the module SimplePay in section 5.2.1. Why is it necessary to have the value Saturday in the enumeration even though it is not used?

6. Describe some advantages of using subranges.

7. Which of the following ranges is incorrectly specified, and why?
a) [10 .. 5]
b) ["0" .. 9]
c) [a .. e]
d) ["a" .. "Z"]

8. What is the difference between an iterated repetition, and the more general counted repetition?

9. Why are the WHILE and FOR loops not equivalent?

10. Which of the following are incorrect and why?
a. FOR count = 1 TO 15 DO
b. FOR count := 15 TO 1 DO
c. FOR count := "a" TO "z" DO
d. FOR boolVar := FALSE TO TRUE DO
e. FOR day := Mon TO Fri BY 2 DO
f. FOR count := 1.5 TO 10 DO
g. FOR count := 1 TO 10 BY 1.5 DO
h. FOR count := 1 TO 10 BY count DO

11. When the following code is compiled, all is well. However, when it is run, there is always an out-of-range error. Why?

  countRange = [1 .. 10];
  count : countRange;
  count := 0;
  WHILE count <= 10
      statement sequence;
      INC (count);

12. Using DayName as defined in the chapter: (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday); consider the following statement sequences. If an error arises, indicate the nature of the error. Assume that cardVar is of type CARDINAL and has the value of 2 at the beginning of each statement sequence, and answer with the final value of cardVar or day in each case.
a) cardVar := cardVar + ORD (Wednesday);
b) day := Monday;
day := day + 2;
c) day := VAL (DayName, 3);
INC (day, ORD (Monday));
d) cardVar := ORD (VAL (DayName, 2)) - 5;
e) day := Friday;
INC (Friday, 2);

13. Both assignments to the variable count in the following code are incorrect. In each case, why?

FOR count := 1 TO 100 DO
  statement sequence1;
  count := count + 2;
count := count + 2;
statement sequence2;

14. What is wrong with the following nested loop:

FOR count := 1 TO 10
    FOR count := 2 TO 10
        statement sequence;

15. The following loop constructions each contain the statement WriteString ("Hi") at their innermost point to represent the working code of an entire statement sequence. In each case, state the number of times the sample statement executes.

 FOR count := 2 TO 100 BY 3
     WriteString ("Hi");
 FOR count := 200 TO 100 BY -13
     WriteString ("Hi");
 FOR outerCount := 2 TO 100
     FOR innerCount := 2 TO 10
         WriteString ("Hi");
 FOR outerCount := 2 TO 100 BY 3
     FOR innerCount := 2 TO 10 BY 5
         WriteString ("Hi");
 start := 5;
 FOR count := start TO 1
     WriteString ("Hi");

16. Indicate what will be the output from each program segment. Pay attention to carriage returns and spacing.

    GString := "chord";
    FOR i := 0 TO 4
        FOR k := 1 TO 4
            WriteChar (GString [i]);
      i := 5;
      WriteCard (i, 10);
      INC (i, 2);
    UNTIL i = 7;
    FOR i := 1 TO 5
        FOR j := i TO 3
            WriteCard (i, 0);
            WriteCard (j, 2);

17. What is the mathematical name for a two-dimensional array?

18. Show how you would (i) declare, (ii) fill with zeros, one row at a time an n by m two-dimensional array.


19. Show how to modify the code of the module LetterCounter in Section 5.5 to ignore any non alphabetic characters and to regard uppercase and lowercase versions of a letter as the same letter.

20. Modify the module SimplePay in section 5.2.1 to take into account the following additional considerations:

21. Modify the module ClassMarks in section 5.4.2 to allow the individual marks to be weighted. The weights should be expressed in decimal form, and should add to 1. The data input should have the weights of the mark categories on the third line before the first student's name.

22. Write your own short program to print out the ASCII character values and their corresponding ordinals. You should start with CHR (32) and end at CHR (126) as the ones below 32 and above 126 are control characters and may affect your display, program, or computer in rather unexpected ways, and the ones above 127 are not defined for the purposes of Modula-2. (They may be graphics characters on your machine--want to try?) Print out the material and put it in your notebook for future reference.

23. Consider the letter counting and word averaging program in section 5.5. Improve on it so that starting and ending punctuation is not included in the length of a word. Thus, when the program encounters "hello," all eight printable characters are recorded in the frequency array, but only the five alphabetic characters are used in computing the average word length. If the word is a qualified identifier such as STextIO.WriteChar, that is, the punctuation mark is in the middle of a letter group, it should be included for purposes of computing the average word length. Numbers should be included if they are part of an alphabetic word such as identifier1, or goody2shoes, but not when they are part of literals such as 234 or 15.3.

24. Write a program that will take an input word (say, with about four different letters) and write out all possible "words" (anagrams) based on permutations (rearranging the order) of the letters of the given word. Make sure you don't use a letter twice. Use only STextIO.WriteChar for the output, not STextIO.WriteString.
Sample Input:
Sample Output: (Your algorithm may produce a different order.)
two tow wot wto otw owt

25. Write a program that will test a selection of text and determine the average number of syllables per word. You may take as a simple definition of a syllable that it is a consonant followed by a sequence of one or more vowels. Some exceptions to this rule are words that start with vowels or that end with y, which is then a vowel.

26. Write a program that will analyze a selection of text and create a table of frequencies for the letters of the alphabet only. The results should be printed out in order of the most frequently occurring to least frequently occurring letter. (This could be used to decode "secret" messages sent in simple letter-for-letter substitution cyphers.)

27. Consider the PROCEDURE AddArrays3 in section 5.6 and suppose that HIGH (vect1) does not have to equal HIGH (vect2). This leaves some additions undefined, so assume that any extra elements supplied are zero and any extra elements in the result are set to zero. Modify the procedure to work this way and test it with two different test sets of data, each involving two arrays of different sizes. (Six different sizes altogether, please; twice with vect1 larger, twice with vect2 larger, and twice with ansVector larger.)

28. Suppose you have a one-dimensional array of up to ten CARDINALs. Write a procedure to find the smallest one and swap it with the first element. You may want to use a Swap procedure as well. Now write a Module that sorts the whole array this way with successive calls to this procedure scanning elements 2 .. N, 3 .. N, and so on, each time selecting the smallest remaining one. Test with the input data 2, 84, 1, 5, 63, 89, 12, 15. Have the results printed. (This is called a selection sort.)

29. In section 5.6 a procedure was developed for adding two vectors of indefinite length. Write and test a similar procedure for finding the dot product of two vectors of indefinite (but equal) length.
PROCEDURE dotProduct (vect1, vect2 : ARRAY OF INTEGER;
VAR dotOk : BOOLEAN; VAR result : INTEGER);
The procedure should return an error in the manner of AddArrays4 if the lengths of the two open array parameters do not agree. To compute the dot product, multiply the corresponding components together, and add up all the products. Thus if a = (a1 a2) and b = (b1 b2), then a · b = a1b1 + a2b2.

30. Write and test a procedure for determining the length of a two dimensional vector and the angle it makes with the x-axis. If a = (a1 a2), r represents the length and theta is the angle, then r2 = x2 + y2 and theta = arctan (y/x), where arctan may be imported from RealMath.

31. Complete and test the example EnrollData in section 5.8.

32. Write a program to record the marks of an entire class of students and calculate their letter grades. Feel free to use the example ClassMarks of section 5.4.2 for part of this. What you will also need is an array to store student names and another one for their marks, say on four tests, each out of one hundred. Provision should be made for weighting as in problem 16 above. You also need sections for entering the data and for printing it out along with the final letter grades. Make good use of procedures.

33. Twin primes are primes that differ by two. Thus 3 and 5, 5 and 7, 11 and 13, and so on are twin primes. Write a program to examine a file of primes created by a program like the example in section 5.9 for twin primes, and print out all the twins it finds.

34. The Fibonacci sequence is defined by a1 = 1, a2 = 1, and for i > 2, ai = ai-1 + ai-2 so that the numbers in the sequence are 1, 1, 2, 3, 5, 8, 13, etc. Write a procedure Fib (n) to calculate the value of a member of this sequence. Write the surrounding Module to test and print not only Fib (n), but also the ratio Fib (n) / Fib (n-1). Do this for successive values of n, up to the largest CARDINAL that does not give an overflow error. Does the ratio appear to be approaching a particular value?

35. Assume that you only have ReadChar available, and not ReadCard. Write and test a procedure to read in a Cardinal value one digit at a time and store each digit in an array. Write and test a procedure to write these numbers out one character at a time. Write and test a procedure to add two such numbers, one digit at a time. Make no use of cardinals larger than 9 or of reals, just arrays of the digits. Test your procedure now by making them read in, add, and print out the answers to:
a) 760 + 429
b) 62481 + 39862
c) 41839276 + 84321475

36. Write a Module that solves a system of two equations in two variables using determinants (Hint: look up and use Cramer's rule).

37. Extend your solution in #36 to encompass three equations in three variables.


38. (For the really ambitious Mathematician) Write a recursive procedure to calculate the determinant of an n x n matrix. Use an open array. Compute the dimension of the array passed within the procedure.

39. Write a program Module to play the game of tic-tac-toe on the screen. Use an array to hold the current values of the nine boxes. The machine should play the best possible strategy--if it goes first it should always win or draw, regardless of the user's strategy.

40. A number is divisible by nine if the sum of its digits is divisible by nine. Write a program to test a number that is entered as a string of digits, one character at a time, to see if it is divisible by nine. (This problem would be trivial if you were allowed to enter the number as a CARDINAL.)

41. A number is divisible by nine if the sum of its digits is divisible by nine. Write a program to test a number that is entered as a string of digits, one character at a time, to see if it is divisible by nine. (This problem would be trivial if you were allowed to enter the number as a CARDINAL.)

42. Write a program to produce a calendar of an entire year given the year.

43. A square (n by n) matrix is diagonal if only non-zero entries in the matrix are on the main diagonal (at positions 1,1 2,2 3,3 etc.) If all the entries on the main diagonal are equal to one, the matrix is an identity matrix. If all the entries above the main diagonal are zero, it is lower triangular, and if all the entries below the main diagonal are zero, it is upper triangular. Write and test a procedure to classify square matrices of any size as one or more of the above.