Objects studied in discrete mathematics are largely countable sets such as integers, finite graphs, and formal languages. The aim of this course is to teach mathematical basics of computer applications.

Learning Outcomes

CTPO

TOA

Upon successful completion of the course, the students will be able to :

LO - 1 :

describe mathematical basics of computer science and fundamental concepts of discrete systems
describe mathematical basics of computer science and fundamental concepts of discrete systems

1,2,3,4

1,3

LO - 2 :

apply mathematical methods to computer science related and other engineering problems

1,2,3

1,3

LO - 3 :

describe combinatorical computation principles

1,2,3,4

1,3

LO - 4 :

use graph theory in modeling of discrete systems.

1,2,3,4

1,3

CTPO : Contribution to programme outcomes, TOA :Type of assessment (1: written exam, 2: Oral exam, 3: Homework assignment, 4: Laboratory exercise/exam, 5: Seminar / presentation, 6: Term paper), LO : Learning Outcome

Contents of the Course

Logic and Proofs. Enumerative combinatorics. Recurrence Relations. Graph Theory, Representing graphs. The 4-color problem. Boolean Algebra and Combinatorial Circuits. Sets. Formal systems. Hamilton and Euler loops. Counting and relations.

Course Syllabus

Week

Subject

Related Notes / Files

Week 1

Introduction. Sets and Relations

Week 2

Models. relations and Their properties. Representing Relations

Week 3

Boolean algebra. Boolean Functions Properties.

Week 4

Completenesss.

Week 5

Boole Function Applications. Minimization of Circuits

Week 6

Introduction to Graphs

Week 7

Representing Graphs and Graph Izomorphism

Week 8

Connectivity

Week 9

Mid-term exam

Week 10

Euler and Hamilton Paths

Week 11

Graf Coloring

Week 12

Shortest Path Problems. Planar Graphs

Week 13

short exam

Week 14

Application problems

Week 15

Characterization. Forbidden figurs

Week 16

End-of-term exam

Textbook / Material

1

Discrete Mathematics, Richard Johnsonbaugh, Prentice-Hall, 2001.

Recommended Reading

1

Discrete and Combinational Mathematics, Ralph.P. Grimaldi, An Applied Introduction, Addison-Wesley, 1998.