Embedded Files
Activity
Activity
- Complexity CardLine
- Break into 3 games
- 2 teams/game
- 3-4 students/team
- Deal one deck of cards between the two teams
- Teams spend about 10-15 minutes discussing their card problems
- Game play begins!
- Teams take turns placing cards in order of difficulty
- Cards can tie (line them up vertically)
- Teams take turns placing cards in order of difficulty
- Use Trello to report back and decide on order as a class
- Break into 3 games
Concepts
Concepts
- Given a problem S, it belongs to the complexity class TIME(T(n)) if there exists a T(n) algorithm that solves it
- EmptyList ∈ TIME(1)
- Sort ∈ TIME( n log n)
- SUBSET-SUM ∈ TIME(2^n)
- TIME(1) ⊆ TIME( log n ) ⊆ TIME( n ) ⊆ TIME( n log n ) ⊆ TIME( n^2 ) ⊆ ... TIME( n^k ) ⊆ TIME( 2^n ) ...
- P = class of problems for which a polynomial time algorithm exists
- NP = class of problems that are verifiable in polynomial time
Report abuse