Assignment 1: Algorithms
Rules: See the Assignment Rules file on the class Moodle site.
1 Reading Algorithms (20 points)
Input: A nonempty string of characters S1S2 . . . Sn, and a positive integer n giving the number of characters in the string.
Output: See the related problem below.
Procedure:
1 Get n
2 Get S1S2 . . . Sn
3 Set count = 1
4 Set ch = S1
5 Set i = 2
6 While i n
7 If Si equals ch
8 Set count = count + 1
9 Set i = i + 1
10 Print ch, ‘ appeared ’, count, ‘ times.’
11 Stop
Problem 1.1 What is printed if the input string is pepper?
Problem 1.2 What is printed if the input string is CACCTGGTCCAAC?
1
Problem 1.3 What is the output of this algorithm (in general)? Be precise.
Problem 1.4 Suppose line 3 was changed to Set count to 0. How would
your answer to the previous problem change?
2 Reading Another Algorithm (20 points)
The following pattern-matching algorithm was discussed in class, and is used
in this problem and in Problem 4 below.
Input: A string length n and a text string S1S2 . . . Sn of alphabetic charac-
ters, as well as a string length m and a pattern P1P2 . . . Pm of alphabetic
characters.
Output: A message indicating each time the pattern P matches a substring
of S.
1 Get n
2 Get S1S2 . . . Sn
3 Get m
4 Get P1P2 . . . Pm
5 Set i = 1
6 While i n − m + 1 do
7 Set j = 1
8 Set matchOK = true
9 While j m and matchOK = true then
10 If Pj 6= Si+j−1 then
11 Set matchOK = false
12 Set j = j + 1
13 If matchOK = true then
14 Print ’Match found between positions ’, i, ’ and ’, i + m − 1
15 Set i = i + 1
16 Stop
Problem 2.1 Trace through this algorithm when the text string S is
CGCCCTACCGGCACC and the pattern string P is CC. Specifically, (a) state what
the output would be, and (b) each time line 15 is reached write the current
values of i (before 1 is added to i in that line), j, and matchOK.
2
3 Writing Algorithms (20 points)
One task robots might need to do is to navigate through their environment
without bumping into obstacles, etc. Here’s a problem related to this task.
Suppose you have a very simple maze. There’s a designated start square,
a designated finish square, a single path from start to finish, and no dead
ends. Suppose you also have a robot that can do the following:
• moveForward: move forward one square.
• turnLeft: turn ninety degrees to its left.
• turnRight: turn ninety degrees to its right.
• startInMaze: this places the robot at the start square, and orients it
so its first valid move is straight ahead.
• checkForWall: check if there is a wall immediately ahead, and return
true if there is and false if there isn’t.
• checkForMazeEnd: this checks if the robot is at the end square, and
returns true if it is and false if it isn’t.
Using the correct combinations of these, along with other basic pseudocode
operations (get, set, etc.), you should be able to devise an algorithm that
gets a maze as input, places the robot on the start square, and navigates the
robot through the maze.
Problem 3.1 Write a pseudocode description that, given a maze as de-
scribed above, places the robot at the start, and then has it navigate through
the maze. Once the robot reaches the end, the algorithm should print out
a message stating it is at the end, and another stating how many moves it
made navigating the maze. However, it does not need to keep track of other
information such as the number of turns.
When writing your pseudocode, you do not need to specify the input and
output. However, you do need to give all the steps.
Note the robot can check for walls straight ahead, but cannot directly
check for walls to its right or left. Instead, it must turn first. So, for example,
to check for a wall to its right, a robot must first turn right, then check for
a wall.
3
In writing your pseudocode you need to use the specific functions above.
For example, you cannot just write, as a pseudocode step, Find an opening
and move in that direction. Instead you must specify how to use the
checkForWall, turnLeft, turnRight, and/or moveForward functions to do
this.
4 Modifying Algorithms (20 points)
This question again asks you to consider the pattern matching algorithm that
was discussed in class, and is given above in Section 2.
Problem 4.1 Suppose that instead of printing a message whenever there
was a match, you just want the algorithm to output the number of times
matches occur. For example, suppose the text string S is ATGCATAGATT, and
the pattern P is AT. Then the algorithm should output only the message
There were 3 matches.
Modify the pattern-matching algorithm to do this. For your answer you
may either write the entire algorithm, or you may just indicate exactly what
needs to be added or modified exactly where.
Problem 4.2 Sometimes you don’t need exact matches, but want to know if
the match failed only in a single location, or if it failed in two locations, etc.
Modify the pattern matching algorithm (the original version in Section 2, not
your modified version from the previous problem) so that it still outputs the
original message if there is a match, but otherwise, for each i value, states
the number of locations where the match failed. For example, if the text string
S is ATGGATATGATT and the pattern P is ATG, then the output would be
Match found between positions 1 and 3
The match starting at position 2 failed in 2 locations
The match starting at position 3 failed in 3 locations
The match starting at position 4 failed in 3 locations
The match starting at position 5 failed in 1 location
The match starting at position 6 failed in 3 locations
Match found between positions 7 and 9
The match starting at position 8 failed in 3 locations
The match starting at position 9 failed in 3 locations
The match starting at position 10 failed in 1 location
4
(If you do not understand this example, please ask the professor or a TA to
explain it.)
Modify the pattern-matching algorithm to do this general task. For your
answer you may either write the entire algorithm, or you may just indicate
exactly what needs to be added or modified exactly where.
5 Essay Question (20 points)
Some things that are relatively easy for humans to learn are very difficult
to express as algorithms. For example, consider tying shoelaces, a skill we
learned as children.
Problem 5.1 Write a medium sized paragraph (about one hundred words)
giving instructions to tie shoelaces for someone who has never done it before.
Problem 5.2 Is your description an algorithm? Why or why not? Are you
satisfied with it? Why or why not? (Answer in a few paragraphs, not more
than 300 words.)
Problem 5.3 Write a medium-length paragraph (about one hundred words)
discussing which types of things are difficult or impossible to express as algo-
rithms and which are easier.
5