Re: Ideas for course on great ideas in (theoretical) CS?

From: Tim Smith (reply_in_group_at_mouse-potato.com)
Date: 02/21/04

  • Next message: Imam Tashdid ul Alam: "Re: Ideas for course on great ideas in (theoretical) CS?" 
    Date: Sat, 21 Feb 2004 11:32:26 GMT

    In article <e6b6bda9.0402201648.65c1acb2@posting.google.com>, Chip Klostermeyer wrote:
    > and may use that as a guide for some of the course. Examples
    > of some things I might discuss (besides a couple weeks on
    > basics/definitions/history) include Towers of Hanoi, Byzantine
    > Generals, voting problems, maybe a gentle discussion
    > of interactive proofs, prisoner's dilemma, game of life, primality
    > testing, graph coloring ... anything that can be discussed in a
    > day or so to folks with no CS background, yet which has some
    > theory component to it ... stuff that is surprising or counter-intuitive
    > is all the better ;)
    > Anyway, if anyone has any suggestions for material/topics
    > that I might cover, I would most appreciate it. Any pointers

    Zero-knowledge non-interactive proofs could be good. There was an article
    in "FOCUS" about 12 years or so ago that I recall that claimed the
    following, if I recall correctly:

        Given any theorem and a proof of that theorem, it is possible to
        construct a graph with a Hamiltonian circuit, and where given the graph
        and a Hamiltonian circuit, the proof can be reconstructed, and someone
        who does not know the proof can verify that the graph has this property,
        without gaining any information about the proof itself.

    (Someone jump in here, please, and correct any mistakes in the above. I
    defintely recall the parts below, but I'm fuzzy on the above. In
    particular, is the graph constructed from the theorem and the proof, or can
    the graph be constructed without knowing a proof of the theorem? I.e., for
    every theorem, does there exist a graph that contains a Hamiltonian circuit
    if and only if the theorem is true?)

    One of the common examples given to show zero-knowledge proofs is the
    problem of proving that you know a Hamiltonian circuit on a graph.

    Combine those, and use a non-interactive proof, and you get the surprising
    result that if you have a theorem and a proof of it, it is possible to
    prove to others that you indeed have a correct proof, without giving them
    any information about that proof!

    Imagine how frustrating that would be if it were actually practical and
    someone did that for an important problem, like one of the Millenium
    problems. (I wonder...would they get the prize?)

    > to references to articles (e.g., from Scientific American) that
    > would be accessible to students would be great (I have a couple)
    > would be great.

    Take a look at "The New Turing Omnibus" by A. K. Dewdney. The book itself
    is probably too lightweight for your needs, but it will give you many topic
    ideas.

    For something different, how about sorting stacks of pancakes? Suppose
    you've got a stack of N pancakes, each a different size, and you'd like the
    stack sorted with bigger ones on the bottom, smaller on top (e.g., like a
    stack from the Towers of Hanoi). The only operation you have is to pick the
    topmost k pancakes (1 <= k <= n), and reverse them. So, if your stack is
    (from top to bottom) 1 5 3 2 4, and you flipped the top 4, you would have 2
    3 5 1 4. All the usual questions can be asked about this: average number of
    flips required, worst case, etc.

    Besides being an interesting problem, there is an interesting bit of trivia
    associated with it. It is the subject of the one and only scientific paper
    by Bill Gates:

        Gates, W. and Papadimitriou, C. "Bounds for Sorting by Prefix Reversal."
        Discrete Math. 27, 47-57, 1979

    This is why Bill Gates has an Erdos number (4). 

    -- 
--Tim Smith
  • Next message: Imam Tashdid ul Alam: "Re: Ideas for course on great ideas in (theoretical) CS?"

    Relevant Pages

    • Re: Whats the standard interface for a graph?
      ... have more or less standard interfaces. ... For example, for a stack, ... Simple navigation of a graph is ...
      (comp.object)
    • Re: Interpreted Basic control-flow analysis
      ... I've thought of is to avoid duplicating any (line number, control ... but I don't see how reaching definitions are ... the reaching sets in some kind of stack, ... First form the "conservative" control graph with Ends ...
      (comp.programming)
    • Graph DFS implementation (stack usage)
      ... pushed on to the stack then print out the order in which they are popped ... int visit(int v, struct ADJACENCY *G_adj) ... With this approach the order in which my graph should print out should ...
      (comp.lang.c)
    • Re: C++ sucks for games
      ... >> graph that can't live on the stack? ... but i can't imagine that it's never been done. ... Professional Software Developer, Amateur Quantum Mechanicist ...
      (comp.lang.lisp)
    • Re: Is this simple scheme secure?
      ... >>enough to comment on the case of more general secrets. ... > interesting problem" can be proved using ZKP. ... > Hamiltonian circuits on a graph. ... with the property that the existence of a Hamiltonian circuit on ...
      (sci.crypt)