Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [complexity-theory]

This tag is for all questions of teaching complexity theory, a mathematical topic related to the inherent efficiency of algorithms and the problems they solve.

2
votes
2answers
57 views

How to explain ETH to undergraduate students?

I am a TA for complexity theory course. I want to explain the Exponential Time Hypothesis (ETH) to undergraduate students. They have done algorithm and theory of computation course. They know about ...
5
votes
3answers
166 views

Incorporating algorithmic complexity in grading

What are some advantages of incorporating algorithmic complexity in grading tests and assignments given to students? Currently, students in 11th grade at my school are required in tests to write ...
11
votes
7answers
355 views

Intuitive example of an NP problem

I was talking to a student today, and explaining that NP problems are hard to solve, but easy to verify. I used password encryption/decryption as an example, but he got stuck. He was unable to ...
3
votes
2answers
56 views

Presenting Mapping Reducibility (for P vs NP)

So, I am preparing to teach about P and NP for the first time. I know that I need to teach about Mapping Reducibility (aka One-to-One Reducibility). Can anyone recommend a set of algorithms that are ...