CIS 2166 Course Outline

" In Computer Science, Elegance Is Not A Dispensable Luxury, But A Matter Of Life And Death " 

                                         --- E. W. Dijkstra
Instructor: Dr. Arthur T. Poe
Time: Tuesday & Thursday, 8:40am - 10:00am (Section I)
Place:  
Text: Discrete Mathematics and its Applications, By Kenneth H. Rosen 3nd. Ed. McGraw Hill
Pre-requisites: Grade C or better in CIS 1066
Grading: Homework: 25-30%
  Midterm: 30%
  Final: 40-45%

Topics

For Review Selected Sections from Chapter 2, 3, and 6
Chapter 4 Counting - §4.1, §4.2, §4.3
Chapter 5 Advanced Counting Techniques - §5.1, §5.2, §5.4, §5.5 with other supplements
Chapter 6 Relations - §6.4
Chapter 7 Graphs - §7.1, §7.2, §7.3, §7.4, §7.6, §7.7
Chapter 9 Boolean Algebra - §9.4 with other supplements
Chapter 10 Modeling Computation - §10.1, §10.2, §10.3, §10.4, (§10.5)

Outline

I. Reviews and Preliminaries:
  • PMI (Principle of mathematical induction) and loop invariance
  • Relations and their closures
  • Functions, bijections, cardinality
  • Properties of integers
  • Euclidean Algorithm
  • Linear congruence
  • Pigeon Hole Principle
II. Growth of Functions
  • Big O notation -- asymptotic behavior
  • various Big O classes
III. Recursive
  • Recursive Definitions
  • Recursively defined sets
IV. Relation and its Transitive Closure
  • Warshall's algorithm and its complexity
V. Solving Recurrence Relations
  • Linear Homogeneous recurrence relation with constant coefficients
  • Non-homogeneous recurrence relation. By iteration, by characteristic equation, by undetermined coefficient, (by generating function).
  • Strassens method for matrix multiplication, (Number of onto-functions)
VI. Permutations
  • R-permutation
  • R-combination
  • Binomial coefficients and their computation.
  • Permutation as a product of disjoint cycles.
  • Permutation generation.
VII. Graphs
  • Adjacency
  • Connectivity
  • Graph invariance
  • Isomorphism.
  • Planarity
  • Euler's formula
  • Kuratoski's theorem.
  • Dijkstra's shortest path algorithm
VIII. Boolean Algebra
  • Minimization -- Quine-McCluskey method
IX. Languages and Grammars
  • Types of grammar
  • Regular sets and type 3 languages
  • Non-regular languages and machines.