Introduction to Computer Science

• Prelude
• A word of welcome from the Greek chorus
• Lecture Notes, updates
• Lecture Notes, Week 01
  • The events leading to the oral exam
  • An Aristotelian approach
  • Background and general introduction
  • Exploring one’s computer with Emacs
  • Languages, meta-languages, and program processors
  • Where are we and where do we go from here?
  • Bootstrapping
  • Exercises for Week 01
  • Index of concepts for Week 01
• Lecture Notes, Week 02
  • Kleene’s S-m-n theorem
  • Computational paradigms
  • Finite description of arbitrarily large data
  • Syntax of regular expressions
  • Exercises for Week 02
  • Index of concepts for Week 02
• Lecture Notes, Week 03
  • Towards OCaml
  • OCaml: a language of algebraic expressions, with names and functions
  • Unit tests
  • Using Emacs to interact with the OCaml processor
  • Exercises for Week 03
  • Index of concepts for Week 03
• Lecture Notes, Week 04
  • On test coverage
  • Polymorphic types
  • OCaml: a language with lexical scope and stuff
  • Unit tests, revisited
  • The proof is trivial (variations on a theme)
  • Exercises for Week 04
  • Index of concepts for Week 04
• Lecture Notes, Week 05
  • Strings
  • Unparsing values and formatting strings
  • Unit tests, re-revisited
  • Where do we go from here?
  • Tracing function calls and returns
  • The factorial function
  • Induction and recursion over natural numbers
  • Polynomials revisited
  • Exercises for Week 05
  • Index of concepts for Week 05
• Lecture Notes, Week 06
  • So, induction and recursion over natural numbers
  • Functional abstraction and instantiations
  • Generic programming with natural numbers
  • From primitive iteration to primitive recursion for natural numbers
  • Mutual induction and recursion over natural numbers
  • The case of the Fibonacci numbers
  • Exercises for Week 06
  • Index of concepts for Week 06
• Lecture Notes, Week 07
  • On simplifying OCaml expressions
  • Inlining functions
  • From complete unit tests to implementation
  • Observational equivalence, functional equivalence
  • Weak polymorphism
  • It doesn’t type
  • Exercises for Week 07
  • Index of concepts for Week 07
• Lecture Notes, Week 08
  • Polymorphic lists in OCaml
  • Polymorphic lists in OCaml, continued
  • The map function over polymorphic lists
  • Representing sets as lists
  • Programming with lists
  • Exercises for Week 08
  • Index of concepts for Week 08
• Lecture Notes, Week 09
  • Reversing lists
  • Programming using accumulators
  • Generic programming with lists
  • The Art of Computer Science
  • The polymorphic option type
  • Exercises for Week 09
  • Index of concepts for Week 09
• Lecture Notes, Week 10
  • Concrete data types
  • The proof is trivial (revisited)
  • Polymorphic binary trees in OCaml
  • The slash type error
  • Generic programming with binary trees
  • Exercises for Week 10
  • Index of concepts for Week 10
• Lecture Notes, Week 11
  • Evaluation order
  • Demand-driven computation
  • Lazy lists
  • Streams
  • Programming with streams
  • The samefringe problem
  • Demand-driven computation, revisited
  • Exercises for Week 11
  • Index of concepts for Week 11
• Lecture Notes, Week 12
  • From concrete data types to abstract data types
  • Environments
  • Queues
  • Modules in OCaml
  • From concrete data types to abstract data types, revisited
  • Environments, revisited
  • Queues, revisited
  • Unit tests using modules
  • Exercises for Week 12
  • Index of concepts for Week 12
• Lecture Notes, Week 13
  • Mutable data in OCaml
  • A musing about variables
  • Sequencing in OCaml
  • Exceptions in OCaml
  • Programming using exceptions
  • Imperative lists
  • Exercises for Week 13
  • Index of concepts for Week 13
• Food for thought to take home
  • Adages about the Practical OCaml Programmer
  • More Sayings about the Practical OCaml Programmer
• Mini projects
  • Mini-project: Functional abstraction and instantiations
  • Mini-project: The underlying determinism of OCaml
  • Mini-project: Cracking polynomial functions
  • Mini-project: Palindromes, string concatenation, and string reversal
  • Mini-project: The power of recursion
  • Mini-project: A simple variant of the knapsack problem
  • Mini-project: A study of right-to-left linked lists
  • Mini-project: Computing the width of a binary tree
  • Mini-project: Implementing a sieve
  • Mini-project: Depth-first and breadth-first traversals
  • Mini-project: Indexing data structures
  • Mini-project: Multiplying integers in a tree using an accumulator
  • Mini-project: Three program processors for arithmetic expressions
• Miscellanies
  • How to solve it
  • From the summatorial function to the summation operator
• Tools
  • GNU Emacs
  • Objective Caml
• Dramatis Personæ
  • In real life
  • Fictional characters
• Songbook
  • Cosine
  • ‘Crastination
  • String map down
• Syllabus
  • Syllabus of a sort
  • Food for thought
• Postlude