Notes for Lecture 1 - Friday September 3rd, 2004

• Return to the main StudentFrontPage.

• Scribe: Frances Haugen
• Editor: Mel Chua
• Editor:

Introduction to FOCS

• Lynn went over the syllabus, found here: EmergingSyllabus

The Three Themes of FOCS

1. What resources do I need?
   • Time resources. Will I have to compute until the end of time to get enough computing steps?
   • Can I guarantee an answer in X amount of time.
   • How much space do I need? Scratch space? Example: Integral tables are a trade off between computing time and space.
2. Can I solve it at all? Why can't I solve it?
3. What kind of language should I use?

Abstract Data Type

1. An abstract data type is like a contract. It is the signature of the program - the interface of what you can do with the language.
2. A collection could be an abstract data type (like a class). For example, the methods that you could use on/with it could be:
   • insert(thing, collection) - add an item to the collection
   • delete(thing, collection) - remove an item from the collection
   • member?(thing, collection) - Is the thing in the collection The programmer agrees with the language only to use methods provided by the implementer and the implementer is the only one who sees how the methods are written. === Example: Array ===
     • An array is like a series of boxes [][][][][] where you can put information into each box that you want. It is also known as a vector. Individual boxes cannot be removed, but the data inside them can be removed. Arrays are like mailboxes, if you remove a single box physically, the structure will fall apart. Arrays correspond to blocks of physical memory in the computer.
     === Example: List ===

     • a[][]-> b[][] Lists can point to different places. As a result, lists can be reordered easily. Lists must be stepped through sequentially.

3. If implemented perfectly, it shouldn't be possible to detect a difference between these two abstract data types. They do have different computational characteristics. One might take longer to processes or it might be more difficult to move things around within one vs. the other.

Formalisms

• === Regular Expressions ===
  • a*b will return b, ab, aab, aaab but not abb
  === Grammars ===
  • Top level expressions like class or interface declarations.
  === Abstractions ===
  • At a certain point, what becomes the most important is picking the right programming language for the project. During this course, please program in Java, Python, or Scheme. Please talk to Lynn if you would like to use something else.

Lisp

1. Lisp is the oldest program language still in common use. Lisp was originally created as a mathematical abstraction, and was then turned into a programming language by a grad student.
2. Parentheses are very important in lisp.
3. To add 3 + 4: (+ 3 4). + is the operator acting on 3 and 4. In other words, Lisp uses prefix notation.
4. Lambda is the lisp procedure that creates procedures. It, too, is very important.
5. In lisp, if it ain't false, it's true. Everything that doesn't explicity evaluate to a bool of #f evaluates to #t. === Example: Defining plus ===

   •    (define +
          (lambda (a b)
           (-(- 0 a b))))
     

Homework

1. Learn Java/Python eventually (whichever you don't know)

2. Install and play with DrScheme (enough to write a factorial or fibonacci function)