Topics we hope to cover

Definitely subject to change.

See also Topics2Textbooks for how these map to readings.

2 weeks on algorithms:

• abstract data types
• simple collection types (array, linked list); insert, delete, member?

• searching & the benefits of ordering

• sorting
• binary tree, recurrence relations

• self-balancing hacks (trees)

• hashtable magic
• implement various algorithms
• timing exercises; theoretical vs. real bounds; constant factors

2? weeks on LISP

• intro scheme S-expr
• special form
• lambda/first order procedure
• recursion
• tail recursion
• cons/car/cdr
• cdr down list/cons up an answer
• functional programming beyond lisp

  • FHP page on ML

1 week on finite state machines/regular expressions

• See FiniteStateWeek

  • intro RE languages (and formal languages generally)
  • intro FSMs
  • build mini-parser
  • pumping lemma

    • Wikipedia on FSMs -- too short by itself, but combined with articles on DFAs, NDFAs, etc. and REs, etc., a reasonable if succinct summary. Includes, e.g., a proof of the Pumping Lemma

    • http://www.cs.uwaterloo.ca/High_School_Liaison/girls/june2002/resources/fsm.pdf Very brief intro w/pointers to JFLAP

    • ""Look up JFLAP!! (when the web is cooperating)""

1 week on context free grammars/stack (push-down) machines

• improve language to CFG
• improve automaton to PDA
• pragmatics

? on interpreter

? Prolog/constraint programming (Guide to Prolog) (Prolog Programming: A First Course)

• propositional logic, truth tables
• paradoxes and puzzles

1 week on NP-completeness

• formal framework
• classic problems
• intro SAT, propositional logic

1 week on computability/decidability

• Turing machine
• diagonalization/halting
• first order predicate calculus

• Godel/incompleteness -- this is really cool. kmr

• ?Knowledge representation

Information retrieval and TFIDF

• Overview

Clustering and machine learning

ProgrammingLanguages

• gratuitously included for linkage purposes