Course Number / Section:

CIS 2166 / 001

Course Title:

Mathematical Concepts in Computing II

Instructor:

Dr. Arthur T. Poe

      Office:

Wachman Hall, Room 1008.

      Email:

Arthur.poe@temple.edu

      Phone:

215-204-648.

Course Web Page:

 

Web Site for Complete 

Syllabus:

http://knight.cis.temple.edu/~poe

 

http://knight.cis.temple.edu/~poe

 

Prerequisites:

Grade of C or better in CIS1166 (066)

 

Textbook(s):

 “Discrete Mathematics and Its Applications” 6th Edition.

 By Kenneth H. Rosen McGraw-Hill.  Same text as CIS1166

 

Course Goals:

            This is a continuation of CIS1166(CIS66)

Concepts and Structure that are fundamental for Studying Computer Science are introduced so are their applications. Whenever possible, complexity associated with a computation will also be discussed. The goal is to instill in students the concepts and mechanics of formal methodology.

 

Topics Covered:

Concepts and structures that were introduced in CIS1166 (CIS66) are reviewed and revisited.    A program being partially  correct,  Hoare Triplet, Rules of Inference. Principle of Mathematical Induction and its application to Program Correctness/Verification.  Relations, properties of relations,  Closures of relations and their computation. Partial ordering and topological sort.  Equivalence relations and partitions.  Equivalence closure. Discrete Probability.  Graphs, connectivity, shortest paths problems.  Planarity.  Trees, Tree Traversal.  Spanning  trees,  Minimal Spanning Trees. Boolean functions and its minimization.  Models of Computation. Finite State Machines with output, without output (Automata).  Language recognition. Turing machines.

 

 

 

Attendance Policy:

 

Attendance will be taken during lectures as well as at recitation. Although occasional absence is tolerable, repeated absence without excuse affect your performance and grade.