CSC250 - Foundations of Computer Science Applications

Under construction

• A discussion of Turing's Imitation GameKirkpatrick and Klingner
• Parsing in a Compiler using CFG for the programming language, with the CFG in the correct form.
• Recent Methods for RNA Modeling Using Stochastic Context-Free Grammars; (1994); Yasubumi Sakakibara, Michael Brown, Richard Hughey, I. Saira Mian, Kimmen Sjvlander, Rebecca C. Underwood, David Haussler; Proc. of the Asilomar Conference on Combinatorial Pattern Matching
• ******TAKEN*****(Mine)parter?  Computing with DNA by Leonard Adlerman; Scientific American; August 1998 (not on-line); method that has high probability of finding a solution to the Hamiltonian path problem using DNA
• Read Section 3.6.2 and 3.6.3 of Lewis and Papadimitriou textbook on Top-Down and Bottom-Up Parsing (of context-free grammars).
• *******TAKEN*****(Hannah and Aurelia) VRML Grammar Definition, and demo
  Find the grammar specification for VRML (Virtual Reality Modeling Langauge); Find some example code and show derivations for it from the language spec; download a VRML viewer ( FreeWRL)) and show the code examples (you can show some complex ones too, for fun).
  
  • Here is an article to find out more it as an ANSI standard
    
  • Here is a nice site with examples and tutorials
    
  • Click here to go to the official web page and find the specification
• *****TAKEN*****(Lauren) The Stochastic Revolution in Art and Scienceby Graham Coulter-Smith
• *******TAKEN********(Margaret and Christina)Sketch of the Analytical Engine with Ada Augusta, Countess of Lovelace notes
  as well as
  a mechanical description of the analytical engine.
• Stephanie, maybe a partner? Generating Rock Guitar Solos with a Context-Free Grammar
• Sarah - partner maybe??? A context-free grammar for the foxtrot
• Holly - Regular expressions in Perl - either use a textbook from 104 or 209, or do a web search. You'll have to know/learn a little Perl and then describe how it uses regular expressions for pattern matching. Show examples.
• *****TAKEN**** (Tessa) Light Parsing as Finite-State Filtering; using transducers (finite-state machines with output. Used for language processing used in information retrieval and information extraction.
• Download and demonstrate JFLAP. JFLAP is a package of graphical tools which can be used as an aid in learning the basic concepts of Formal Languages and Automata Theory.
• For the musically inclined, take a look at Bol Processor Grammars; grammars for Indian Tabla drumming.
  Articles:
  1998; Migrating Musical Concepts -- an Overview of the Bol Processor. Computer Music Journal, 22, 2, pp.56-64.
  And.... Sound samples, etc are here
• Write a turing machine program for an interesting problem.
• *****TAKEN***** (Rae and Amy)The Enigma Machine
  Paper 1
  Paper 2
  Enigma photos
• Chapter 23 of Cohen textbook: Turing Machine Languages.
• Chapter 24 of Cohen textbook: the Chomsky Hierarchy.
• Chapter 25 of Cohen textbook: Computers.
• ****TAKEN**** (Constance and Ngaire) For the mathematically brave - Quantum Computing grammars
  • Quantum Automata and Quantum Grammars by Moore and Crutchfield
• *****TAKEN***** (Justine and Diana)G-pictures: Elements of a Probabilistic Pictorial Grammar (rules are in picture form. Terminals and Nonterminals are embedded in the picture.) Studies of Mondrian.
• What is lojban.org's Annotated machine grammar?
• Redstart Systems Human-Machine Grammar What are the rules and words?
• What operations are performed on context-free grammars to ready them for use as language models for compilers?