# Questions tagged [teaching]

The tag has no usage guidance.

35 questions
Filter by
Sorted by
Tagged with
572 views

### Examples of the value of proofs for algorithms

In teaching Intro. Algorithms to undergrads, one of the most difficult tasks is to motivate why they need to know how to prove things about algorithms. (For many students, at least in many US ...
143 views

### Mastery-based grading for Theory of Computation

I would be interested to learn of anyone's experience using mastery-based (or "mastery-level") grading in a Theory of Computation course. Usually this requires—at a minimum— a detailed ...
3k views

### Theoretical computer science self-study resources for programmers

I am a pretty proficient software engineer, but I don't know much theory. I want to learn more theory. Particular topics that I am interested in are: computational complexity, formal languages, and ...
1k views

I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get ...
667 views

### How would a theory of computation course that culminated in lambda-calculus as “the” model of computation, instead of Turing machines, look like?

Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics: Finite automata and regular languages Pushdown automata and context-free languages Turing ...
484 views

### Streaming algorithms suitable for undergrad course

I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course. Good choices should probably satisfy the following requirements: ...
100 views

### Talk for K-12 Students + General Audience Reference Request

I will be giving talks about general topics in CS, and want to hit on TCS as well. The talks will be given to K-12 schools, so not all of them will be seniors who may go to an undergraduate program at ...
155 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 ...
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 ...
543 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 ...
398 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. ...
643 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 ...
168 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 ...
7k 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 ...
96k 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 ...
652 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 ...
1k 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 ...
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.
24k 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 ...
916 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 ...
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 ...
1k 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 ...
283 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 ...
23k 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? ...
261 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 algorithms ...
825 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 ...
1k 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'. ...
454 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 ...
621 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 ...
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 ...
759 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 ...
838 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 don'...
3k 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 ...
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 >...