Course Outline

COURSE OUTLINE (2012-2013)

COURSE TITLE: Discrete Mathematics

COURSE NUMBER: MATH3020

QUARTER CREDIT HOURS: 4.5

CONTACT HOURS: 45 lecture hours

PREREQUISITE(S): MATH1013 or MATH 1020

COURSE DESCRIPTION:

This course is designed to give students the basic mathematical concepts and methods that are prevalent in information science. Topics include sets, relations and functions, elementary graph and network theory, trees, matching algorithms, network flows, counting techniques, and recurrence relations.

COURSE OUTCOMES:

Students will be able to:

  1. Correctly perform operations with sets, relations, and functions on both examinations and in assigned work.
  2. Correctly use graphs, directed graphs, and multigraphs on both examinations and in assigned work.
  3. Correctly solve problems involving matching and matching algorithms on both examinations and in assigned work.
  4. Correctly solve problems involving network flows on both examinations and in assigned work.
  5. Correctly solve problems involving counting techniques on both examinations and in assigned work.
  6. Correctly solve problems involving recurrence relations and linear difference equations on both examinations and in assigned work.

CONTENT OUTLINE

1. Combinatorics

  1. The Fundamental Counting Principle
  2. Permutations and Combinations
  3. Permutations with Repetitions Present
  4. Probability
  5. The Binomial Theorem and Pascal’s Triangle
  6. The Matching and Knapsack Problems
  7. Algorithms

2. Sets, Relations and Functions

  1. Set Operations
  2. Equivalence Relations
  3. Congruence
  4. Functions
  5. Mathematical Induction
  6. Applications

3. Graphs

  1. Basic Concepts
  2. Paths and Circuits
  3. Shortest Path and Distance
  4. Coloring a Graph
  5. Directed Graphs and Multigraphs

4. Trees

  1. Basic Concepts
  2. Minimal and Maximal Spanning Trees
  3. Depth-First Search
  4. Rooted Trees
  5. Binary Trees and Traversals
  6. Optimal Trees

5. Recurrence Relations

  1. Basic Concepts
  2. Method of Iteration
  3. Linear Difference Equations
  4. Efficiency of Algorithms
  5. Generating Functions

REQUIRED TEXT(S)/TECHNOLOGY:

Lipschutz, Lipson, Schaum's Outlines: Discrete Mathematics, 3/e. McGraw Hill, 2007. 978-0-07-161586-0

A scientific or graphing calculator (smart phones/tablets/laptops are encouraged as alternatives to a calculator)

EVALUATIVE CRITERIA: 1. Periodic exams, quizzes, assignments 2. Final examination 3. Class participation/active learning

OUTCOMES ASSESSMENT: The results from testing students for the Performance Transcript in this course will be used to form a cohort for the assessment of Quantitative Literacy.

PERFORMANCE TRANSCRIPT: Quantitative Literacy, measured with the Accuplacer adaptive test of arithmetic and algebra.

WRITING INTENSIVE COURSE: N/A

HONORS OPTION: Available in this course

APPROVED COURSE CAPACITY: 40

CLASSROOM REQUIREMENTS: Lecture Room