Computer Science Assignment 6

COMP 2103X1 Assignment 6 Due Thursday, March 2 by 7:00 PM General information about assignments ( important!):

http://cs.acadiau.ca/ ~jdiamond/comp2103/assignments/General-info.html Information on passing in assignments:

http://cs.acadiau.ca/ ~jdiamond/comp2103/assignments/Pass-in-info.html Information on coding style:

http://cs.acadiau.ca/ ~jdiamond/comp2103/assignments/C-coding-style-notes [1] Searching for strings is an extremely common operation in a lot of programs. For this problem you will write a program which accepts two strings as command­line arguments and output some information as described below.

Consider the following text(written by a famous mathematician/logician) There was one who was famed for the number of things He forgot when he entered the ship:

His umbrella, his watch, all his jewels and rings, And the clothes he had bought for the trip.

(I've written this on four lines, but it is really one string with a “ ” character following each of the lines.) Now suppose our search stringis “forgotten”. In this case, the word we want is not in the text, but various pre xes of the string are. Your program should nd the rightmost occurrence of the search string, if it exists, and otherwise of all instances of the longest pre x of the search string in the text, it should nd the rightmost one.

In either case, your program then outputs two numbers, as shown below in the examples. The rst number is the number of characters of the search string which match, and the second number is how many characters from the right end of the text to go backwards (to nd the match).

For example, the pre x “forgot” (of “forgotten”) is found 128 characters back from the end of the string, and the length of this longest matched pre x is 6. Thus your program will output “6;128”.

Here are some examples of how your program should operate. You mustinclude these samples, as well as some of your own creation, when you create your script le.

$a6p1'twas brillig ' 'was not ' 4;11 $a6p1 'aaron aardvark ' 'aaabbb ' 2;8 $a6p1 'aaron aardvark ' 'qwerty ' 0;q $a6p1 hicdefghi hi 2;2 $a6p1 'A two-line text string 'inky 2;3 1 You will notice that if there is no (non­empty) pre x of the search string in the text that the program outputs 0 for the matched length (as expected) but instead of outputting the distance from the end, it outputs the rst character of the search string. Your program must do this as well.

What other unusual cases should your program deal with? If there are any that you can think of, the comment at the top of your program should describe these cases and what your program does with them. Your program should never “blow up”.

Finally, notice that by surrounding the text and search string with single quotes, the spaces be­ come part of their respective command­line argument, rather than acting as argument separators.

Similarly, an embedded newline character becomes part of the argument when enclosed in quotes, rather than completing the command.

[2] Write a program which does the following things. — Declares a 4 4 matrix of ints.

— Reads in such a matrix (from stdin).

— Prints out the matrix in a rectangular array (see examples and further directions below).

— Prints out “It is upper triangular.” if the matrix is all zeroes below the main diagonal.

— Prints out “It is lower triangular.” if the matrix is all zeroes above the main diagonal.

— Prints out “It is not triangular” if it is not all zeroes either above or below the main diagonal.

— Prints out a blank line and then the transpose of the matrix.

— Prints out a blank line and then “It is symmetric.” if the transpose of the matrix is equal to the matrix, otherwise “It is not symmetric.” You should test your program on enough matrices to show that your program detects all the different possibilities. Naturally, you should use good programming practices when writing your program.

You might want to store test data in les, rather than repeatedly typing matrix data in. If so, in your script le you should display the contents of your test les with cat.

If your program is reading from the keyboard, you mustprint out a prompt, asking the user for the data. If the program is reading from a re­directed le (e.g., a6p2 < test1) or from a pipe (e.g., cat test1 | a6p2 ) then DO NOT print out a prompt. You can use the isatty()library function (see man 3 isatty ) to determine whether you are reading from the keyboard or not.

Note that isatty() takesfd(“ le descriptor”) as its parameter. You can get the correct fdby using the return result of fileno(stdin).Ž Here is an example of what running this program might look like. %a6p2 Please enter 16 integers:

1 0 3 4 0 4 5 6 0 0 9 0 0 0 0 8 The matrix is:

1 0 3 4 0 4 5 6 Ž Note that some historically signi cant early computer terminals were made by Teletype Corpora­ tion, and consequently “tty” became a generic short form for “computer terminal”. Thus “ isatty” means “is a tty”, i.e., “is a terminal”.

2 0 0 9 0 0 0 0 8 It is upper triangular.

Its transpose is:

1 0 0 0 0 4 0 0 3 5 9 0 4 6 0 8 It is not symmetric.

% %a6p2 < test2 The matrix is: 1 233 6666 -4 0 4 5 236 0 0 9 0 77 0 0 8 It is not triangular.

Its transpose is: 1 0 0 77 233 4 0 0 6666 5 9 0 -4 236 0 8 It is not symmetric.

For this assignment, you should ensure that you were able to correctly read 16 integers, but you do not need to do sophisticated error handling; if stdindoes not have 16 consecutive integers for you, write out an error message and terminate the program.

You should write a function which takes two 4 4matrices and stores the transpose of the rst matrix into the second matrix.

Your code to perform the tests on the matrix should be in one or more functions, not in the main program. Similarly, good design practices should lead you to put the code to read the matrix in its own function.

When printing the matrix, make the columns as narrow as possible, as shown above. That is, nd the number with the largest printed width, and print allof the numbers in elds that wide. (And separate columns with one space.) 3 [3] When you study algorithm analysis, you will nd (or attempt to nd) mathematical functions which describe how long a given algorithm will take to work on a problem of a given size. Sometimes this is easy, sometimes it is more dif cult, and sometimes it may be extremely dif cult or impossible.

Sorting is a very important and well­studied problem in computer science. Consider the following algorithm, which sorts an array of nnumbers, using the following idea. First, nd the smallest number in the array and save it as the rst sorted number. Then, nd the smallest number in the rest of the array and save that as the smallest number. Continue doing this until there are only two numbers left; when you have found the smallest of those two numbers, the remaining number is the largest.

This idea can be formalized as follows:

SelectionSort(array[1..n]) for i = 1 to n-1 minpos = i for j = i+1 to n if array[j] < array[minpos] minpos = j if minpos != i swap(array[minpos], array[i]) In sorting algorithms we often count the number of comparisons of data items and use that as the measure of how long an algorithm takes. In this case, we can see that the inner forloop does n 1 comparisons the rst time, n 2comparisons the second time, and so on down to 1 comparison the last time. Thus we can say that the amount of time used by selection sort to sort nnumbers is T .n/ Dn 1 X i D 1i forn > 0 which is a sum we can solve with elementary mathematics, giving us T .n/Dn.n 1/=2 .

I told you that story so I can tell you this story.

Some algorithms operate by breaking down a big problem into two or more smaller problems, of more or less equal size. (This breaking down may or may not require some work to be done, depending on the situation.) Then the sub­problems are solved, which takes some time, and the solutions are combined to give us a solution to the original problem, which may also take some time. Such techniques fall into a class of algorithms known as divide and conquer.

The equations describing divide and conquer algorithms (and some other classes) are much more complex than the one given above. For example, the time required by one well­known algorithm can be described as follows T .n/D 0 ifn < 2 T . dn=2 e/ C T . bn=2 c/ C n 1 otherwise .

/ In other words, we break the problem into two sub­problems whose sizes are as equal as possible, we solve those problems, and we use another n 1operations in the “break apart” and/or “put together” phases.

4 These equations can be dif cult to solve sometimes. Since this is COMP 2103, instead of solving equation . /, write a program which (i) prompts the user for two numbers, (ii) inputs two numbers, and (iii) outputs a table of nversus T .n/for all numbers between the two input numbers.

For example, here is a possible terminal session, user input inred: $a6p3 Enter two numbers:2 4 n | T(n) ------+-------- 2 | 1 3 | 3 4 | 5 Your table doesn't have to look like mine, but try to make it something you'd be proud of, not something you'd try to hide. Also, keep in mind that T .n/will get large sooner or later, so try to keep that in mind while designing your table layout.

To solve this problem, create a recursivefunction which, when given a non­negative integer n, returns T .n/. Then call this function as needed from the place in your program where you are printing out the table.

When creating your script le run your program a few times with different inputs to test boundary conditions, invalid inputs, and so on. And, of course, at least one case where everything is correct. Did you use functions in any of these questions? Should you have? Did you document them correctly?

Does you program “blow up” on unexpected input, or does it deal with bad input in a “graceful” way?

How does your program deal with boundary conditions, if there are any?

Did you remember to put all required comments in? Does your program call out for any other comments in the body of the code?

5