C++案例 Q1 What kind of algorithms are Prim’s and Kruskal’s? (0.5 pts)

bruteforce
greedy
divide andconquer

EECS 281: Data Structures and Algorithms, Fall 2018
Lab 10 Assignment
Canvas Quiz and Autograder due December 14th by 11:59pm

(NEW THIS SEMESTER: START EARLY ON THE AUTOGRADER PORTION)
dynamic C++案例dynamic C++案例

Q1 What kind of algorithms are Prim’s and Kruskal’s? (0.5 pts)
bruteforce
greedy
divide andconquer
branch andbound
none of theabove


Q2 What kind of algorithm is selection sort? (0.5 pts)
bruteforce
greedy
divide andconquer
branch andbound
none of theabove


Q3 What kind of algorithms are quicksort and mergesort? (0.5 pts)
bruteforce
greedy
divide andconquer
branch andbound
none of theabove


Q4 Your company is working on a map application but has run into a roadblock in their algorithm — finding the shortest route from point A to point B takes too long for practical use! Upon further analysis, you realize that the algorithm often does unnecessary work by traversing paths that are worse than the current optimal path. What algorithm can you use to fix this problem? (0.5 pts)
bruteforce
greedy
divide andconquer
branch andbound
none of theabove


Q5 Which of the following statements are true? Select all that apply. (1 pt)
a brute force solution will always give you the optimalsolution
because backtracking avoids looking at large portions of the search space by pruning,the asymptotic complexity of backtracking is always better than that of brute force
the greedy algorithm guarantees an optimal solution to the 0-1 knapsackproblem
branchand bound will not speed up your program if it will take at least just as long to determine the bounds than to test all choices
dynamic programming reduces both the time and memory used to solve a problemwith multiple overlapping subproblems
givenn items and a knapsack capacity of m, the dynamic programming solution to the 0-1 knapsack problem runs in Θ(mn) time

Q6 You want to color a graph of the United States such that no adjacent states share the same color.
Which of the following algorithm families would be best at accomplishing this task? (0.5 pts)

branch andbound
backtracking
bruteforce
combine andconquer
greedyalgorithm


Q7 The dining hall just closed for the night, and the workers have started kicking everyone out. As the other students leave, you realize that you have a problem on your hands – you got way too much food! You still have several uneaten dishes on your table, and each of these dishes gives you different levels of satisfaction. You are not obligated to fully finish a dish once you start it. However, your stomach can only handle so much, and you prefer not to throw up after you leave. Which algorithm family would be most efficient at determining what you should eat to maximize your satisfaction, while also considering the capacity of your stomach? (0.5 pts)
dynamicprogramming
bruteforce
divide andconquer
backtracking
greedyalgorithm


Q8 You are using Dijkstra’s algorithm to find the shortest path from A to every other vertex in the graph above. S is the set of vertices for which the minimum path weight from A has been found. A is the first vertex you add to S. Which of the following gives the correct order in which vertices are added to S? (1 pt)
A, B, C, E, G, D,F
A, B, G, C, E, D,F
A, F, B, G, D, C,E
A, B, G, D, C, E,F
A, B, C, G, E, D,F

~ NEW THIS SEMESTER – LAB 10 AUTOGRADER PORTION ~

Dynamic Programming: A Meal at the ChEECScake Factory

10 points.


Your favorite restaurant, the ChEECScake Factory, has a customer loyalty program. On your first visit to the restaurant, you are offered a punch card. Whenever you purchase a meal at full price, you can add one hole punch to your punch card. Once you have five punches, you can turn in the card for a free meal and a brand new punch card.

For example, if your meals cost [3, 3, 3, 3, 3, 3, 3, 120], then you should earn hole punches on the first five meals ($15), pay normally for the next two meals ($6), and then turn in the punch card so that the $120 meal is free! The lowest cost would be $21 ($15 + $6).

However, you ALSO have a lot of coupons that can be used at the restaurant. In fact, you have enough coupons that you can apply one to every meal! If you apply a coupon, you get a 25% discount on that meal. But there’s a catch: if you apply a coupon, you don’t get to add a hole punch to your punch card! Using the example above, you would be able to use coupons on the two $3 meals before the $120 meal, which would bring the lowest cost down to $19 ($15 + 0.75*$3 + 0.75*$3, rounded down).

Consider another example: if your meals cost [2, 2, 2, 2, 1000, 100] and you use the first five meals to earn hole punches, you would need to spend $1008 to get the $100 meal for free. It would be much better to apply the 25% discount to each item so that you pay a total of $829. Note that we apply the discount separately to each item and round down, so we’ll pay $1 + $1 + $1 + $1 + $750 + $75 = $829.

There are, however, many cases where it would make sense to use a mixture of punch discounts and discounting coupons. This is where your program comes in! Write a program that, given a vector of meal prices, calculates the MINIMUM cost needed to pay for the meals using the hole punch loyalty program and restaurant coupons.



Implementing the Program
Download the following three starter files from the lab10 folder on Canvas:

h
Makefile
cpp


You will be doing your coding in the deals.h file. Do not modify the other two files! Here are some additional notes you should read before you begin coding:

writeyour implementation in the provided best_price() function — the function should return the best price that you calculated
usethe provided discounted() function to compute the discount from applying a coupon
you must either use a coupon or apply the punch card for eachmeal
you have an unlimited number ofcoupons
your program should run in lineartime
greedy solutions will not work (so do not even attempt writingone)
instead, use dynamicprogramming!

Testing
Once you are done with your program, you may use the provided Makefile and samples.cpp file to test your implementation. The samples.cpp file includes 15 public test cases that you may use to check the accuracy of your program. Simply make an executable with deals.h and samples.cpp in the same directory and run it (using the command ./meals). If done correctly, you will get    something like this (the following output is just an example):



[meal #1] … PASS [meal #2] … PASS [meal #3] … PASS [meal #4] … PASS [meal #5] … PASS [meal #6] … PASS [meal #7] … PASS [meal  #8] … PASS
[meal #9] … FAIL: expected 33929 but got 33932 [meal #10] … PASS

[meal #11] … PASS

[meal #12] … FAIL: expected 23422 but got 23426

[meal #13] … FAIL: expected 9106 but got 9124

[meal #14] … FAIL: expected 15306 but got 15308 [meal #15] … PASS


You should use this output to help you debug your code. To further help you with the debugging process, the comments under each test case in the samples.cpp file also provide the total cost with no discounts or promotions, the total cost with only coupon discounts, and the total cost if the punch card is always applied.





Submitting to the Autograder
Before submitting, add you and your partner’s names to the top of the deals.h file. To submit to the Autograder, create a .tar.gz containing just deals.h:



tar -czvf lab10.tar.gz deals.h



If you are working with a partner, both partners must submit to the Autograder. Only students who submit code to the Autograder will receive points. It’s perfectly fine for both partners to submit identical code, as long as the code was written by both of the partners.



You will be able to make 5 submissions to the Autograder per day, up until the due date. Please take advantage of these extra submissions! It may even be helpful to make a submit even if you aren’t passing all 15 public test cases, as the Autograder may offer you helpful advice that will lead you in the right direction. Please do not wait until the last day to begin this – you can almost certainly expect a dynamic programming written question on the final, so an understanding of how to approach this problem (and problems like it) will be very important.