P/NP, Final Review

CSE 332 (Section 10)

Original slides by: Nile Camai, Amanda Yuan

Announcements

• EX16 due tomorrow (12/09 11:59 PM)
• No lates accepted. However, remember that your lowest 2 exercises will be dropped and considered as “Above and Beyond” credit.
• Congrats on finishing project 3!! 🥳
• Late cutoff is tomorrow (12/09 11:59 PM) 💪
• Final Exam next Thursday (12/15 8:30-10:20 AM) 📝
• Usual lecture hall (CSE2 G20)
• Final Exam Review Session Tuesday (12/13 4:30pm-6:00pm)
• Location CSE2 G10
• Please fill out instructor evals!
• We really do look over every evaluation to help improve the course in future quarters!

P/NP

P, NP, NP-Complete

“NP” stands for:

​

​

What does it mean for a problem to be in NP?

P, NP, NP-Complete

“NP” stands for:

Nondeterministic Polynomial

​

What does it mean for a problem to be in NP?

Given a candidate solution to a decision problem, we can verify whether the solution is correct in polynomial time.

P, NP, NP-Complete

For the following problems, circle ALL the sets they (most likely) belong to:

Is there a path of weight at most k from one vertex to another vertex in a weighted directed graph?

NP P NP-complete None of these

Is there a cycle that visits each edge in a graph exactly once?

NP P NP-complete None of these

Will this program run forever?

NP P NP-complete None of these

Can we find the prefix sum of an array in parallel using 10 processors?

NP P NP-complete None of these

Is there a path that starts and ends at the same vertex that visits every vertex exactly once?

NP P NP-complete None of these

P, NP, NP-Complete

For the following problems, circle ALL the sets they (most likely) belong to:

Is there a path of weight at most k from one vertex to another vertex in a weighted directed graph?

NP P NP-complete None of these

Is there a cycle that visits each edge in a graph exactly once?

NP P NP-complete None of these

Will this program run forever?

NP P NP-complete None of these

Can we find the prefix sum of an array in parallel using 10 processors?

NP P NP-complete None of these

Is there a path that starts and ends at the same vertex that visits every vertex exactly once?

NP P NP-complete None of these

Snow Day

Snow Day

After 4 snow days last year, UW has decided to improve its snow response plan. Instead of doing “late start”' days, they want an “extended passing period” plan. The goal is to clear enough sidewalks that everyone can get from every classroom to every other eventually but not necessarily very quickly. Unfortunately, UW has access to only one snowplow.

Your goal is to determine which sidewalks to plow and whether it can be done in time for the first 8:30 AM lectures. You have a map of campus, with each sidewalk labeled with the time it will take to plow to clear it.

​

Snow Day Questions

1. What will the vertices of your graph be?
2. What will the edges be? You should at least say whether your edges are directed or not and whether they're weighted or not.
3. What algorithm will you run on your graph?
4. How will you interpret the output of your algorithm? (i.e. which sidewalks to plow “in the real world" instead of just in graph terms).
5. Briefly (2-4 sentences) explain why your model works. You should at least address why you ran the algorithm you did (e.g., why are you looking for a shortest path/MST/topological ordering/etc.) and how you are ensuring your algorithm will be able to produce an "extended passing period" plowing plan.

​

Snow Day Answers

• What will the vertices of your graph be?

Buildings

• What will the edges be? You should at least say whether your edges are directed or not and whether they're weighted or not.

Sidewalks - undirected (you can go either direction on a sidewalk), and weighted (by the time it takes to plow the sidewalk)

• What algorithm will you run on your graph?

MST finding algorithm, Kruskal’s

​

Snow Day Answers

d) How will you interpret the output of your algorithm? (i.e. which sidewalks to plow “in the real world" instead of just in graph terms).

Whatever edges are chosen are the sidewalks the plow should clear.

e) Briefly (2-4 sentences) explain why your model works. You should at least address why you ran the algorithm you did (e.g., why are you looking for a shortest path/MST/topological ordering/etc.) and how you are ensuring your algorithm will be able to produce an "extended passing period" plowing plan.

We want an MST because our goal is to connect everything cheaply (not find the shortest route from A to B). Look at the weight of the MST. That's how long it will take to plow. If the plow can start in time to finish by 8:30, then we can start on time!

Final Exam Review!

Best of luck on the final! :)

Thank you for attending section this quarter!