UBI/UTI 501 Discrete Structures for Computer Science 

 

Fall 2019

 

Instructor: Asst. Prof. Dr. İlker Kocabaş (ilker.kocabas@ege.edu.tr)

Assistant: Cemre Candemir (cemre.candemir@ege.edu.tr)

Time: Thursday 09:15 – 12:00 (UBI)/ Thursday 18:15 – 21:00 (UTI)

Office Hour: Wednesday 15:00 – 17:00. For other times please make an appointment.

 

All important information about the course is available from this Web page.

 

 

Announcements:

*    Quiz grades

*    Grades (09.01.2020)

 

*    For UBI501:

*    The midterm exam will take place on Thursday, December 5, 2019 at 13:30 in the library of UBE.

*    The final exam will take place on Thursday, January 09, 2020 at 13:30 in the library of UBE.

 

*    For UTI501:

*    The midterm exam will take place on Thursday, December 5, 2019 at 18:30 in the library of UBE.

 

 

Course Description:

Principles of discrete mathematics and its applications to computer science. Topics include: Fundamental Mathematical Concepts and Structures [Algorithms & Complexity, Integers, Matrices], Mathematical Reasoning [Proof Methods, Induction, Recursion], Counting [Permutations & Combinations, Discrete Probability], Relations [Representation, Equivalence Relations], Graphs [Terminology, Representation, Trees].

 

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:

There are no course prerequisites.

 

Course Material:

*    Required lecture slides (available on the course’s web  page)

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

 

Tentative Course Syllabus:

Date

Topics

Supplementary Notes

06.10

Overview: Introduction of course contents.

 

13.10

The Foundations: Logic, Proposition Equivalences, Predicates, Quantifiers, Proof Methods

QSET#1

20.10

The Foundations: Sets, Set Operations

QSET#2

27.10

The Fundamentals:  Functions , Series, Summations

QSET#3

03.11

The Fundamentals: Algorithms, Algorithm Complexity, : Big-O notation, Growth of Functions

 

10.11

The Fundamentals: Number Theory

 

17.11

Mathematical Reasoning: Induction, Recursion

 

24.11

MIDTERM

 

01.12

Counting: The Basics of Counting, Pigeonhole Principle, Permutations, Combinations

 

08.12

Counting: Discrete Probability, Recurrence Relations

SupNotes#1

SupNotes#2

SupNotes#3

15.12

Relations: n-ary Relations, Representation of Relations

SupNotes#1

SupNotes#2

22.12

Relations: Closures of Relations, Equivalence Relations

SupNotes#1

SupNotes#2

SupNotes#3

29.12

Graphs: Terminology, Representations of Graphs

 

05.01

Graphs: Graph Isomorphism, Connectivity, Euler and Hamilton Paths

 

 

Trees: Trees & Sorting, Spaning Trees

 

 

Grading (Tentative):

*    Quiz 30%

*    Midterm 30%

*    Final 40%