 63705 Discrete Structures

# 63705 Discrete Structures

•  Study programme and level: Interdisciplinary University Study Programme in Administrative Information Science - 1st Cycle
• 6 ECTS
• Course type: Elective
• Lectures: 45
• Tutorial: 30
• Individual work: 105
• Lecturer: Gašper Fijavž, PhD

### 1. Objectives and competences

• Ability of critical thinking.
• Developing skills in critical, analytic and synthetic thinking.
• The object of the course is to deepen student’s understanding of mathematical logic and formal reasoning, together with the basics of discrete mathematics.

### 2. Content

Lectures:

Natural numbers: induction principle.

• Propositional calculus: truth tables, construction trees, complete sets of connectives, formal reasoning, basics of predicate calculus.
• Naive set theory: operations, mappings, basics of counting.
• Relations: properties and operations, equivalence relations, partial orders. Graph of relation.
• Number theory: extended Eucledian algorithm, linear Diophantine equations, modular arithmetic.
• Permutations: computing with permutations, parity, conjugate permutations.
• Graph theory: isomophism, operations, graph families, vertex degrees, subgraphs, connectivity, trees and forests, Euler and Hamilton graphs, graph colorings.
• Linear recurrence relations with constant coefficients. Homogeneous and nonhomogeneous.

Exercise groups:

• Exercise group time is in part devoted to the classical blackboard approach; the students solve computational problems with some help of TA. In part of the exercise groups the students individually solve computerized versions of problems using symbolic computation software.

Homework:

• Homework assignments are distributed on a weekly basis. The assignments are obligatory. Their purpose is to prepare the students for continuously working on the DS topics.

• G. Fijavž, Diskretne strukture, Ljubljana, 2014, matematika.fri.uni-lj.si/ds/ds.pdf.
• V. Batagelj, S. Klavžar: DS1, DMFA, Ljubljana, 1997.
• V. Batagelj, S. Klavžar: DS2, DMFA, Ljubljana, 2000.
• R. J. Wilson, J. J. Watkins: Uvod v teorijo grafov, DMFA, 1997.
• P. Grossman: Discrete mathematics for computing, Macmillan, 2002.
• J. L. Hein: Discrete Structures, Logic, and Computability, Jones & Bartlett, 2001.

### 4. Intended learning outcomes

Knowledge and understanding:

• After successfully finishing the course a student will master the basic principles of discrete mathematics, mathematical logic and their application in CS.

Application:

• Using mathematical logic and discrete mathematics in algorithm design.

Reflection:

• Using mathematical formalization to accurately and consistently describe the relation between a theoretical model and its implementation.

Transferable skills:

• Mathematical abstraction is frequently needed in all areas of computer and information science.

### 5. Learning and teaching methods

Lectures, exercise groups, homework assignments. The focus lies in continuous work with home assignments, using computer and symbolic computation software.

### 6. Assessment

Type (examination, oral, coursework, project):

• Continuing (homework, midterm exams) (50 %)
• Final (written exam) (50 %)