gregbo (gregbo) wrote,

  • Mood:
I'm a bit pressed for time, so this post will cover two semi-related topics.

Dick Lipton, a CS theory prof at Georgia Tech, discusses his graduate complexity theory requirements. He is moving away from the problem solving aspects of the subjects, and insisting that his students better understand the definitions, axioms, key theorems, etc. of complexity theory. I don't think he is expecting them to memorize all of them – hopefully, he is trying to get them to understand how to use them to prove or derive other results. I think I would have benefited from this type of approach.

Former Googler Niniane Wang would like there to be games that teach computer science concepts such as regular expressions (regexes) and shortest-path algorithms. In one such game, you'd be given regexes and be asked to supply strings that the regexes accept. What is taught in complexity theory (and how it's taught) can differ quite a bit, but I'm not so sure this type of game could develop intuition for the types of problems I saw when I took the classes, such as:

  • when given a description of a regular language, having to supply a finite automaton (FA) recognizing it or regular grammar generating it
  • understanding the closure properties of FA
  • understanding the equivalence of deterministic and nondeterministic FA
  • understanding why a language is not regular
Tags: education

  • young adults struggle to find employment in Europe

    I happened upon a WSJ article describing how the recession has made it difficult for young adults in Europe to find work. The article also notes…

  • algorhythms

    Another theorist for your perusal, Jeff Erickson, Associate Professor of CS at UIUC. He teaches graduate and undergraduate algorithms courses. (His…

  • inside the Physics GRE

    Via Aurelie's blog, I found a post I found very interesting that dissects the Physics GRE. The post and the comments cover several issues that I…

  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.