7.14 Assignments

Questions:

1. What is a Modula-2 string? Explain all terms used.

2. What is an implied abstract data type, and why is it more correct to use this terminology than to say that Modula-2 has a string type?

3. Suppose str1, str2, and str3 are of type String (ARRAY [0 .. 79] OF CHAR,) and str1 = "dogs ", str2 = "cats ", str3 = "chase". What will the assigned variable hold in each case, assuming it to be of the correct type?
a. Concat (str1, str3, D); Concat (D, str2, E)
b. m := Length (str3)
c. FindNext ("t", str3, 0, found, position)
d. i := CompareStr ("cat" , str2)
e. Copy (str2, 0, 1, F); Copy (str1, 1, 3, G); Concat (F, G, H)
f. Insert (str2, 2, str1); Delete (str1, 6, 2)
g. FindNext ("cat", "the old cat in the hat", 0, found, position);
h. FindPrev ("cat", "the cat in the hat sat on the bat", 26, found, position)

4. "Some string operations may silently truncate the result." What does this statement mean, and under what circumstances may this arise?

5. What is the difference between the Length of a string and the number returned by HIGH when it operates on a string?

6. When the following pairs of strings are compared, will the result be less, equal, or greater? Why?
a. "hare" and "hair"
b. "all" and "ALL"
c. "rick" and "Rick"
d. "%ages" and "pages"
e. "1" and "one"

7. For client programs of the module MenuHandler (Section 7.5) why is it necessary to initialize the first unused string to the null string?

8. (Research) Look up and be able to explain how DES encryption works.

9. Define mean, variance and standard deviation (both versions of the latter.)

10. Look up and write out a definition of the median of a data set. What additional facilities would be needed in addition to those in the statistical modules presented to calculate the median?

11. Look up and write out a definition of the mode of a set of data. What additional facilities would you suggest are necessary to do this calculation?

12. What are the advantages of separating the low level statistical functions from the high level ones?

13. Why are random numbers generated by a formula not really random numbers? (What are they called?) What can to be done to make them more random?

14. What is a matrix? State at least four substantially different applications of matrices.

15. What is a vector? State at least four substantially different applications of vectors in science.

16. Make a table listing the differences between the ADT Point and the ADT Vector.

Problems

17. Write a module that will read an input paragraph of text from the keyboard and reformat it and output it to the printer according to the following rules:
a. The first line is indented exactly five spaces.
b. Multiple spaces between words are reduced to single spaces.
c. There are exactly two spaces between sentences, regardless of how many are found in the original text.
d. As many complete words are printed on a line as possible and there are no words that are broken between lines. You may assume any convenient line length.

