The tag has no wiki summary.

learn more… | top users | synonyms

5
votes
1answer
143 views

Interesting programs on small machines

I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1 ...
12
votes
4answers
4k views

Interesting results in TCS which are easily explainable to programmers without technical background

Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math. In order to show them the beauty of TCS, I'd ...
16
votes
4answers
360 views

Teaching high school TCS - existing programs

I was offered to teach a novel TCS high school program, which requires constructing a curriculum. I would very much like to hear opinions and suggestions regarding this. First, does anyone know of ...
10
votes
0answers
186 views

Illustrative Examples of Tarski's Fixed Point Theorems

I have come across many informal examples that provide a physical illustration for Brouwer's fixed point theorem (some due to Brouwer himself). A person walks from the bottom of a hill to the top. ...
6
votes
1answer
577 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
142 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 ...
17
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 ...
190
votes
10answers
85k 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
520 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 ...
15
votes
2answers
788 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
4k 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.
22
votes
14answers
7k 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
629 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 ...
35
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 ...
12
votes
6answers
985 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
265 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 ...
41
votes
9answers
13k 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
762 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 ...
19
votes
5answers
835 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'. ...
5
votes
4answers
424 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
539 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 ...
23
votes
9answers
2k 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
613 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
582 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 ...
33
votes
5answers
4k 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 ...