1. Review Sites
  2. Home
  3. Readings

Readings and other resources in module order

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”.

Module: Boolean Algebra

Rosen Ch. 12 - Boolean Algebra

Sections 12.1-12.4: Boolean functions, representing boolean functions, logic gates, minimization of circuits

Textbook 30 pages

Boolean algebra, Part 1

Abstract algebra, boolean algebra, normal forms

Lecture notes

Boolean algebra, Part 2

Logic circuits, logic gates, half-adder, full-adder

Lecture notes

Boolean algebra, Part 3

Minimization of logic circuits, Karnaugh maps, Quine-McClusky method, logic circuit design

Lecture notes

Module: Models of computation

Rosen Ch. 13 - Modeling computation

Sections 13.1-13.5: Languages and grammars, finite-state machines, language recognition, Turing machines

Textbook 50 pages

Formal languages, grammars, and automata, part 1

Introduction to theory of computation, formal language theory, strings, languages, grammars, automata.

Lecture notes

Formal languages, grammars, and automata, part 2

Deterministic finite automata, state transition diagrams, Moore and Mealy machines, nondeterministic finite automata, regular sets.

Lecture notes

Formal languages, grammars, and automata, part 3

Regular sets revisited, regular expressions.

Lecture notes

Formal languages, grammars, and automata, part 4

Turing machines, restricted types of automata.

Lecture notes

Formal languages, grammars, and automata, part 5

Chomsky hierarchy, models of computation, computational complexity theory.

Lecture notes

Module: Linear algebra and matrices

Rosen Ch. 2 - Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

Section 2.6: Matrices

Textbook 8 pages

Linear algebra

Introduction, applications, systems of linear equations, Cramer’s Rule.

Lecture notes

Module: Relations

Rosen Ch. 9 - Relations

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, part 1

Relations, binary relations and digraphs, classification, operations, applications to relational database theory.

Lecture notes

Relations, part 2

Functions, representations, closures, equivalence relations and classes, quotient sets.

Lecture notes

Relations, part 3

Order relations, topological sorting

Lecture notes

Relational databases

Relational data model, terminology, relational algebra, tuple relational calculus, introduction to SQL

Lecture notes

Module: Graphs

Rosen Ch. 10 - Graphs

Section 10.1-10.8: Graphs, terminology, representations, connectivity, Euler and Hamilton paths, shortest paths, planar graphs, coloring

Textbook 94 pages

Graphs, part 1

Directed graphs, undirected graphs, representation of graphs, classification of undirected graphs.

Lecture notes

Graphs, part 2

Graph traversal: DFS and BFS, connectivity, graph isomorphism.

Lecture notes

Graphs, part 3

Euler paths, Hamilton paths, planarity, coloring, miscellaneous terminology.

Lecture notes

Graphs, part 4

Shortest paths, a key idea of Dijkstra’s algorithm: the greedy method, a key idea of Floyd’s Algorithm: dynamic programming.

Lecture notes

Module: Trees

Rosen Ch. 11 - Trees

Sections 11.1-11.5: Trees, applications, traversal, spanning trees, minimum spanning trees

Textbook 58 pages

Trees, part 1

Trees, rooted trees.

Lecture notes

Trees, part 2

Applications, tree data structures, hierarchical structures, decision trees, game trees, Huffman trees.

Lecture notes

Trees, part 3

Tree traversals, notations of expressions

Lecture notes

Trees, part 4

Spanning trees, DFS Trees, BFS Trees, minimum spanning trees, Kruskal’s algorithm, Prim’s algorithm.

Lecture notes

Module: Advanced counting techniques

Rosen Ch. 5 (Induction and Recursion) and 8 (Advanced counting techniques)

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

Advanced counting, part 1

Recurrence systems, solutions of recurrence systems, classification of recurrence equations, uniqueness of solutions.

Lecture notes

Advanced counting, part 2

Principle of superposition; methods of: iteration, substitution, characteristic roots, undetermined coefficients. Higher-order recurrence systems.

Lecture notes

Advanced counting, part 3

Generating functions, solving recurrence systems with generating functions, counting with generating functions.

Lecture notes

Advanced counting, part 4

Inclusion-exclusion principle, derangements.

Lecture notes

Algorithm analysis

Algorithm analysis by recurrence relations, divide-and-conquer and recursive algorithms, generating functions.

Lecture notes

Inclusion exclusion principle

Screencast on inclusion-exclusion principle (Trevor)

Screencast 18 minutes TrevTutor

Inclusion exclusion practice

Screencast on inclusion-exclusion problems (Trevor)

Screencast 28 minutes TrevTutor

Module: Verification

Rosen Ch. 1 (Logic and Proofs) and 5 (Induction and Recursion)

Sections 1.1, 1.6, 5.5: Program verification techniques, 5.5: Hoare’s axiomatic approach

Textbook 32 pages

Program verification, part 1

Applications of predicate logic, program verification, program assertions, axioms and inference rules.

Lecture notes

Program verification, part 2

Examples of verification of straightline programs, verification of sequential programs with loops

Lecture notes