Class Notes: Applied Discrete Structures

Spring Semester 1999 - MWF 5th Period CSE/E222, Section 4617X

Instructor: M.S. Schmalz -- TAs: James Jeffers, Yasmeen Fatimah, Jang-Uk In, Jing Zhao

Housekeeping Details

Course Material

  1. Introductory Material: Logic, Sets, Functions, Complexity
      1.1. Introduction and Overview
      1.2. Basic Concepts of Logic
      1.3. Sets, Set Operations, Mappings, and Functions
      1.4. Algorithms and Algorithmic Complexity
      1.5. Integers, Matrices, and Number Theory

  2. Proof Construction -- Techniques and Pitfalls
      2.1. Methods of Proof
      2.2. Algebraic Derivation and Constructive Proof
      2.3. Mathematical Induction
      2.4. Recursion and Recursive Algorithms
      2.5. Program Correctness

  3. Counting, Permutations, & Relations
      3.1. Counting and the Pigeonhole Principle
      3.2. Elements of Probability Theory
      3.3. Permutations and Combinations
      3.4. Relations and Recurrence Relations
      3.5. Divide-and-Conquer
      3.6. Inclusion-Exclusion

  4. Graphs and Trees
      4.1. Mathematics of Graphs and Trees
      4.2. Graph Connectivity and Path Problems
      4.3. Planar Graphs and Graph/Map Coloring
      4.4. Trees, Tree Traversal, and Sorting
      4.5. Spanning Trees and MSTs

  5. Boolean Algebra and Finite-State Machines
      5.1. Boolean Functions
      5.2. Logic Gates and Minimization of Circuits
      5.3. Languages and Grammars
      5.4. Finite-State Automata and Applications

    6. Bibliography

    This Web page and all subordinate pages
    Copyright © 1998,1999 by Mark S. Schmalz
    All rights reserved, except printing by UF/CISE faculty
    or UF students officially registered for this class.