Introduction to Discrete Structures: Discrete v. Continuous in Mathematics.

Propositional Calculus, Biconditionals, Equivalence, Applications to Natural Language and System Specification.

Predicates and Quantifiers, Algorithms: Searching, Linear and Binary Search.

Sorting: Bubble Sort, Insertion Sort.

Algorithmic Efficiency: Big O Notation; Theorems and Examples

Big O for Combinations of Functions, Complexity of Algorithms: Linear and Binary Search, Miscellaneous Asymptotic Analysis Topics.

Counting: Product and Sum Rules, Counting Examples.

Pigeonhole Principle: Generalized Pigeonhole Principle.

Permutations and Combinations: Binomial Theorem and Identities, Pascal’s Identity, Pascal’s Triangle.

Number Theory: Divisibility, Division Algorithm, Modular Arithmetic, Modular Arithmetic and Congruences, Prime Numbers, Fundamental Theorem of Arithmetic, GCD, LCM.

Review of Number Theory, Algorithm for div and mod (Quotient and Remainder).

Euclid’s Algorithm for GCD, Review of Asymptotic Analysis.

Integer representations, Computing representations, Integer addition algorithm, Integer multiplication algorithm, Exponentiation, Exponentiation Algorithms.

Graph Theory Introduction, Types of Graphs.

Paths and Circuits: Euler Circuits and Paths, Graph Isomorphism.

Planar Graphs, K3, 3, Euler’s Formula.

Shortest Path Problems and Dijkstra’s Algorithm, Complexity, Hamiltonian Circuits, Traveling Salesman Problem

Trees: Definitions and basic properties, Applications of Trees: Searching, Binary Search Trees, Tree Traversal: Inorder, Preorder, Postorder, Applications to file systems, expressions.

Spanning Trees: Construction of spanning trees, Breadth First Search, Depth First Search, Minimum Spanning Trees