#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.