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, Growth of Functions
• 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.

Course Homepages

Return to Academic Information Page

Return to ICI homepage

---

Send any comments or suggestions to dalkilic
Last revised in Sept 24, 1997