diff options
Diffstat (limited to 'assignments')
| -rw-r--r-- | assignments/1.md | 59 |
1 files changed, 59 insertions, 0 deletions
diff --git a/assignments/1.md b/assignments/1.md index 4247f10..30559f3 100644 --- a/assignments/1.md +++ b/assignments/1.md @@ -117,3 +117,62 @@ * b. How could we modify the algorithm so that it finds only the complete word `and` rather than the occurrence of the character sequance `a`, `n` and `d` that is contained within another word, such as `band`? +19. Refer to the pattern-matching algorithm in Figure 2.16. Explain how the + algorithm would behave if we accidentally ommitted the statement on Line 16 + that says `Increment k by 1`. +20. Design an algorithm that is given a positive integer `N` and determines + whether `N` is a prime number, that is, not evenly divisible by any value + other than 1 and itself. The output of your algorithm is either the message + `not prime` along with a factor of `N`, or the message 'prime'. +21. Write an algorithm that generates a Caesar cipher - a secret message in + which each letter is replaced by the one that is `k` letters ahead of it in + the alphabet, in a circular fashion. For example, if `k = 5`, then the + letter `a` would be replaced by the letter `f`, and the letter `x` would be + replaced by the letter `c`. (We'll talk more about the Caesar cipher and + other encryption algorithms in Chapter 8.) The input to your algorithm is + the text to be encoded, ending with the special symbol `$`, and the value + `k`. (You may assume that, except for the special ending character, the text + contains only the 26 letters `a...z`.) The output of your algorithm is the + encoded text. +22. Design and implement an algorithm that is given as input an integer value `k + >= 0` and a list of `k` numbers `N1,N2,...,Nk`. Your algorithm should + reverse the order of the numbers in the list. That is, if the original list + contained: + `N1 = 5, N2 = 13, N3 = 8, N4 = 27, N5 = 10 (k = 5)` then when your algorithm + has completed, the values stored in the list will be: + `N1 = 10, N2 = 27, N3 = 8, N4 = 13, N5 = 5`. +23. Design and implement an algorithm that gets as input a list of `k` integer + values `N1, N2,...,Nk` as well as a special value `SUM`. Your algorithm must + locate a pair of values in the list `N` that sum to the value `SUM`. For + example, if your list of values is 3, 8, 13, 2, 17, 18, 10 and the value of + `SUM` is 20, then your algorithm would output either the two values (2, 18) + or (3, 17). If your algorithm cannot find any pair of values that sum to the + value.`SUM`, then it should print out the message `Sorry, there is no such + pair of values`. +24. Instead of reading in an entire list `N1, N2, ...` all at once, some + algorithms (depending on the task to be done) can read in only one element + at a time and process that single element completely before inputting the + next one. This can be a useful technique when the list is very big (e.g., + billions of elements) and there might not be enough memory in the computer + to store it in its entirety. Wire an algorithm that reads in a sequence of + values `V >= 0`, one at a time, and computes the average of all the numbers. + You should stop the computation when you input a value of `V = -1`. Do not + include this negative value in your computations; it is not a piece of data + but only a marker to identify the end of the list. +25. Write an algorithm to read in a sequence of values `V >= 0`, one at a time, + and determine if the list contains at least one adjacent pair of values that + are identical. The end of the entire list is marked by the special value `V + = -1`. For example, if you were given the following input: + `14, 3, 7, 7, 9, 1, 804, 22, -1`. + the output of your algorithm should be a `Yes` because there is at least one + pair of adjacent numbers that are equal (the 7s). However, given the + following input: `14, 3, 7, 77, 9, 1, 804, 22, -1` the output of your + algorithm should be a `No` because there are no adjacent pairs that are + equal. You may assume in your solution that there are at least two numbers + in the list. +26. Modify the algorithm that you developed in Exercise 25 so that if there is a + pair of identical adjacent values, your algorithm also outputs, in addition + to the phrase `Yes`, the value of the identical numbers. So, given the first + list of numbers shown in Exercise 25, the output of your algorithm would be + something like `Yes, the numbers 7 and 7 are adjacent to each other in the + list`. |