This page collects together all of the “readings” associated with individual modules.
In this site, readings represent “passive” learning opportunities, as opposed to experiences, which represent “active” learning opportunities. In many courses, readings and experiences together constitute the “assignments”.
Sections 12.1-12.4: Boolean functions, representing boolean functions, logic gates, minimization of circuits
Textbook 30 pages
Sections 13.1-13.5: Languages and grammars, finite-state machines, language recognition, Turing machines
Textbook 50 pages
Introduction to theory of computation, formal language theory, strings, languages, grammars, automata.
Deterministic finite automata, state transition diagrams, Moore and Mealy machines, nondeterministic finite automata, regular sets.
Sections 9.1-9.6: Relations and their properties, n-ary relations and their applications, representing relations, closures of relations, equivalence relations, partial orderings
Textbook 57 pages
Relations, binary relations and digraphs, classification, operations, applications to relational database theory.
Functions, representations, closures, equivalence relations and classes, quotient sets.
Section 10.1-10.8: Graphs, terminology, representations, connectivity, Euler and Hamilton paths, shortest paths, planar graphs, coloring
Textbook 94 pages
Directed graphs, undirected graphs, representation of graphs, classification of undirected graphs.
Sections 11.1-11.5: Trees, applications, traversal, spanning trees, minimum spanning trees
Textbook 58 pages
Applications, tree data structures, hierarchical structures, decision trees, game trees, Huffman trees.
Sections 5.3, 8.1, 8.2 (Recurrence systems), 8.3-8.6 (divide and conquer, inclusion-exclusion, generating functions), 5.4 (Algorithm design)
Textbook 50 pages
Recurrence systems, solutions of recurrence systems, classification of recurrence equations, uniqueness of solutions.
Principle of superposition; methods of: iteration, substitution, characteristic roots, undetermined coefficients. Higher-order recurrence systems.
Algorithm analysis by recurrence relations, divide-and-conquer and recursive algorithms, generating functions.
Screencast on inclusion-exclusion principle (Trevor)
Screencast 18 minutes TrevTutor
Sections 1.1, 1.6, 5.5: Program verification techniques, 5.5: Hoare’s axiomatic approach
Textbook 32 pages
Applications of predicate logic, program verification, program assertions, axioms and inference rules.