[Solved] CS2123 Data Structures Midterm 1 Recursion Program

Given the high weight of this problem you should start early and ask questions if you get stuck. Be sure to not share code with any other students. This assignment should be the work of you and you alone. Cheating will result in a zero.

• Description

Jethro and Cleatus are quarantined at home and bored. They spend most of their day sitting at their computer monitor working or browsing the internet in their small apartment. Out of boredom Jethro begins counting the number of steps needed to reach each location in their small apartment. After seeing that taking different paths from their computer to their coffee maker yields different numbers of steps a question dawns on them. They want to know what is the fewest number of steps needed to reach all of the locations in their small apartment starting from their computer.

Fortunately, Jethro is quite skilled at ASCII art. So they model their room with ASCII characters. A space can be moved through. An asterisk * is a wall or furniture that cannot be traversed (no climbing over furniture!). Going up, down, left, right one space takes exactly one step (well assume no diagonal movements for that sake of simplicity). For example, here is a possible model of their room:

**************

*	*
* *	*
* *	*
* ***	*
*	*

• ***** *
• *** *

**************

Assume that (0, 0) is the upper lefthand corner. For the sake of simplicity you can assume the apartment is enclosed in * characters and that Jethros computer is located at (1,1).

Jethro is still new to programming and wants to hire you to write the program to label all of the locations in their apartment with the minimum number of steps needed to reach them. To keep with the ASCII art theme youll use the letters A-Z Such that:

A is 0 steps

B is 1 step C is 2 steps

Y is 24 steps

Z is 25 (or more) steps

For example, after running your algorithm on it, the apartment above should look as follows:

**************

*ABCDEFGHIJKL*

*BCDE*GHIJKLM*

*CDEF*HIJKLMN*

*DE***IJKLMNO*

*EFGHIJKLMNOP*

*FGHIJ*****PQ*

*GHIJK***SRQR*

************** Example 2:

**********************************

• *

**********************************

After applying your algorithm (we dont count past Z since Jethro has a pretty small apartment):

**********************************

*ABCDEFGHIJKLMNOPQRSTUVWXYZZZZZZZ*

********************************** Example 3:

*******

• *

**** *

• * *

*******

After applying your algorithm (unreachable areas should remain unchanged):

*******

*ABCDE*

****EF*

• *FG*

*******

3 Problems

PROBLEM 1: (5 points)

Write a brute force recursive definition/idea for this problem. Specifically write a recursive algorithm attempts to update the symbol located at (x,y) where

0 x < MAXWIDTH,0 y < MAXHEIGHT and then is recursively called on all adjacent locations.

Hint 1: From any given space, you need to try to continue moving up, down, left, and right. DO NOT try to travel diagonally.

Hint 2: Your algorithm CAN move into a wall or furniture spot, but upon recognizing it as uncountable, it should return from that call.

Hint 3: It will help to pass the distance traveled so far from the start.

PROBLEM 2: (5 points)

To make sure you understand how this recursion will work, draw a recursion tree diagram if the room were just 4 x 5 with no furniture. Start your tree at position (1, 1)

*****

• *
• *

*****

Hint 1: Heres the first 2 levels of your recursive call tree (the order of the calls on the 2nd level will depend on your pseudocode):

PROBLEM 3: (5 points)

Write a RECURSIVE program in C that implements your recursive algorithm.

The program must compile and run on the fox servers. Use valgrind on your program to try to find all possible defects before submitting.

Hint 1: chars can be treated like small valued integers. In particular, it may be helpful to use + and <= with your chars.

Your program must output the base room first, and then the updated room when done, like so:

Base room:

**************

*	*
* *	*
* *	*
* ***	*
*	*

• ***** *
• *** *

**************

Room after algorithm:

**************

*ABCDEFGHIJKL*

*BCDE*GHIJKLM*

*CDEF*HIJKLMN*

*DE***IJKLMNO*

*EFGHIJKLMNOP*

*FGHIJ*****PQ*

*GHIJK***SRQR*

**************

PROBLEM 4: (5 points)

What is the runtime complexity of your algorithm? We want to see HOW you arrived at your answer and if you are taking everything into account.

4 Deliverables:

Submit the following on Blackboard:

• a PDF, TXT, DOC file containing your answers for #1 and #4. Separate each problems answer with a few blank lines and give each a heading with its problem number.
• a PNG, JPG, PDF, or PPT file that is your answer for #2. Name the file so that it includes answer2 in its file name
• c which is the implementation for problem #3.