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

  • Ciena interview

    I had an onsite interview at Ciena a couple of weeks ago for a Senior Systems Test position. Long story short — I didn't get the job. I think they…

  • ProtonMail test

    I took a test from 7-9am this morning from ProtonMail, a secure email provider based in Geneva, Switzerland, that has an office in SF. The test was…

  • IBM interview

    I had an interview loop yesterday at the IBM Silicon Valley Lab facility with several people from the Cloud Network Services group. Four engineers…

  • 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.