Comp 200 Project Ideas

The class project is intended to be your chance to choose a particular topic that interests you, and do further thinking, reading, or programming on that topic. A project can be (1) a technical or algorithmic description and/or analysis (5-10 pages), (2) a program, or (3) a solution to a problem or multiple problems from the course text or supplemental reading sources (a well-written solution to a challenging problem). If you have some other notion you want to try, ask me about it; I am open to alternatives as long as they incorporate structural thinking about anything related to computation.

Unlike other classes, in which a paper/project is often meant to be a broad overview, in this group III class I'm looking for something more focused. A program or problem-solution is already well-defined enough. If you choose the description/analysis option, your topic should be fairly narrow, one which precisely discusses a computational problem, solution, or process. For instance, if you do an analysis of DNA computing, I'm not looking for a broad "Here are many different schemes people have proposed . . . ", but rather "Here is one particular proposed scheme, and though I didn't actually carry it out in a bio lab, I've thought about it closely, probably could carry it out (with some help and resources) if I really put my mind to it. Here are the real-world problems I'd expect to run into, along with estimates of how much DNA I might need to use, and reasons why it would or would not work well in practice, and ideas on just how to overcome any weaknesses."

What I absolutely don't want is a standard factual history report or paper. Examples: Bad: "The Abacus was first used in 500 BCE . . ." Good: "Here is a description of the abacus addition and subtraction algorithm . . . " Bad: "Charles Babbage was born in 1791 . . . " Good: "This is how Babbage's difference engine actually worked . . ." In general, it's OK to include factual information, but the core should be a detailed technical analysis. Don't get too fluffy!

Below are some initial ideas for your project. For all of them, after thinking about which topic to try (doing a tiny amount of preliminary research), send me e-mail or drop by my office to talk about possible aspects to focus on.

• Data Encoding (not Encryption): Error-correctiong codes. When a receiving computer gets, for instance, a credit-card number that has been mis-typed, how can it (hope to) detect that there's been an error? What are the trade-offs involved? There are schemes can not only detect some transmission errors, but even correct them: what are algorithms for doing this? (You can search for "Hamming codes".)
• Data compression: How are text files compressed (".zip")? Are there limits on how much a file can be compressed? (Huffman coding; Zimpel-Lev compression; lossy vs lossless compression.) Why do image-compression algorithms tend to work differently from text-compression algorithms?
• Image compression: Describe in detail a couple of algorithms for compressing images. You can search for "run-length encoding". How are jpeg or gif images stored?
• Electronic money, or "e-cash": Can you combine electronic transactions with the anonymity provided with cash? In detail, how could such a scheme be implemented? What privacy issues are involved? Should there be regulated limits on the use of electronic money?
• AI: Neural Nets: What are some real-world problems that neural nets have been trained for? Describe how the inputs were encoded, and what learning rules were used. (There are many options here, such as recognizing faces, understanding speech, classifying airplanes, trying to predict earthquakes,....) What is "overtraining"?
• AI: Using DrScheme, write an interesting Eliza-like "talking" program, as discussed in class.
• A paper on various notions of "computation": Turing machines, Pebble (Abacus) machines, Random Access machines, as well as more varied ideas such as the lambda calculus or recursive functions. Include an equivalence between two of these: that is, show that any (say) turing machine program corresponds corresponds to some abacus machine, and vice versa. (That this can be done is the Church-Turing thesis.)
• AI: In The Emporer's New Mind, noted physicist Roger Penrose argues that computers fundamentally cannot achieve true intelligence. Alternately, Hofstadter's Metamagical Themas have several essays which do tend to side on the strong-AI side. Examine these books/essays, and rebuttals to them. What do you think? Give the best arguments you can for each side, rebuttals, and your honest opinion of how strong the arguments are.
• An analysis of early computing machines, and descriptions of exactly how (and how well) they worked. The exact details of one machine is more intersting than a vague overview of several early machines. [Note that it is difficult to get precise information on the internal mechanics of these machines, which is what would be desired.]
• Programming: Core Wars: (After we discuss the assembly language (Jelly2000), in class.) Consider two different programs, both in memory, where the computer alternately runs one step of each program. The goal is to make the other program stop -- by writing bogus instructions into (hopefully) the part of memory currently used by the opposing program. Of course, the other program is trying to do the same to you. Your assignment is to write two such programs in assembly language. (If more than one person chooses this project, you can play against each other.) Implementation details.

