Skip to main content
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 ...
Rushi's user avatar
  • 948
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 ...
Kim Nguyễn's user avatar
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 ...
MTSan's user avatar
  • 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 ...
Peter's user avatar
  • 9,102
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 <...
user4934's user avatar
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: ...
Ben I.'s user avatar
  • 33.7k
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 ...
Mike Zamansky's user avatar
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 ...
Buffy's user avatar
  • 36.4k
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 ...
xuq01's user avatar
  • 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 ...
Buffy's user avatar
  • 36.4k
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 ...
Panagiotis Grontas's user avatar
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 ...
Matthew W.'s user avatar
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 &...
Victor Eijkhout's user avatar
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 ...
Victor Eijkhout's user avatar
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 ...
Buffy's user avatar
  • 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 ...
sevensevens's user avatar
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 ...
Neelesh V's user avatar
  • 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 ...
Buffy's user avatar
  • 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 ...
Buffy's user avatar
  • 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,...
Samasambo's user avatar
  • 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, ...
Discrete lizard's user avatar

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