UBE 501

DISCRETE MATHEMATICS and its APPLICATIONS to COMPUTER SCIENCE

*2008-2009
FALL*

**Catalog Data: **Discrete Mathematics and its applications
to Computer science, 3 hours lecture.

Principles of discrete
mathematics and its applications to computer science

**Instructor: **Dr. Mehmet E.
DALKILIC (mehmet.emin.dalkilic@ube.ege.edu.tr)

**Textbook** Kenneth H. Rosen, Discrete Mathematics and Its Applications,
6th ed., McGraw Hill, 2007

**Goals: **To introduce the mathematical tools for describing data
structures and algorithms and the concepts of modern

algebra as applied to the design
of digital systems.

**Prerequisites: **Basic Mathematics Skills

**Topics:**

**Foundations:**Logic, Propositional Equivalances, Predicates and Quantifiers**Foundations (cont'd):**Sets, Set Operations, Functions, Sequences and Summations**Foundations (cont'd):**Big-O notation,**Fundamentals:**Algorithms, Complexity of Algorithms, Integers, Matrices**Mathematical Reasoning:**Proof Techniques, Induction, Recursion**Counting:**Basics of Counting, Pigeonhole Principle, Permutations and Combinations**Counting (cont'd):**Discrete Probability, Generating Permutations and Combinations, Recurrence Relations**Relations:**n-ary Relations, Representing Relations, Closures of Relations, Equivalence Relations**Graphs:**Graph Terminology, Representing Graphs, Graph Isomorhism, Connectivity**Graphs (cont'd):**Euler and hamilton Paths, Trees**Boolean Algebra:**Boolean Functions, Logic Gates, Minimization of Circuits**Modeling Computation:**Finite State Machines, Turing Machines

**Grading:**- Homeworks %30
- Midterm %30
- Final Exam %40

**Note: **Only
a subset of homework problems will be graded.

Class material ube501.rar

Homework#1 **(Do not submit. Your work will be evaluated
through in class Quiz #1 on Oct. 16 ^{th}
2008, 09:00-09:15)**

** Section 1.1 (9, 27, 55)**

**
Section 1.2 (6, 15, 28, 42, 43,50, 59) **

** Here
are the problems courtesy of TA Sinem Aslan**

Homework#2 **(Do not submit. Your work will be evaluated
through **

** in class Quiz #2 on Oct. 23 ^{th} 2008,
09:00-09:15)**

** Section 1.3 (5, 10, 19)**

**
Section 1.4 (9, 26, 31) **

** Section 1.5 (13, 16, 23)**

** Here
are the problems courtesy of TA Sinem Aslan**

Homework#3 **(Do
not submit. Your work will be evaluated through **

** in class Quiz #3 on Oct. 30 ^{th} 2008,
09:00-09:15)**

** Section 1.5 (20, 33)**

**
Section 1.6 (8, 17, 31, 39) **

** Section 1.7 (6, 7, 27, 36)**

** Here
are the problems courtesy of TA Sinem Aslan**

Homework#4 **(Do
not submit. Your work will be evaluated through **

** in class Quiz #4 on Nov 6 ^{th} 2008,
13:30-13:45)**

** Section 2.1 (2, 16, 20)**

**
Section 2.2 (9, 15, 42) **

** Section 2.3 (19, 30, 46)**

** Section 2.4 (40) Read the definition of
“countable set” carefully; Consider all different cases.**

**Here
are the problems courtesy of TA Sinem Aslan**

Homework#5 **(Do
not submit. Your work will be evaluated through **

** in class Quiz #5 on Nov 13 ^{th} 2008, 09:00 –
09:15)**

** Section 3.1 (15, 16)**

**
Section 3.2 (5, 14, 21) **

** Section 3.3 (1, 9, 10) Here are the problems courtesy of TA
Sinem Aslan**

Homework#6 **(Do
not submit. Your work will be evaluated through **

** in class Quiz #6 on Nov 20 ^{th} 2008, 09:00 – 09:15)**

** Section 3.1 (3, 7)**

**
Section 3.2 (12, 24) **

** Section 3.3 ( 12 )**

** Section 4.1 (5, 15, 18) Here are the problems courtesy of TA
Sinem Aslan**

Homework#7 **(Do
not submit. Your work will be evaluated through **

** in midterm
exam on Nov 27 ^{th} 2008, 09:15
– 11:15)**

** Section 4.1 (48)**

**
Section 4.3 (5, 13, 25) **

** Section 4.4 (3, 9, 12, 28) Here are the problems courtesy of TA
Sinem Aslan**

Homework#8 **(Do
not submit. Your work will be evaluated through **

** in class Quiz on December 18 ^{th} 2008, 09:00 –
09:15)**

** Section 5.1 (57, 30, 22, 9)**

**
Section 5.3 (3, 12, 22, 33) Here
are the problems courtesy of TA Sinem Aslan**

Homework#9 **(Do
not submit. Your work will be evaluated through **

** in class Quiz on December 25 ^{th} 2008, 09:00 –
09:15)**

** Section 8.1 (7, 28, 35 (only
parts a,b,c,d), and 48)**

**
Section 8.3 (4, 13, 14, 15) Here
are the problems courtesy of TA Sinem Aslan**

Homework#10 **(Do
not submit. Your work will be evaluated through **

** in class Quiz on October 8 ^{th} 2008, 09:00 –
09:15)**

** Section 8.4 (19, 24, 26, 29)**

**
Section 8.5 (2, 11, 16, 26) Here
are the problems courtesy of TA Sinem Aslan**

**Note: TA
Sinem Aslan’s office hours is Wednesday 15:00 – 17:00. For other times please
make an appointment.**

*Send any comments or suggestions
to dalkilic*

Last revised in Sept 24, 1997