HW3

CS350

• Collaboration: You may work in groups of up to 3 students per group. Remember to clearly indicate the group members on your HW submission.
• Format: Preferably typeset in LaTeX but nearly handwritten is okay too, as a .pdf file.
• Submission: Your group submit your work in a single email to cs350pdx@gmail.com as well as all the group members.
• IMPORTANT: Provide an email subject line with the following pattern: HWx Section xxx - Full Name, Full Name, Full Name

---

Problem 1: Power Algorithm
(a) Design a recursive algorithm for computing $2^n$ for any non-negative integer $n$ that is based on the formula $2^n = 2^{n-1} + 2^{n-1}$.

(b) Set up a recurrence relation for the number of additions made by the algorithm and solve it. Show your work.

(c) Is it a good algorithm for solving this problem? Describe a better approach.

---

Problem 2: Maze Solving

Starting with a map represented by a rectangular grid with
height $h$ and width $w$. Cells are numbered (0, 0) in the top left to ($h−1$, $w−1$)
in the bottom right. Each cell in the grid is either empty or contains an
impassable object. All movements on the map are done as a single step to
a cell that is adjacent horizontally or vertically. No diagonal movement is
permitted.

(a) Write an algorithm that uses a breadth first search to find the
length of the shortest path from $(0, 0)$ to $(w − 1, h − 1)$. Return $−1$ if no
such path exists.

(b) What is the worst case complexity for your algorithm? Be sure
to specify how the input size is measured and show your work.

(c) Modify your algorithm from part (a) to return the shortest
path from $(0, 0)$ to $(w − 1, h − 1)$ in addition to its length. How does your
change affect the time complexity? How does your change affect the amount
of memory required.