• Circuit design: We saw an adder-circuit in class. Write a circuit to multiply two binary numbers. This isn't too difficult, buildable out of AND, OR, NOT, and 1-bit-full-adders (the circuit we built in class, with inputs a,b,c_in, and outputs d, c_out). So do the multiplication circuit, but then modify it to also include one additional feature:

  Have the circuit multiply two *signed* four-bit numbers. That is, your numbers are anywhere from -15 to +15. The first question is, how can we easily represent the sign, with circuits? (We've already seen how to represent 0..15 with circuits.) And then, worry about how you'll calculate the sign of the resulting output.

• Circuit design: After doing hw06, design a memory system! A memory which contains 16 addresses (numbered 0..15), and each location stores a 3-bit binary number.

  The inputs would be, perhaps, the address lines (how many lines needed, to express any address 0..15?), some data-in wires (each datum being 3-bits), and two other wires do-load and do-store. The output would be wires which carry the result (datum) of a memory lookup.

  Also you'd include a write-up of what would needed to be changed, to make it a memory with 64Meg locations, each one being an 8-bit number.

  To finish off, create the CPU circuit which generates the signals do-load and do-store: That is, given the encoded Jelly2000 instruction (in binary), make sure that do-load is on iff the corresponding instruction needs to get a number from memory; similarly for do-store.

  See me for notation for repeated wiring, and other details.
  Not too hard!

• AI: What are genetic algorithms? Find a problem amenable to GAs (perhaps PacWar), and think about how you might represent the population in scheme. You write a breeding function (and, if not PacWar, a fitness function) and I'll write the surrounding code breed generations.
• Privacy: Beyond en/decrypting messages, what other privacy issues are being affected by computers? What vulnerabilities, if any, does having a computer with a web-browser expose you to? Are password-systems secure? What are alternatives?
• Fractals: How are fractals used in different areas (e.g. computer graphics)? What are Julia sets, and the Mandelbröt set?
• Computability: Read chapter 9 (Turing machines), and fill in the details of the proof that the problem of tiling the half-plane is undecidable. (pp 248-250).
• Reductions: Read Harel chapter 9 (Turing machines), and sketch the details of the proof that SATISFIABILITY is NP-complete. (This is similar to the previous problem.)
• reductions: In lecture, we reduced HamPath <= MonkeyPuzzle. I will give you the converse reduction, MonkeyPuzzle < HamPath, and you argue that indeed there is a solution to the corresponding HamPath if and only if there is a solution to the given MonkeyPuzzles problem. (See me for specific examples.)
  Alternately, you can do a reduction from TSP to HamPath, or perhaps another pair of problems (ask me for suggestions).
• Encryption. What are some other issues involved with public-key cryptosystems? For instance, you are at home, and want to send me an encrypted message, so you go to my web page to look up my public key. However, a nosy adversary might have a false web page that purports to be mine, but actually contains their public key, and any message you send me can be decrypted by the adversary. What are protocols that can minimize this type of attack?

• Encryption/programming. How, exactly, did the WWII Enigma machine work? Describe in enough detail so that you could actually build the machine out of coconuts, were you stuck on a desert island.

  Then, program it up: You could talk with me or Ian to brainstorm about how to approach this; each rotor might be a list-of-numbers; the whole machine would be a list-of-rotors. Then you'd write a few functions, like

    ; rotate-rotor: number, rotor --> (list number rotor)
    ; given a rotor, and a number of steps to rotate it,
    ; return both the new (shifted) rotor, and the rotor's current number.
  

  and

    ; encode-character: number, (list-of rotor) --> number, (list-of rotor)
    ; given a single keypress and a whole machine,
    ; return the output keypress plus the newly-spun machine.
  

  Or maybe you'd represent a rotor's information as an unchanging list plus an offset. Of course, we'd be representing characters as numbers; me or jacob could whip up a function to translate between numbers and letters if you like; that's trivial.

• Probability: For the Minesweeper game, argue that a first guess being in the middle is better, worse, or as good as guessing in the corner. What differences are there, if you are guaranteed the first guess won't be a bomb? This problem requires some mathematical sophistication in probability, to be able to make interesting and conclusive statements.
• Math with Infinities: Looking at infinite sets and trying to precisely formalize the relative size of infinite sets leads to some surprising results: some infinite sets are "bigger" than others! This, in turn, can be used to give an alternate proof that there must be some problems which we cannot write a program for. (In class we showed this by proving a particular problem -- the Halting problem -- unsolvable.) This is related to the diagonalization argument in chapter 8 (pp 210-211).
• Write a scheme function for a game in which you wander in a maze, looking for adventure. See the comp210. (This would take some extra work with me, for the particular programming background needed.)
• You can write programs to calculate pi, in Scheme and/or Jelly2000, along with a 1-2 page write-up of your approach. Okay, Jelly2000 doesn't have fractions, so you can mutliply each term in the series by K (with perhaps K being 100,000 or so), and compute K*pi (or, an integer near K*pi). See hw06 for details.
• Grab any issue of Wired or Mondo 2000, and ask me if some idea therein is worth a project. These magazines (in my opinion) are full of slick, super-hyped, buzzword-laden essays eager to make sweeping changes to society. While the articles can sometimes be over-the-top, and are often as full of glitz as they are substance, they are often based on interesting ideas that merit discussion. They can lead to worthwhile reflection on our social structure, its weaknesses, and how technology might improve (or worsen) it. Retain a healthy sense of criticism, and these magazines are excellent sources of ideas.

  General advice on the paper: i'm looking for your honest thought-out opinion and reasoning. I always find it less convincing to hear "X is totally correct has no drawbacks whatsoever" than to hear "X is pretty good, especially with respect to such-and-such, though it has the following shortcomings.." (Though of course, if you decide the former *is* true, then no prob -- just convince me!)

Finally, here are some other web pages that might spark some ideas:

various AI demos

Digital Culture - 98.01

Moore's Law

Chaos in the Classroom

references on fractals

The Koch Snowflake

Self-similarity

CNET Features - Digital Life - Bugs

CyberSpace Law Lessons

Cyberspace Law Institute

TR: April '97: Dertouzos

Archive of Sample Articles by Subject

Copyright Law / Copyright Law in Cyberspace (The Cyberlaw Encyclopedia)

Games that inte rest John Conway

Mathematical Games, Toys, and Puzzles

POP Mathematics

Mathematical Quotation Server

PI

The Oracle of Bacon at Virginia

Other misc references:

• design as info tech
• encryption & free speech ruling
• the RISKs newsgroup (archives) (find a file with a recent date)