CSCI 140

Discrete Structures

Coordinator: Nazli Hardy

Credits: 4.0

Description

Discrete mathematical structures and their application to computer science including formal mathematical notation and proofs, algorithms, computer related arithmetic, propositional logic, predicate logic, set theory, relations, functions, matrices and combinatorics.

Prerequisites

Placement in MATH 151 or higher.

Prerequisites by Topic

  1. Algebraic manipulations (factoring, polynomial manipulations).
  2. Plotting functions.
  3. Solving algebraic equations for the unknown.
  4. Exponents and Logarithms.

Sample Textbooks

Course Outcomes

The successful student will learn the fundamental notation and concepts of discrete structures, learn techniques for proving things about and manipulating structures, and have an appreciation of formal axiomatic systems.

Major Topics Covered

  1. Number systems
    1. Binary numbers
    2. Integers
    3. Floating point, rational, and real numbers
  2. Propositional Logic
    1. Propositions
    2. Truth tables
    3. Conjunction, disjunction, negation
    4. Conditionals, biconditionals, valid arguments, converse, contrapositive
    5. Axioms and rules of inference
    6. Applications
  3. Predicate Logic
    1. Quantified statements
    2. Operations on quantified statements
    3. Bound and free variables
    4. Axioms and rules of inference
    5. Boolean algebra
    6. Applications (e.g. logic programming with Prolog)
  4. Sets
    1. Sets and their operations
    2. Venn diagrams
    3. Proving facts about sets
    4. Countable sets
    5. Uncountable sets
    6. Counting principles
    7. Applications
  5. Relations
    1. Ordered pairs
    2. Cartesian products
    3. Representations of Relations
    4. Properties of Relations
    5. Equivalence Relations
    6. Congruences
    7. Modular arithmetic
    8. Applications (e.g. relational algebra and SQL)
  6. Functions
    1. Functions whose domains are numbers, strings, and sets
    2. Function composition
    3. Recursive functions
    4. Recurrence relations
    5. Applications (e.g. recursive functions in Prolog)
  7. Vectors and Matrices
    1. Definitions and properties
    2. Dot product
    3. Matrix multiplication and addition
    4. Inverse of a matrix
    5. Applications (e.g. systems of linear equations, graphics transformation matrices)
  8. Mathematical Induction
    1. Definitions
    2. Steps involved
    3. Applications
  9. Combinatorics
    1. Permutations and Combinations
    2. Binomial coefficients
    3. Principle of Inclusion and Exclusion
    4. Discrete Probability
  10. Graph Theory
    1. Notation
    2. Vocabulary
    3. Types (e.g. complete, bipartite, directed, weighted)
    4. Applications (e.g. finite state automata)

Sample Laboratory Projects

  1. Implementing recursive functions in Prolog
  2. Implementing recurrence relations in Prolog
  3. Learning SQL using Ms Access Database - single table Queries
  4. Using SQL to access data from multiple tables