8
votes
Do you include coding assignments in an intro to complexity and computation course?
I'll use “TCS” — theoretical computer science — as the name of your course
Should an introductory TCS course have coding assignments?
Yes and no.
Since there are two parts to that let me start with ...
- 918
8
votes
Intuitive example of an NP problem
If your student has tried it once, you can use sudoku as an example (it does not work so well if the student has never heard of it).
Given a completed sudoku grid, write a program that verifies that ...
- 727
6
votes
Intuitive example of an NP problem
Map coloring is a very nice example.
It is NP to find if the graph is planar or not (you can reduce the map coloring if a graph is planar or not), but it is relatively easy to see if the colored map ...
- 297
5
votes
Intuitive example of an NP problem
Start with the humor of xkcd:
I used the above comic in a lecture on P vs. NP. The analogy I gave is eating at The Cheesecake Factory. Their menu boasts something like 250 dishes and 50 kinds of ...
- 9,082
5
votes
Intuitive example of an NP problem
The subset sum problem is one that is easy to understand - "given this set of numbers {provide a set of a dozen or so}, is there a subset of these numbers that sum up to 100?"
For example, the set <...
- 51
4
votes
Do you include coding assignments in an intro to complexity and computation course?
I don't give many assignments in my coursework on that material, but I have a few important ones. I have them implement NFA, DFA, and PDA in Scheme. The function headers look like so:
...
- 32.9k
4
votes
Incorporating algorithmic complexity in grading
I wouldn't want to penalize kids who are really relatively inexperienced for not coming up with the fastest solutions on a test. Even if they're in 11th grade and have a couple of years under their ...
- 1,572
3
votes
Why do we want small-o and small-omega?
Who is this "we" of which you speak? Note that Big-O and related concepts precedes the computational and algorithmic use. It is a concept of mathematics that is useful in analyzing the ...
- 36k
3
votes
Accepted
Presenting Mapping Reducibility (for P vs NP)
Considering that you teach HS students, many of the reduction examples "off the market" might be conceptually a bit too complex, and can be confusing even for many college students.
I'd suggest that ...
- 276
2
votes
Intuitive example of an NP problem
Complexity class NP_ is described here: https://en.wikipedia.org/wiki/NP_(complexity).
One of the easiest examples to explain is given there as: The decision ...
- 36k
2
votes
Intuitive example of an NP problem
Please note that all P problems are in NP too, since they are easy to solve and therefore also easy to verify.
Maybe you are asking for an NP-complete problem. In that case I think the sudoku ...
2
votes
How to explain ETH to undergraduate students?
It seems that you are aiming to convey the significance of disproving ETH? If you're looking to leave some impression, it's always better to show rather than tell.
I think your students need to see ...
- 303
2
votes
Do you include coding assignments in an intro to complexity and computation course?
I've never taught this sort of course, but I'd start at the bottom of the Chomsky hierarchy:
Program a finite state machine: coke vending machine.
Program a pushdown automaton: parking garage with &...
- 1,453
1
vote
Why do we want small-o and small-omega?
If you want to see if a number is prime naively you try all of its potential factors. A little more cleverness shows that sqrt(n) factors are enough.
One of the ...
- 1,453
1
vote
Does anyone know of any reliable summary of the complexity of common data structure operations?
I worry that you are asking for learning and insight without putting in the work that it requires. Having a "quick hit" explanation of some phenomenon doesn't mean that you actually ...
- 36k
1
vote
Do you include coding assignments in an intro to complexity and computation course?
Yes - things like sorts, regexes, and virtualization are great ways of explaining complexity and CS theory
Sorts are a great example.
YouTube video with sorts animated
Implementing them myself in one ...
- 111
1
vote
Any materials on fractional/quotient languages?
An Introduction to formal Languages and Automata
Included in the University of Nottingham's Languages and Computation Course resources
The book An Introduction to Formal Languages and Automata by ...
- 188
1
vote
How to explain ETH to undergraduate students?
I'm not sure I understand your dilemma, especially for the students you describe. Many computational problems can be shown to be "reducible" to others using a sub exponential (usually polynomial) run ...
- 36k
1
vote
Incorporating algorithmic complexity in grading
I recognize that this isn't exactly an answer to your question, but is a different way to think of the issue. I applaud the answer of Mike Zamansky given here already, but suggest an orthogonal ...
- 36k
1
vote
Intuitive example of an NP problem
First, note the difference between NP and NP-hard. NP simply means verifiable easily. NP-hard means verifiable easily, but also means that the problem is as hard to solve as the hardest problems in NP,...
- 121
1
vote
Presenting Mapping Reducibility (for P vs NP)
A fairly simple reduction goes from Hamiltonian Cycle to the Travelling Salesman Problem (TSP).
The Hamiltonian Cycle problem on instance $G$ asks whether there exists a tour of some unweighted, ...
- 415
Only top scored, non community-wiki answers of a minimum length are eligible