NWI-IBC018
Discrete Structures
Course infoSchedule
Course moduleNWI-IBC018
Credits (ECTS)3
CategoryBA (Bachelor)
Language of instructionDutch, English
Offered byRadboud University; Faculty of Science; Informatica en Informatiekunde;
Lecturer(s)
Coordinator
dr. E.G.M. Hubbers
Other course modules lecturer
Contactperson for the course
dr. E.G.M. Hubbers
Other course modules lecturer
Lecturer
dr. E.G.M. Hubbers
Other course modules lecturer
Lecturer
dr. F. Wiedijk
Other course modules lecturer
Academic year2017
Period
KW2  (13/11/2017 to 04/02/2018)
Starting block
KW2
Course mode
full-time
RemarksSchakelcursus alleen voor HBO-minoren, bestaande uit gedeelte Formeel Denken en gedeelte Combinatoriek
Registration using OSIRISYes
Course open to students from other facultiesNo
Pre-registrationNo
Waiting listNo
Placement procedure-
Aims
After the course participants are able to:
  • reproduce and use basic concepts from the field of graph theory;
  • compute and use binomial coefficients;
  • define functions using recursion and prove simple theroems using mathematical induction;
  • derive closed formulas for given recurrence relations..
Content
This course is not a course on its own, but combined from different topics from the courses Formal Reasoning (IPK001) and Combinatorics (IBC016). These are the topics discussed:
  • Formal Reasoning: Chapter 4, Discrete mathematics
    • Graph theory
    • Binomial coefficients
    • Recursion
    • Induction
  • Combinatorics: Homogeneous and nonhomogeneous linear recurrence relations
  • Computer assignment
Teaching formats
• 14 hours plenary lecture
• 4 hours unsupervised group project
• 2 hours presentation by students
• 2 hours response lecture
• 12 hours tutorial

Topics
Topics:
• Graph theory
• Binomial coefficients
• Induction
• Recursion, in particular

• Compute values given recurrence relations
• Define recurrence relations
• Transform recurrence relations into closed formulas

Test information
There are two non-mandatory intermediate tests for this course resulting in the grades TO1 and TO2. In addition there is a written final exam, resulting in the grade TE. The final grade of this course is given by the formula MAX(TE, (2*TE+TO1+TO2)/4). This grade is rounded as usual.
In order to be admitted to the final exam, the computer assignment must have been done sufficiently.

Prerequisites
The course Mathematical Structures (IPC020) or a similar course. Programming experience is required for the computer assignment.

Contact information
http://www.cs.ru.nl/~hubbers/courses/ds

Required materials
Reader
Herman Geuvers, Henk Barendregt, Bas Spitters, Engelbert Hubbers, Freek Wiedijk: Formal Reasoning. We only use chapter 4.
Book
'Discrete Mathematics and Its Applications', by Kenneth H. Rosen. We use the so-called 'Global edition' of the seventh edition. The same book is also used for the courses Mathematical Structures and Combinatorics
ISBN:9780071315012

Instructional modes
Course
Attendance MandatoryYes

Lecture

Remark
For the first part of the course the lectures for Formal Reasoning are joined. After that there are separate lectures.

Presentation
Attendance MandatoryYes

Remark
The results of a computer assignment need to be presented.

Response course

Remark
Response lectures are like qeustion sessions directly before the intermediate tests.

Tutorial

Remark
For the first part of the course each lesson starts with one hour tutorial followed by one hour lecture.

Zelfstudie
Attendance MandatoryYes

Tests
Tentamen
Test weight1
OpportunitiesBlock KW2, Block KW4