Climbing Stairs: You are climbing a stair case. It takes n steps to reach to the top.<\/p>\n
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?<\/p>\n
Write an algorithm in StairsSlow.java that is recursive without any fancy speed ups.<\/p>\n
Write an algorithm in Stairs.java that will run in $O(n)$ time.<\/p>\n
Use the BigInteger library to avoid overflow errors<\/strong><\/p>\n Test Cases:<\/p>\n 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.<\/p>\n 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?<\/p>\n 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,…”) <\/p>\n Due:<\/strong> 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.<\/p>\n","protected":false},"excerpt":{"rendered":" #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… Read more »<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,1],"tags":[],"_links":{"self":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/355"}],"collection":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/comments?post=355"}],"version-history":[{"count":10,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/355\/revisions"}],"predecessor-version":[{"id":690,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/posts\/355\/revisions\/690"}],"wp:attachment":[{"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/media?parent=355"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/categories?post=355"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/josephpcohen.com\/teaching\/cs310\/wp-json\/wp\/v2\/tags?post=355"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}$java Stairs 3\r\n3\r\n$java Stairs 4\r\n5\r\n$java Stairs 10\r\n89\r\n$java Stairs 20\r\n10946\r\n$java Stairs 30\r\n1346269\r\n$java Stairs 400\r\n
1075736893<\/del> \/\/incorrect due to Integer overflow.\r\n284812298108489611757988937681460995615380088782304890986477195645969271404032323901 \/\/correct using BigInteger<\/pre>\n#2<\/h2>\n
$java LargestRectangleArea 2 1 5 6 2 3\r\n10\r\n$java LargestRectangleArea 2 2 5 6 2 3 3\r\n14\r\n$java LargestRectangleArea 4 4 2 1 2 3 3\r\n8\r\n$java LargestRectangleArea 1 2 3 4 5 6 7 8\r\n20\r\n$java LargestRectangleArea 1 2 3 4 3 2 1\r\n10\r\n<\/pre>\n
#3<\/h2>\n