Computer science is an interesting and beautiful field of study dating back to the early 1930s, long before personal computers existed. This class spotlights the coolest and most awe-inspiring developments in computer science such as Turing machines, the Lambda Calculus, automata, higher-order functions, continuations, object-oriented programming, functional programming, logic programming, artificial intelligence, and Web applications.
This course is taught as part of MIT's Educational Studies Program during the High School Studies Program.
| Name | Email address | URL |
|---|---|---|
| Mike Burns | netgeek@speakeasy.net | http://netgeek.ws |
| Mike MacHenry | dskippy@ccs.neu.edu | http://www.ccs.neu.edu/home/dskippy |
http://netgeek.ws/teaching/wcacs/
Saturday 1:00 PM to 3:30 PM.
3-343 (Build 3, Room 343)
Homework should be submitted via email to wcacs@goreliance.com by 5:00 PM on Thursday; an email response of corrections will be given back by 5PM on Friday. Sample solutions will be made available on the course Web site.
For homework that is tricky to submit via email (state diagrams, for example) try these ideas: create an image using e.g. The GIMP, Sodipodi, xv, or MS Paint, saved as a JPEG, PNG, SVG, BMP, or TIFF, and attached to the email; or draw the assignment on paper and take a picture with a digital camera or scan it or fax it to your computer, then attach it to your email; or, use ASCII art in your email; or, use some other creative way to express the homework's answer to us via email.
What is a language and why do we care?
This lecture will show what a language is in the formal sense and explain what syntax is. Finite state machines will be introduced and used as a means of recognizing languages. Grammars will be explained and it will be shown how grammars and finite state machines compare.
What is the simplest machine that can solve any mathematical computation?
This lecture explains the motivations for Turing machines and what they are. Students will learn how to construct Turing machines to solve arbitrary computation. It will be explained what it means to be "Turing complete". The Halting Problem and NP-Completeness will also be discussed.
What is the simplest programming language that can express any mathematical computation?
The Lambda Calculus syntax and semantics will be explained in detail. It will be shown how the Lambda Calculus can represent numbers, Booleans, lists, and pairs. Simple programs for adding numbers will be shown and combined to write more complicated programs.
How does language affect programming? Which language constructs make it easier to write readable code? Which language constructs make it easier to write unreadable code?
Functional programming will be explained and it will be shown what the advantages and disadvantages are over imperative programming. Functional language constructs and style such as higher-order functions and recursion will be explained and concrete examples will be given.
What can be accomplished with a control construct that operates on the state on an interpreter?
It is explained what a continuation is and why they are so powerful. In-class examples will show how continuations can be used to implement other language constructions as well as how they can be used to optimize code in a controlled, readable, and reasonable manner.
How can we write Web applications in a more natural style than typical Web development? How can we transform existing code to run on the Web?
The PLT-Scheme Web server is explained and it is shown how it differs from typical Web programming infrastructions. It will be shown how using continuations to model Web interactions gives programmers the ability to write more natural, readable code. In-class examples will show how programs written for the PLT-Scheme Web server are easier to read and write and it is how these programs can be easily adapted to run on both the command-line and Web.
How can we make programs easier to write, more readable, and easier to maintain with data definitions? How can we use these data definitions to catch errors before they occur?
Haskell- and ML-style types are introduced, along with their powerful pattern-matching constructs. It is shown how data definitions map to function templates and how these data definitions enable easy, formulaic construction of programs if designed first. Type systems as a means of error detection and formal, light-weight proof systems are discussed.
How can one encapsulate data definitions and operations that act on that data? How can we reuse code yet modify certain pieces?
Object-oriented design is explained and related to functional data definitions. Advanced object-oriented constructs such as mixins are shown. In-class examples show how mixins make code apadtable. The Smalltalk programming language is introduced and its interesting semantics are described.
The Prolog programming language is explained in detail showing many small examples and describing syntax and semantics. Prolog is used to illustrate logic programming and Prolog features such as cuts, backtracking, and unification, which are explained.
Can machines think?
- A. Turing
The broad field of Artificial Intelligence is covered briefly for breadth and in certain areas for depth in this lecture. Two major ares of artificial intelligence, game AI and theorm proving, are detailed. A large game AI is code-walked and theorm provers are shown.