## #1

Climbing Stairs: You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Write an algorithm in StairsSlow.java that is recursive without any fancy speed ups.

Write an algorithm in Stairs.java that will run in $O(n)$ time.

**Use the BigInteger library to avoid overflow errors**

Test Cases:

$java Stairs 3 3 $java Stairs 4 5 $java Stairs 10 89 $java Stairs 20 10946 $java Stairs 30 1346269 $java Stairs 400~~1075736893~~//incorrect due to Integer overflow. 284812298108489611757988937681460995615380088782304890986477195645969271404032323901 //correct using BigInteger

## #2

Largest Rectangle Area: Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

$java LargestRectangleArea 2 1 5 6 2 3 10 $java LargestRectangleArea 2 2 5 6 2 3 3 14 $java LargestRectangleArea 4 4 2 1 2 3 3 8 $java LargestRectangleArea 1 2 3 4 5 6 7 8 20 $java LargestRectangleArea 1 2 3 4 3 2 1 10

## #3

Knapsack: Show the table generated by the Knapsack problem dynamic programming solution that was covered in class. The items and their weights are as follows: (i,v,w), (1,1,5), (2,4,4), (3,3,6), (4,5,3). What is the subset that yields the maximum value for a weight limit of 10?

Submit your table as a .csv file called “knapsack.csv” that is comma separated (when you submit it to users, cat the file to make sure it looks like “0,0,0,0,…”)

**Due:** 7/14 @5pm. Submit the code to users in a hw4 folder. Each question is 3 points and then 1 points for how easy it is to grade.