Title: P vs. NP Categorizing Grid
Author: Kate Deibel
Date: 03/10/28
Technique: Categorizing Grid
Before Class Preparation Time: LOW
Class Completion Time: LOW
In-Class Analysis Time: LOW
Out-Of-Class Analysis Time: LOW
Assessment Goals:
- Develop analytic skills
- Develop ability to draw reasonable inferences from observations
- Improve memory skills
- Develop appropriate study skills, strategies, and habits
- Learn terms and facts of this subject
- Learn concepts and theories of this subject
Topics:
- Complexity
- NP
- P
- Algorithms
Purpose:
This activity allows instructors to see students' knowledge regarding the elements within P and NP.
Activity:
This activity will give you the opportunity to decide whether an a computational problem is known to be in P (solvable in deterministic polynomial time) or NP (solvable in non-deterministic space).
|
Problems
|
- Finding a clique in a graph of size at least k
- 3-coloring a graph
- 4-coloring a graph
- Coloring a planar graph
- Determining if an integer is prime
- Determining if an integer is composite
- Finding a max-flow in a network graph
- Finding a path shorter than length k from A to B in a graph
- Finding a path longerer than length k from A to B in a graph
- Determining if a logical expression is satisfiable
- Sorting a pre-ordered list
- Determing if a graph has an Euler cycle (crossing every edge once)
- Determing if a graph has a Hamiltonian cycle (touching every vertex once)
- Determine if two graphs are isomorphic
|
Solution:
The following are suggestions, but several of the items in this activity are meant to encourage discussion.
- NP: Finding a clique in a graph of size at least k
- P: 3-coloring a graph
- NP: 4-coloring a graph
- P: Coloring a planar graph
- P: Determining if an integer is prime
- P: Determining if an integer is composite
- P: Finding a max-flow in a network graph
- P: Finding a path shorter than length k from A to B in a graph
- P: Finding a path longer than length k from A to B in a graph
- NP: Determining if a logical expression is satisfiable
- P: Sorting a pre-ordered list
- P: Determing if a graph has an Euler cycle (crossing every edge once)
- NP: Determing if a graph has a Hamiltonian cycle (touching every vertex once)
- NP: Determine if two graphs are isomorphic
Instructor Responses:
- Lecture
- Next Day Summary
- Class Discussion
- Homework
Response Analysis:
Run through the grids and mark incorrect or missing entries. Identify the most common errors as well as any patterns that could explain student confusion. Reflect upon these errors and report them back to the class as you see fit.
Variant Uses of Activity:
- Have students work in groups to complete this activity. The instructor may want to circulate throughout the groups to ensure that each group is making progress. After the groups have completed their lists, the instructor can ask for votes on each item. It is important that the instructor explains why each data structure is appropriate for the task.
- Have students work individually on their lists and then form groups of 4-5 people to discuss their individual lists with other members of the group.
Device-Enabled: Has Been Enabled
Related Topics:
- Efficiency
- NP-Complete
- Decidability
- Analysis