New answers tagged

1

Yes - things like sorts, regexes, and virtualization are great ways of explaining complexity and CS theory Sorts are a great example. YouTube video with sorts animated Implementing them myself in one of my courses let me experience n*log(n) vs n^2. Students will see bubble sort taking much longer than quick-sort as the sample arrays get larger. So is regex. ...


7

I'll use “TCS” — theoretical computer science — as the name of your course Should an introductory TCS course have coding assignments? Yes and no. Since there are two parts to that let me start with the third — the And! Analogy: When Johnny will only have candy and momma insists that spinach is good for him the result can be a difficult impasse. Yeah we all ...


2

I've never taught this sort of course, but I'd start at the bottom of the Chomsky hierarchy: Program a finite state machine: coke vending machine. Program a pushdown automaton: parking garage with "is empty" indicator. Linear bounded automata (Did you delete my comment?) are always the hardest. I think primality testing would be an example here. ...


4

I don't give many assignments in my coursework on that material, but I have a few important ones. I have them implement NFA, DFA, and PDA in Scheme. The function headers look like so: (define (DFA input Sigma S s0 delta F) ...) (define (NFA input Sigma Q q0 Delta F) ...) (define (PDA input Sigma Gamma S s0 delta F) ...) I will say that these ...


Top 50 recent answers are included