The teaching tag has no wiki summary.
2
votes
1answer
224 views
Most important topics for a short introduction to Prolog
Suppose you were teaching an introductory course on logic as part of a TCS curriculum. Furthermore, suppose that you had one week (= two 90 minute lectures) to spare for introducing Prolog on the ...
3
votes
1answer
122 views
Teaching end-course material in a computational-models course
As TAs in an undergrad course on computational models, every year we are faced with a dilemma of what material to teach in the last few weeks of the course.
To be specific, our typical syllabus is ...
15
votes
4answers
2k views
Abstract algebra for Theoretical Computer Scientists
I have a reasonable undergrad math education but have never been 100% comfortable with abstract algebra (the mathematics of groups, rings, fields etc. ). I think this was partly as I needed to see ...
114
votes
10answers
35k views
What is the enlightenment I'm supposed to attain after studying finite automata?
I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we ...
20
votes
4answers
485 views
Language and automata textbook, free or low cost?
I'll be teaching a standard undergraduate class on languages and automata next semester, and would prefer to use a legitimate free or low-cost text. Any suggestions?
I love the Sipser text but the ...
12
votes
2answers
531 views
Notable examples of the square root idea in complexity analysis
There are a number of algorithms and data structures which exploit the idea that $\max \left\{k, n/k\right\}$ gets its minimum value at $k=\sqrt n$. Common examples include
baby-step giant-step ...
31
votes
11answers
3k views
Concepts in theoretical CS that would be approachable ages 8-14
Guessing it's unlikely a common question, but wondering if anyone has seen material that was clearly made to address this audience in a meaningful way.
15
votes
13answers
4k views
How practical is Automata Theory?
There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...
8
votes
4answers
384 views
Example problems with polynomial and exponential solutions, and tiny footprint?
I'm planning on running an “experiment” when teaching my algorithms class this fall, with one very old, limited computer (main limiting factor is probably memory—possibly as low as 16KB) and one ...
34
votes
6answers
4k views
Have you ever realized you can't solve the homework you assigned?
This question is targeted at people who assign problems: teachers, student assistants, tutors, etc.
This has happened to me a handful of times in my 12-year career as a professor: I hurriedly ...
10
votes
6answers
842 views
“Natural” decidable problems known not to be in NP.
Every time I teach NP-Completeness, students ask "are there any problems that are known to not belong to NP?"
How would you answer? I usually give them an undecidable problem as an example, but this ...
2
votes
3answers
258 views
Explaining input-size of integral arguments to undergraduate CS students
When I teach undergraduate algorithms, the students have no problem accepting that two n-bit numbers can be added in $O(n)$ time, or that modular exponentiation takes $O(n^3)$ time.
But when we get ...
31
votes
9answers
4k views
Explain P = NP problem to 10 year old
It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it?
...
1
vote
0answers
258 views
Large real-world graphs for teaching use? [duplicate]
Possible Duplicate:
graphs from real-life problems
I'm teaching Algorithms for the 7th time or so, and I want augment the class by asking the students to implement some of our thematic ...
3
votes
1answer
703 views
Website with TCS Fun Facts
This interesting paper http://www.math.hmc.edu/~su/papers.dir/leitzel.pdf is about how to motivate students during a course.
One of the idea is to add some "fun facts" during the course for some ...
18
votes
5answers
785 views
Problem teaching computability
I have difficulty teaching the concept of computable functions. I tried to develop the idea of why researchers like Hilbert/Ackermann/Godel/Turing/Church/... invented the notion of 'computability'. ...
6
votes
4answers
412 views
Natural notion for computational hardness
When I teach students concepts like intractable problems and efficient algorithms in discrete structures or data structures and algorithms, it is difficult for students to intuitively grasp somewhat ...
10
votes
2answers
517 views
Motivating Talk on Foundations of Cryptography
This question is in the same vein as inspirational talk for final year high school pupils. My Ph.D. advisor asked me to give an inspirational talk for new M.Sc. students. The subject is foundations of ...
19
votes
6answers
1k views
Great algorithms, machine learning and no linear algebra
I teach an advanced algorithms course and would like to include some topics related to machine learning which will be of interest to my students. As a result, I would like to hear people's opinions of ...
21
votes
6answers
570 views
Curriculum: Logical/Formal Methods in Security
At present I teach a small course (Four two hour lectures at the Masters level) on Logical Methods in Security, though the title Formal Methods in Security might be more apt. It covers briefly the ...
27
votes
1answer
485 views
Other applications of Karger-Stein branching amplification?
I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class. This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I ...
32
votes
13answers
2k views
Inspirational talk for final year high school pupils
I am often asked by my department to give talks to final year high school pupils about the more mathematical elements of computer science. I do my best to pick topics from TCS which might inspire ...
30
votes
5answers
3k views
Is the Chomsky-hierarchy outdated?
The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the ...
32
votes
8answers
2k views
Which definition of asymptotic growth-rate should we teach?
When we follow the standard textbooks, or tradition, most of us teach the following definition of big-Oh notation in the first few lectures of an algorithms class:
$$
f = O(g) \mbox{ iff } (\exists c ...