18. Pretend that you do not have the procedures Insert and Delete available from the module Strings. (In some cases, you won't.) Write them, and include them with the procedures Concat and Length in a module of your own. Test your module by calling on it in a program module and show the results on a printout.

19. Write a program module that will take lines of text as they are typed at the keyboard and save them into a disk file under an appropriate name. The text should go into the disk file as a continuous block with carriage returns only at the end of a paragraph. Define a paragraph as a carriage return followed by one or more spaces.

20. A Pascal string or a Macintosh string is an ARRAY [0 .. 255] OF CHAR, but the first CHAR is in position 1, with str [0] containing a CHAR whose ORDinal value is the length of the string (number of the last position). Note that such strings are limited to lengths of no more than can be accomodated in a storage location used by the type CHAR--usually this means no more than 255 characters to a string. Write a procedure StrModToPas that converts a Modula string to a Pascal string.

21. Add to #20 the complementary procedure StrPasToMod. Encapsulate both in a library module and test them with a suitable client program.

22. A word search game is played with an array of letters and a list of words that the player is expected to find in the array. Words may go in any direction (including diagonally) and a given letter may be part of more than one word.

A X Y T J K R E W
B L O O D F F W G
R A U D I T N W Q
A U L M O A O R U
T M I N T M O R E
E A T L Y Y E S R
M O D U L A M G Y

23. Write and test a procedure ConvertToDay, along similar lines to the procedure ConvertToMonth in section 7.4. Write also the procedure WhatDay, similar to WhatMonth in the same section. Test both. Now, test again with a driver program that makes a large number of calls to each and see which is more efficient.

24. Implement the menu generating module and test it with one of your own programs.

25. Implement the module Substitution in section 7.6 (the second way) and test it with a driver program that reads the coder/decoder key from the user. Now try encrypting a file and decrypting it again.

26. Rewrite the suite of statistical modules so as to have appropriate error handling. Include

TYPE
  StatsState = (StatsOK, ...); (* with appropriate values *)
VAR
  StatsStatus : StatsState;

and revise the code to set the value of StatsStatus appropriately. If it is available, reduce the probability of an overflow by accumulating the sums in the type LONGREAL.

27. Section 7.8 included discussion of the system dependent nature of randomizers that depend on a special memory location that the system periodically updates. Either implement the module Randoms without this provision, or find such a location for your system, or some similar means of obtaining a seed from the system and rewrite the system dependent code in the suggested module.

28. Write a short program module to generate an array of at least ten thousand random cardinals. Write the array out to a disk file for further reference.

29. At the beginning of section 7.8 the procedure Generator.Random was developed to produce random numbers between zero and one. Write a new version of the later module Randoms that uses this procedure as the basis for generating random cardinals or random numbers in some cardinal subrange.

30. The procedure RndInRange as presented in section 7.8 will not work very well if the range is a large fraction of the whole cardinals. For instance, suppose the cardinals are in the range [0 .. 65535] and the selected range for random number generation is [0 .. 9999]. In this case too many of the random cardinals generated have a second digit of 5 or less, so more than the proper share of the numbers in the range [0 .. 9999] will be in the subrange [0 .. 5535]. Compute what are the expected and proper percentage of numbers generated in the subrange [0 .. 5535]. Run the code given in the text, generating a large number of random numbers and determine the actual percentage generated in this range to confirm this. (This will require a replacing of the question with an appropriate range and some extra steps if the range of cardinals is different on your machine.) Now rewrite the code to eliminate this bias.

31. Can you predict what ought to be the standard deviation of a population (and a sample) of randomly distributed numbers over a range? Test your prediction with a suitable program module and the file of random numbers you created earlier.

32. There are a variety of ways of testing the effectiveness of random number generators. One is simply to find the mean of the numbers and see if it lies in the middle of the range selected. You may wish to try this and to research other methods as well. One method that is fairly easy to implement if your terminal is capable of graphics is to convert the random numbers generated into ordered pairs that represent points on the graphics screen over the complete range of possible horizontal and vertical coordinates allowed (look this up for your machine) and then plot a dot at that point. If your program is allowed to run long enough, it should eventually plot every possible dot and there will be no blank spaces at all on the screen. If, on the other hand, your random number generator is flawed, repetition will set in, and some space will remain no matter how long you allow it to run. How good is yours on a test like this? You will, of course, have to look up the module for handling graphics on your terminal.

33. Rewrite the procedure Multiply in section 7.8 to operate by converting both numbers to reals, performing a real multiplication, stripping the amount over maxcard and converting back to a cardinal.

34. Implement Addition, Subtraction, Multiplication, and Division (the latter is a challenge) on the type BigCard. You will have to change the error type to an enumeration, as there are more than just overflow errors to contend with now.

35. Modify the code produced in the last section so that the procedures can handle user-defined types of a type similar to but bigger than the convenience type BigCard that the suggested module exports. That is, they should take parameters that are ARRAY OF CARDINAL rather than BigCard and operate correctly regardless of how many components there are. If you have a larger range for CARDINAL on your machine, you may wish to store more than four digits in each component.

36. Modify the procedure WriteBigCard to take a second parameter that is the field length in which to write the BigCard. Your code will have to pre-scan the BigCard to be written to find out how many spaces it would occupy. If too little is available, it should take what space it needs. If the field length is longer than needed, the number should be padded on the left with blanks.

37. Design, define, implement, and test a module to do matrix arithmetic and operations. You must decide which operations to include, providing a rationale for your decisions, write and compile the definition module, and then implement that definition, define a test harness program, and thoroughly test your implementation.

38. Implement the determinant computation procedures given in section 7.10.2 with the addition in the client program of a test to distinguish between the two cases where the determinant is zero, and appropriate messages for the two cases. Also, test your program on systems of two, three, four, five, and six variables, timing each solution. You may wish to make use of files to input the data, if OpenInput is available in some form. What is the practical limit on your machine for solving systems of equations in this way?

39. Complete and test the module Vectors in section 7.11 and develop a test harness to check your work thoroughly.

40. A ship heads due East at 15 knots. It is influenced by a current of 10 Knots setting to the Northwest, and a wind of 10 Knots from the South. Ignoring the effects of friction, what will be the resultant velocity? (Solve this with a program module that is a client of the module Vectors.)

41. Write a client of the module Vectors that computes the resultant force of any two supplied force vectors. You can decide what format the vectors are to be input in from the keyboard or a file, and what units to use.

42. An old problem in probability has a solution that rather astounds many people. If two people are in a room, what is the probability that both were born on the same day of the year? (Answer 1/365--ignore Feb 29) Now toss in a third, and ask what is the probability that two of the three have the same birthday. This is a little harder computation, but still not very difficult. The problem is to discover how many people need to be in the room before it becomes a 50-50 proposition that at least two will have the same birthday. Get the computer to do the computations for you. The answer is not very large, is it?

Research Projects and Challenges

43. What are the most secure encryption algorithms? Implement and test one of these.

44. What is the cross product of two vectors? What is it used for in practical applications? Design a library module abstracting a three dimensional vector type. Implement and test this, including the cross product. Build a client application to solve a practical problem using cross products and test it.

45. Implement and completely test the module FinanceMath in section 7.12, ensuring that all formulas are correct by comparing the results with those obtained on a financial calculator. You may decide to add one or more procedures. If you do, be sure to provide a complete rationale and documentation.