imperative programming
Thoughts to come.
syllabus
part 1: programming with state
Basic imperative programming constructs: assignments, conditionals, procedures and loops. Comparison of imperative and functional programming. Examples.
Method of invariants: correctness rules for while loops; proof of termination. Examples including summing an array, slow and fast exponentiation. Examples: string comparison, printing numbers in decimal.
Unit testing; debugging. Binary search. Quicksort.
part 2: datatypes and data structures
Modularisation and abstract datatypes. Specification, interfaces and (some) implementation. Relevant classes from the API (HashSet, Map). Examples: spell-checking, dictionary and phone book.
Programming with abstract datatypes. Relevant classes from the API (List, Queue, Option). Example: the word path.
Implementing abstract datatypes: abstraction functions; datatype invariants; correctness conditions; encapsulation. Example: phone book.
Documentation and testing of objects and classes. Linked lists. Bit maps and hash tables. Binary trees. Priority queues.