COMBINATORICS

Course Code:

MATH 158

Semester:

Spring

Course Type:

Core

P:

2

Lab:

2

Laboratuvar Saati:

0

Credits:

3

ECTS:

7

Course Language:

English

Course Objectives:

The aim of this course is to introduce the topics and techniques of discrete methods and combinatorial reasoning with wide variety of applications.

Course Content:

Fundamental principle of counting. Introduction to discrete probability. Pigeonhole principle. The principle of inclusion and exclusion. Recurrence relations. Introduction to graph theory. Languages and finite state machines.

Course Methodology:

1: Lecture, 2: Problem Solving

Course Evaluation Methods:

A: Written examination

Vertical Tabs

Course Learning Outcomes

Learning Outcomes	Teaching Methods	Assessment Methods
1) Understands and solves problems in counting using the basic principles of counting.	1,2	A
2) Uses the principle of inclusion and exclusion to solve related problems indirectly.	1,2	A
3) Solves first-order linear recurrence relations, second-order linear homogeneous recurrence relations with constant coefficients, and some particular nonhomogeneous recurrence relations.	1,2	A
4) Models a given particular situation or a problem using graph theory.	1,2	A
5) Decides whether or not given graphs are isomorphic.	1,2	A
6) Understands the structure of languages and finite state machines	1,2	A

Course Flow

Week	Topics	Study Materials
1	The rules of sum and product. Permutations	1.1, 1.2
2	Combinations. The binomial theorem. Combinations with repetition	1.3, 1.4
3	The pigeonhole principle	5.5
4	Well-ordering principle, Mathematical Induction	4.1, 4.2
5	Division algorithm. The Euclidean algorithm. The fundamental theorem of arithmetic	4.3, 4.4, 4.5
6	The principle of inclusion and exclusion.	8.1, 8.2
7	Generating functions	9.1, 9.2
8	Partition of integers	9.3, 9.4
9	The first-order linear recurrence relation	10.1
10	The Second-order linear homogeneous recurrence relation with constant coefficients	10.2
11	The non-homogeneous recurrence relation	10.3
12	Method of generating functions	10.4
13	Graph theory: Graphs, subgraphs, complements, graph isomorphisms	11.1, 11.2
14	Languages: Finite state machine	6.1, 6.2, 6.3

Recommended Sources

Textbook	Discrete and Combinatorial Mathematics, R.P. Grimaldi, Addison-Wesley, 5th edition, 2013.
Additional Resources	Discrete Mathematics and Its Applications, K. H. Rosen, Mc Graw Hill, 6th edition, 2007.

Material Sharing

Documents
Assignments
Exams

Assessment

IN-TERM STUDIES	NUMBER	PERCENTAGE
Mid-terms	1	100
Quizzes
Assignments
Total		100
CONTRIBUTION OF FINAL EXAMINATION TO OVERALL GRADE		60
CONTRIBUTION OF IN-TERM STUDIES TO OVERALL GRADE		40
Total		100

COURSE CATEGORY

Core Courses

Course’s Contribution to Program

No	Program Learning Outcomes	Contribution
No	Program Learning Outcomes	1	2	3	4	5
1	The ability to make computation on the basic topics of mathematics such as limit, derivative, integral, logic, linear algebra and discrete mathematics which provide a basis for the fundamenral research fields in mathematics (i.e., analysis, algebra, differential equations and geometry)					x
2	Acquiring fundamental knowledge on fundamental research fields in mathematics	x
3	Ability form and interpret the relations between research topics in mathematics	x
4	Ability to define, formulate and solve mathematical problems				x
5	Consciousness of professional ethics and responsibilty				x
6	Ability to communicate actively	x
7	Ability of self-development in fields of interest					x
8	Ability to learn, choose and use necessary information technologies	x
9	Lifelong education				x

ECTS

Activities	Quantity	Duration (Hour)	Total Workload (Hour)
Course Duration (14x Total course hours)	14	4	56
Hours for off-the-classroom study (Pre-study, practice)	14	6	84
Mid-terms (Including self study)	1	15	15
Quizzes
Assignments
Final examination (Including self study)	1	20	20
Total Work Load			175
Total Work Load / 25 (h)			7
ECTS Credit of the Course			7

Search form