Introduction to Computer Science (YSC1212)

• YSC1212 Lecture Notes, updates
• YSC1212 Lecture Notes, Week 01
  • Background and general introduction
  • You and your digital identities
  • Exploring one’s computer with Emacs
  • Languages and language processors
  • Definitions
  • Exercises
• YSC1212 Lecture Notes, Week 02
  • Bootstrapping
  • On interpretive overheads
  • Computational paradigms
  • Finite description of arbitrarily large data
  • Syntax of regular expressions
  • Semantics of regular expressions
  • Exercises
• YSC1212 Lecture Notes, Week 03
  • Using emacs to interact with the OCaml processor
  • Towards OCaml
  • OCaml: a language of algebraic expressions, with names and functions
  • Unit tests
  • Exercises
• YSC1212 Lecture Notes, Week 04
  • Polymorphic types
  • OCaml: a language with lexical scope and stuff
  • Unit tests, revisited
  • The proof is trivial (variations on a theme)
  • Exercises
• YSC1212 Lecture Notes, Week 05
  • Strings
  • Unparsing values and formatting strings
  • Tracing function calls and returns
  • The factorial function
  • Induction and recursion over natural numbers
  • Exercises
• YSC1212 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
  • Exercises
• YSC1212 Midterm Project
  • Midterm project
  • Mini-project: The underlying determinism of OCaml
  • Mini-project: The case of the Fibonacci numbers
  • Mini-project: Palindromes, string concatenation, and string reversal
• YSC1212 Lecture Notes, Week 07
  • On simplifying OCaml expressions
  • Inlining functions
  • From complete unit tests to implementation
  • Unit tests for real
  • Exercises
• YSC1212 Lecture Notes, Week 08
  • Polymorphic lists in OCaml
  • Polymorphic lists in OCaml, continued
  • The map function over polymorphic lists
  • Representing sets as lists
  • Exercises
• YSC1212 Lecture Notes, Week 09
  • Reversing lists
  • Programming using accumulators
  • Generic programming with lists
  • The Art of Computer Science
  • Concrete data types
  • Polymorphic binary trees in OCaml
  • Generic programming with binary trees
  • Exercises
• YSC1212 Lecture Notes, Week 10
  • Evaluation order
  • Demand-driven computation
  • Lazy lists
  • Streams
  • Programming with streams
  • The samefringe problem
  • Demand-driven computation, revisited
  • Exercises
• YSC1212 Lecture Notes, Week 11
  • Mutable data in OCaml
  • Sequencing in OCaml
  • Exceptions in OCaml
  • Programming using exceptions
  • Imperative lists
  • Exercises
• YSC1212 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
• YSC1212 Lecture Notes, Week 13
  • Take-home Chinese food for thought
  • Exercises
• YSC1212 Term Project
  • Term project
  • Mini-project about multiplying integers in a tree using an accumulator
  • Mini-project about depth-first and breadth-first traversals
  • Mini-project about indexing data structures
  • Mini-project about implementing a sieve
  • Mini-project about a simple variant of the knapsack problem
  • Mini-project about computing the width of a binary tree
  • Mini-project about three language processors for arithmetic expressions
• Tools
  • Objective Caml
  • GNU Emacs
• Dramatis Personæ
  • In real life
  • Fictional characters