CS 105: Discrete Structures of Computer Science

Fall 2008/2009

Assoc. Prof. Dr. Brahim HNICH

http://homes.ieu.edu.tr/~bhnich

brahim.hnich@ieu.edu.tr

Office: 415

Course Description

This course seeks to place on solid foundations the most common structures of computer science, to illustrate proof techniques, to provide the background for an introductory course in computational theory, and to introduce basic concepts of probability theory. Topics include Boolean algebras, logic, set theory, relations and functions, graph theory, combinatorics, and probability. The course syllabus can be found here.

Course Resources

• Lectures: There are two groups that I teach this fall:
• Software Engineering Group : Each Monday @ 8:30--11:20 in M107
• Computer Engineering Group : Each Monday @ 12:30--15:20 in M107
• Textbook: Discrete and Combinatorial Mathematics (An Applied Introduction) by Ralph. G. Grimaldi, Addison-Wesley: 5^th Edition
• Web page: All slides used during lectures and related documents can be obtained from the course web page
• Office hours: Each Wednesday from 13:30--17:30, or by appointment
• Teaching Assistant: TBA

Marking Scheme

• 5-6 Homework assignments worth 5\% each,
• 1 Midterm worth 30\%, and
• Final exam worth 40\%

Academic Honesty

Academic Honesty plays a key role in maintaining high standards of academic excellence and integrity. Therefore, all students are kindly reminded that acts of intellectual dishonesty are subject to disciplinary action by the University.

Detailed Course Contents

• Introduction
• Fundamentals of logic
• Basic connectives and truth tables
• Logical equivalence: The laws of logic
• Logical implication: Rules of inference
• The use of quantifiers
• Logical inference of quantified statements
• Theorems and proofs
• Set Theory
• Sets and subsets
• Set operations and the laws of set theory
• Relations and functions
• Relations
• Orders and equivalences
• Functions
• Bijections and Cardinality
• Growth of functions
• Mathematical induction
• Basics of counting & the principle of inclusion and exclusion
• Counting: Permutations and combinations
• The pigeonhole principal
• Combinatorics: Binomial coefficients
• Finite probability
• Graphs and trees

Slides follow closely those of A. Bulatov for logic, set theory,and relations and function. For the rest of the subjects they follow those of A. Bloomfield.

Homeworks

Please download the latest version of the homework as some typos have been spotted and corrected!

Homework 1 and its solution.

Homework 2 and its solution.

Homework 3 and its solution

Homework 4 and its solution prepared by Zeynep ODABAS. Please send the code to gzd.ee@hotmail.com

Homework 5 and its solution prepared by Zeynep ODABAS.

Tutorials

Please download the latest version of the tutorials as some typos have been spotted and corrected!

Tutorial 1 and its solution prepared by Zeynep ODABAS

Tutorial 2 and its solution prepared by Zeynep ODABAS

Tutorial 3 and its solution prepared by Zeynep ODABAS

Tutorial 4 and its solution prepared by Zeynep ODABAS