Intractability
Intractability
Intractability worksheet [optional]
Logistics
New pods!
Status flags
Each team has a status flag that you can use to help me focus where to go:
green: working, no questions
yellow: have a question, but not blocked from doing work
red: have a question, blocked from doing work
blue: done, just hanging out
Articulation practice
Remember: this is an opportunity to practice clear, concise and precise communication while working through the material!
Throughout the course, each of you must volunteer at least once to serve as the facilitator, who will:
Make sure everyone has a chance for their voice to be heard. For example, saying:
“X, we haven’t heard from you in a while. Do you have thoughts on this problem or is there another one you’d like to shift to?”Keep track of time to cover as much of each problem as possible
Post a clearly articulated report with a summary and/or questions to the corresponding Ed Discussion category
Please be sure to also post your pod # and other team members, as in “Report for Pod 2 (Audrey St. John, Mary Lyon, …)”
If you’d prefer to use a doc, post the link or turn it into an image to attach
If you have work from the board, you can take a photo and post it
Pick one of these problems and search for "NP-complete" or "NP-hard" to get information on it.
When you choose the problem, write it on the board so we don't have duplicates.
Prepare to take 7 minutes to report back to the whole group on the problem. Your pod will need to:
Describe the problem (ideally with a "real-world" framing)
Proceed through the algorithm design process:
Step 0: Present examples and their solutions to gain intuition
Step 1: Formulate the problem precisely
Step 2: Propose an approach (brute force probably!)
Step 3: straightforward for a brute force approach
Step 4: analyze run time
Time-permitting: see if you can find a reduction between a pair of these problems!
NP-complete problems
Independent set
Battleship
Traveling salesperson
Sudoku
Art gallery
Graph coloring (vertex)
Pancake sorting
n-Queens
Crossword puzzle construction
Vertex cover
Maximum-sized clique
Latin squares
Set partition
Bin packing
Graph isomorphism