CSC250 - Foundations of Computer Science Applications

Under construction

• ********Taken?**** Julia?******Lisp expression that proves the unsolvability of the halting problem
• Busy Beaver Turing Machine Problem - uncomputable!
  
  • Short description with hardware TM video
  • Longer description with nice figures
  • Wikipedia more formal description
• *****************Taken**(Valerie)************Phrase structure grammars - definition and example, and Chomsky Hierarchy, from textbook pages 566-573.
• Turing completeness and Turing tarpits
  1. Turing Completeness what is it? How does it relate to regular expresions?
  2. What is a Turing tarpit?
• Relating Probabilistic Grammars and Automata
• Grammar rules for Ruby in BNF context free form
  Grammar for Ruby
  You can install Ruby on your own machine (http://www.ruby-lang.org/en/downloads/)
  or try the html-embedded ruby interpreter to demonstrate Ruby in your presentation:
  http://tryruby.org/. There are also tutorials on this site.
• CFG for theorem generation
• ***********Taken******(Jessica)********ContextFree.js & Algorithm Ink: Making Art with Javascript context-free art is its basis: John Edgar Park
• Javascript Turing Machines
  1. javascript Turing machine, one implemented and you can program it.
     and the jsturing.js the javascript source code
  2. Another javascript Turing machine, three examples
     and tmversion3.js the javascipt source code.
• Parsing expression grammars (PEGS)
• Parsing in a Compiler using CFG for the programming language, with the CFG in the correct form.
  
  • Recursive Descent Parsing using left factoring algorithms on grammars - tutorial by F. Forbes, Univ of Kentucky
  • wiki on compilers
• 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***********(Sharon and Valeria)*****Computing with DNA by Leonard Adleman; Scientific American; August 1998; 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).
• Molecular Query Language which is a context-free grammar for substructure matching
• *************Taken****(Kristina)******* The Stochastic Revolution in Art and Science by Graham Coulter-Smith
• Sketch of the Analytical Engine with Ada Augusta, Countess of Lovelace notes
  
• ************Taken Maria (Laura)**********Generating Rock Guitar Solos with a Context-Free Grammar
• **************Taken Gavi and Naomi**********RA context-free grammar for the foxtrot
• 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.
• Recognizing Multitasked Activities Using Stochastic Context-Free Grammars (Black Jack domain)
• 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.
• Chapter 23 of Cohen textbook: Turing Machine Languages.
• Chapter 24 of Cohen textbook: the Chomsky Hierarchy.
• Chapter 25 of Cohen textbook: Computers.
• **********Taken*******(Leah B-W)********* For the mathematically brave - Quantum Computing grammars
  • Quantum Automata and Quantum Grammars by Moore and Crutchfield
    Click here for paper
    Other papers
    • Quantum Computing Tutorial
    • Quantum Computing for Computer Scientists (ACM article)
• G-pictures: Elements of a Probabilistic Pictorial Grammar (rules are in picture form. Terminals and Nonterminals are embedded in the picture.) Studies of Mondrian.
• *************Taken**************(Erika)*****
  lojban, a constructed, standardized, human language 40 years old.
  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?

Schedule

• Wed April 24
  1. Stochastic Revolution Kristina
• Fri April 26
  1. Computing with DNA Sharon and Valeria
  2. Leah
• Mon April 29
  1. Erika
  2. Naomi and Gavi
  3. Valerie
• Wed May 1
  1. Maria (Laura)
  2. Julia
  3. Jessica