Modules Topics covered in this class.

This page presents the “modules”, or the topics that are covered in this course.

Click on the tile associated with a module to go to a page containing that module’s contents.

1. Boolean Algebra

Boolean functions, logic gates and logic circuits, minimization of circuits, application to logic design.

2. Models of computation

Formal languages and grammars, finite state machines, automata, Turing machines, application to compilers.

3. Linear algebra and matrices

Matrices, determinants, systems of linear equations, application to computer graphics

4. Relations

Binary relations, n-ary relations, closures of relations, equivalence relations, partial ordering, application to relational databases.

5. Graphs

Directed and undirected graphs, representations, classification, isomorphism, connectivity, Euler and Hamilton paths, shortest paths, planarity, coloring, application to computer networks.

6. Trees

Trees, tree traversal, spanning trees, minimum spanning trees, Huffman encoding, Prim’s and Kruskal’s algorithms, applications to network routing.

7. Advanced counting techniques

Recurrence, generating functions, inclusion-exclusion principle, divide-and-conquer, application to algorithm design.

8. Verification

Program verification techniques, Hoare’s axiomatic approach.