EECS 281: Data Structures and Algorithms

EECS 281: Data Structures and Algorithms
Lab 10 Assignment
Q1 What kind of algorithms are Prim’s and Kruskal’s? (0.5 pts)
A. brute force
B. greedy
C. divide and conquer
D. branch and bound
E. none of the above

Q2 What kind of algorithm is selection sort? (0.5 pts)
A. brute force
B. greedy
C. divide and conquer
D. branch and bound
E. none of the above
Q3 What kind of algorithms are quicksort and mergesort? (0.5 pts)
A. brute force
B. greedy
C. divide and conquer
D. branch and bound
E. none of the above
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)
A. brute force
B. greedy
C. divide and conquer
D. branch and bound
E. none of the above
Q5 Which of the following statements are true? Select all that apply. (1 pt)
A. a brute force solution will always give you the optimal solution
B. 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
C. the greedy algorithm guarantees an optimal solution to the 0-1 knapsack problem
D. branch and 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
E. dynamic programming reduces both the time and memory used to solve a problem with
multiple overlapping subproblems
F. given n items and a knapsack capacity of m , the dynamic programming solution to the 0-1
knapsack problem runs in Θ( mn ) time
1
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)
A. branch and bound
B. backtracking
C. brute force
D. combine and conquer
E. greedy algorithm
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)
A. dynamic programming
B. brute force
C. divide and conquer
D. backtracking
E. greedy algorithm
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. A, B, C, E, G, D, F
B. A, B, G, C, E, D, F
C. A, F, B, G, D, C, E
D. A, B, G, D, C, E, F
E. A, B, C, G, E, D, F
2
~ 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:
● deals.h
● Makefile
● samples.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:
● write your implementation in the provided best_price() function — the function should
return the best price that you calculated
● use the provided discounted() function to compute the discount from applying a coupon
● you must either use a coupon or apply the punch card for each meal
● you have an unlimited number of coupons
● your program should run in linear time
● greedy solutions will not work (so do not even attempt writing one)
● instead, use dynamic programming!
3
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.
4