CIS 1066 Course Outline

Mathematical Concepts in Computing I
(Discrete Structures in Computer Science)

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

                                         --- E. W. Dijkstra
Instructor: Dr. Arthur T. Poe
Office Hours: Mondays and Wednesdays 2:00 - 3:00 pm
Place:  
Text: Discrete Mathematics and its Applications, By Kenneth H. Rosen 3rd. Ed. McGraw Hill
Pre-requisites: Grade of C or better in Mathematics 1022, or placement into Mathematics 1041
Grading: Homework: 25-30%
  Midterm: 30%
  Final: 40-45%
The reason for studying discrete mathematics and the goals of this course can be found in the PREFACE and TO THE STUDENT of the textbook. You are asked to read these two parts very carefully.

My lectures will focus on both the understanding of the basic concepts and some of their applications. I believe in active learning: namely my view of learning is that it is a two way street. Therefore, I encourage the class to ask questions. My answer, most of the time, however, will be another question --- a leading question. The emphasis is to enhance your abilities to think and to solve problems by yourself systematically. I would expect you to read the course material we cover in class, either before we meet in class or after we meet, PERFERRABLY BOTH. Being able to take good class notes is crucial. Everytime we meet, We will devote first 10-15 minutes of class time to questions.

I collect homework every week. You are encouraged to DISCUSS our class material and your homework with your fellow classmates. But you must be sure that you really understand the reasons, therefore can solve similar problems afterwards.

Copying somebody-else's homework is prohibited.

Examination problems are of three (3) types:
1. Definitions and statements
2. Calcuations and manipulations
3. Proofs.

I do not give make-up exam. You will be given at least one week's notice before midterm. If you have a legitimate excuse, AND you have obtained my prior approval, your final grade will then depend on homework and final.

For those who want decent grades in exams, you should demonstrate that you are able to:

1. Express the basic concepts, carry out operations, and prove properties of the discrete structures you learned with precision and clarity. The first, and most basic thing is to know all the definitions, and their subtle points. For theorems, you should know the conditions under which each theroem holds, and their implications.

2. Skillfully solve routine problems.

3. Apply various kinds of methods to analyze and solve reasonaby difficult problems to show that you have a firm grasp of the knowledge.

See the following chart for topics to be covered (subject to change).

Finally, to understand and be proficient in this course, one needs to understand:
(1) the precision of language and notation we use, and
(2) the precision of reasoning we need.
To solve problems by yourself, (2) may perhaps be sufficient to certain degree, but to communicate problem solving to others, (1) is essential.

Outline

I. Logic: (Chapter 1.1 - 1.3)
  • Propositions and their equivalence
  • Predicate and Quantifiers
II. Method of Proof: (3.1 - 3.2)
  • Mathematical Induction
III. Sets and their Operations: (1.4 - 1.5)
  • Power Set
  • Cardinality of a set
  • Computer representation of sets
IV. Algorithms, Complexity of Algorithm: (1.8, 2.1 - 2.2)
  • The Growth of Functions
  • The Big-O notaion
V. Number Theory: (2.3 - 2.4 (p.122) - 2.5 (p.135), 2.6)
  • Properties of Integer
  • Application of Number Theory
  • Euclidean Algorithm
  • Linear Cngruences
  • Matrix Multiplications and their complexities
VI. Recursive: (3.3 - 3.4)
  • Recursive Definition and Algorithm
VII. Program Correctness: (3.5)
VIII. Relations: (6.1 - 6.3)
  • Relations and their representations
IX. Functions and Sequences: (1.6 - 1.7)
  • Cardinality: countable infinite
  • Regular sets and type 3 languages
  • Non-regular languages and machines.
X. Counting: (4.1 - 4.2)
  • Basic Counting techniques
  • Pigeonhole Principle
XI. Permutation and Combination: (4.3)
  • Permutation
  • Combination
XII. Probability Theory: (4.4)
XIII. Solving Recurrence Relations: (5.1 - 5.2)
  • Linear with Constant Coefficient
  • Homogeneous / inhomogeneous
XIV. Relations and their Closures: (6.3 - 6.5)
  • Reflexive Closure
  • Symmetric Closure
  • Transitive Closure
  • Warshall Algorithm
XV. Equivalence relations and Partitions: (1.6 - 1.7)