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