Introduction to Computer Science

• Lecture Notes for Intro to CS, updates
• The events leading to the term project
  • Digital signatures
  • Version
• Lecture Notes, Week 01
  • Brief reminder of Aristotle’s four causes
  • Background and general introduction
  • Exploring one’s computer with Emacs
  • Languages and language processors
  • Where are we and where do we go from here?
  • Bootstrapping
  • Exercises 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
• 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
• 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
• Lecture Notes, Week 05
  • Strings
  • Unparsing values and formatting strings
  • Where do we go from here?
  • Tracing function calls and returns
  • The factorial function
  • Induction and recursion over natural numbers
  • Exercises for Week 05
• Lecture Notes, Week 06
  • 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
• Midterm Project
  • Midterm project
  • Mini-project: The underlying determinism of OCaml
  • Mini-project: Palindromes, string concatenation, and string reversal
  • Mini-project: Cracking polynomial functions
• Lecture Notes, Week 07
  • On simplifying OCaml expressions
  • Inlining functions
  • From complete unit tests to implementation
  • Unit tests for real
  • Exercises 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
  • Exercises 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
• Lecture Notes, Week 10
  • Concrete data types
  • The proof is trivial (revisited)
  • Polymorphic binary trees in OCaml
  • Generic programming with binary trees
  • Exercises 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
• Lecture Notes, Week 12
  • Mutable data in OCaml
  • Sequencing in OCaml
  • Exceptions in OCaml
  • Programming using exceptions
  • Imperative lists
  • Exercises for Week 12
• Lecture Notes, Week 13
  • 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 13
• Lecture Notes, Week 14
  • Weak polymorphism
  • It doesn’t type
  • The slash type error
  • Take-home Chinese food for thought
  • A musing about variables
• Term Project
  • Term project
  • Mini-project about multiplying integers in a tree using an accumulator
  • Mini-project about indexing data structures
  • Mini-project about depth-first and breadth-first traversals
  • Optional mini-project about computing the width of a binary tree
  • Optional mini-project about implementing a sieve
  • Optional mini-project about a simple variant of the knapsack problem
  • Optional mini-project about three language processors for arithmetic expressions
• Tools
  • Objective Caml
  • GNU Emacs
• Dramatis Personæ
  • In real life
  • Fictional characters
• Songbook
  • Cosine
  • ‘Crastination
  • String map down