Reading Algorithms

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

   Related Questions in Programming Languages

©TutorsGlobe All rights reserved 2022-2023.