Discrete Structures
Faculteit  Science and Engineering 
Jaar  2022/23 
Vakcode  WBCS01105 
Vaknaam  Discrete Structures 
Niveau(s)  propedeuse 
Voertaal  Engels 
Periode  semester I b 
ECTS  5 
Rooster  rooster.rug.nl 
Uitgebreide vaknaam  Discrete Structures  
Leerdoelen  At the end of the course, the student is able to: 1) Apply definitions and constructions pertaining to discrete mathematical objects such as numbers, recurrences, sets, functions, relations, partially ordered sets, graphs, and trees. 2) Count discrete mathematical objects such as sets and sequences. 3) Carry out simple mathematical proofs, including proofs by (strong) mathematical induction, to formally justify properties of discrete mathematical structures. 4) Apply various algorithms for solving problems or computing properties of relations, trees and graphs. 

Omschrijving  This course covers concepts from discrete mathematics that are used to understand and describe computers and programs at an abstract level: • Sets, sequences, languages, matrices, mathematical structures. • Mathematical induction. • Permutations and combinations. • Recurrence relations. • Partitions, relations, digraphs, equivalences. • Functions. • Ordering relations, partially ordered sets. • Extreme elements, lattices, Boolean algebras. • Trees, searching in trees, spanning trees. • Graphs. Eulerian and Hamiltonian paths. During the lectures, material from the book will be presented by the lecturers. During tutorials, teaching assistants will guide students in solving exercises, and solutions will be discussed. In addition to the weekly tutorial exercises, there will be 4 homework sets that the students can submit to obtain feedback on their learning. These homework sets do not contribute to the final course grade. 

Uren per week  
Onderwijsvorm  Hoorcollege (LC), Opdracht (ASM), Werkcollege (T)  
Toetsvorm 
Schriftelijk tentamen (WE)
(The final grade is equal to the exam grade.) 

Vaksoort  propedeuse  
Coördinator  D. Düstegör, PhD.  
Docent(en)  D. Düstegör, PhD. ,Prof. Dr. H.H. Hansen  
Verplichte literatuur 


Entreevoorwaarden  This firstyear course unit assumes prior knowledge acquired from high school but also from the course Introduction to Logic (Year 1, 1a).  
Opmerkingen  All CS bachelor courses have limited enrollment:  CS students can always enter each course, regardless of whether the course is mandatory for them or not.  A maximum of only 20 places per course is available for nonCS students. These places are filled on a firstcomefirstserved basis, with priority given to students with a strong CSrelated background (e.g., CS exchange students, AI students, etc.). These students need to meet the course prerequisite requirements as mentioned on Ocasys. Six weeks before the course starts, the 20 students that can join are selected and added to the course. If you enroll after this date, you will be placed on the waiting list. For more info about the enrollment procedure, see https://student.portal.rug.nl/infonet/studenten/fse/programmes/bsccs/general/vakintekeningprocedure#cap 

Opgenomen in 
