COURSE UNIT TITLE

: DISCRETE AND COMBINATORIAL MATHEMATICS

Description of Individual Course Units

Course Unit Code Course Unit Title Type Of Course D U L ECTS
MAT 3060 DISCRETE AND COMBINATORIAL MATHEMATICS ELECTIVE 4 0 0 7

Offered By

Mathematics (English)

Level of Course Unit

First Cycle Programmes (Bachelor's Degree)

Course Coordinator

PROFESSOR DOCTOR HALIL ORUÇ

Offered to

Mathematics (English)

Course Objective

This course introduces students to the field of discrete and combinatorial mathematics. It aims to develop mathematical reasoning and problem solving skills through counting discrete structures and it also gives an opportunity to think algorithmically and to solve real world problems.

Learning Outcomes of the Course Unit

1   be able to use basic counting techniques
2   be able to formulate the principle of inclusion and exclusion and apply to the problems of counting
3   be able to identify recursive structures and solve their recurrence relations
4   be able to identify generating functions and apply to enumeration
5   be able to determine time complexity of basic searching and sorting algorithms

Mode of Delivery

Face -to- Face

Prerequisites and Co-requisites

None

Recomended Optional Programme Components

None

Course Contents

Week Subject Description
1 What is Discrete and Combinatorial Mathematics Examples of problems, The rules of sum and product Permutations and combinations, Pascal s identity, Binomial Theorem
2 Pascal s triangle identities, Vandermonde s identity, Permutations and with repetition, Multinomial Theorem, Combination with repetition, Pigeonhole principle
3 Principle of inclusion and exclusion, derangements and properties
4 Principle of inclusion and exclusion counting onto functions and Stirling numbers, Euler phi function, counting primes
5 Solutions of problem set 1 and set 2
6 Recursive definitions and solving linear recurrences, Fibonacci numbers
7 Solving nonhomogeneous linear recurrences, solutions of problem set 3.
8 Special type of recurrences, Stirling numbers (first and second kind), Bell numbers
9 Problems and Solutions
10 Catalan numbers and applications, difference sequences, sum of powers of positive integers
11 Generating functions, exponential generating functions, convolution sequences
12 Solving recurrence relations by the method of generating functions, integer partitions, solutions of problem set 4
13 Growth of functions, big O and big notation, time complexity, Divide and conquer algorithms,
14 Binary search, bubble sort, insertion sort, merge sort and their time complexity. Solution of Problem Set 5

Recomended or Required Reading

Textbook(s): Discrete and Combinatorial Mathematics, R. Grimaldi 5th ed. ISBN 9780201726343.
Supplementary Book(s): Discrete mathematics and its applications, K. Rosen 6th ed. ISBN 9780073229720.
References:
Materials: Lecture notes and problems will be given in the class

Planned Learning Activities and Teaching Methods

Face to face and presentation, problem solving

Assessment Methods

SORTING NUMBER SHORT CODE LONG CODE FORMULA
1 MTE MIDTERM EXAM
2 FIN FINAL EXAM
3 FCG FINAL COURSE GRADE MTE * 0.50 + FIN * 0.50
4 RST RESIT
5 FCGR FINAL COURSE GRADE (RESIT) MTE * 0.50 + RST * 0.50


Further Notes About Assessment Methods

None

Assessment Criteria

Mid Term and Final Exam

Language of Instruction

English

Course Policies and Rules

To be announced

Contact Details for the Lecturer(s)

halil.oruc@deu.edu.tr
Tel: (232) 30 18577
Ofis B205

Office Hours

To be announced

Work Placement(s)

None

Workload Calculation

Activities Number Time (hours) Total Work Load (hours)
Lectures 14 4 56
Preparations before/after weekly lectures 13 3 39
Preparation for midterm exam 1 30 30
Preparation for final exam 1 40 40
Midterm 1 2 2
Final 1 2 2
TOTAL WORKLOAD (hours) 169

Contribution of Learning Outcomes to Programme Outcomes

PO/LOPO.1PO.2PO.3PO.4PO.5PO.6PO.7PO.8PO.9PO.10PO.11PO.12PO.13
LO.15544
LO.25534
LO.345544
LO.444444
LO.5445444