# Tag Info

### 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 ...
• 948

### 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

### 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

### 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,102

### 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

### 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: ...
• 33.7k

### 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

### 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 ...
• 36.4k
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

### 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 ...
• 36.4k

### 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 ...

### 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

### 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,493
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,493
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 ...
• 36.4k
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 ...
• 36.4k
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 ...
• 36.4k
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, ...

Only top scored, non community-wiki answers of a minimum length are eligible