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.
10 questions
1
vote
2
answers
102
views
'just complexity' problems
I am teaching an algorithms class, and I'd like to show some problems just to 'motivate' big O notation and show why it matters. I do the usual sorts, and I show them a timed comparison.
I also show ...
- 391
1
vote
2
answers
140
views
Why do we want small-o and small-omega?
When analyzing asymptotic complexity of functions we have big-O, which is an upper bound. We also have big-Omega, which is a lower bound, and even though it might not seem very useful at first to have ...
2
votes
1
answer
285
views
Does anyone know of any reliable summary of the complexity of common data structure operations?
It seems that the most popular source on the internet on this topic is https://www.bigocheatsheet.com/:
Wikipedia and basically any other similar table I find on the internet copy this one.
There are ...
- 121
7
votes
4
answers
1k
views
Do you include coding assignments in an intro to complexity and computation course?
In an introductory course on complexity and computing, I am thinking about including some programming tasks.
I wonder what types of tasks I could give the students beyond "construct" a ...
- 171
0
votes
1
answer
93
views
Any materials on fractional/quotient languages?
In Hopcroft-Motwani-Ullman there are exercises on this topic. What is another good reference (textbook/website) for fractional/quotient regular languages, possibly with examples?
- 499
0
votes
0
answers
76
views
Computer Science Theory with Haskell?
Do you know of any courses using Haskell to illustrate Computational Theory topics?
- 499
2
votes
2
answers
155
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 ...
- 121
5
votes
3
answers
267
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 ...
- 6,322
11
votes
7
answers
579
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 ...
- 35.3k
4
votes
2
answers
92
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 ...
- 35.3k