CloseHelpPrint
Kies de Nederlandse taal
Course module: 202001363
202001363
Implementation Project on Graph Isomorphism
Course info
Course module202001363
Credits (ECTS)3
Course typeStudy Unit
Language of instructionEnglish
Contact persondr. R.P. Hoeksma
E-mailr.p.hoeksma@utwente.nl
Lecturer(s)
PreviousNext 1
Tutor
dr. F. Ahmed
Examiner
dr. R.P. Hoeksma
Contactperson for the course
dr. R.P. Hoeksma
Lecturer
dr. B. Manthey
Lecturer
dr. A. Skopalik
Academic year2020
Starting block
2A
Application procedureYou apply via OSIRIS Student
Registration using OSIRISYes
Aims
After following this course the student:
  • is able to translate mathematical concepts into algorithms and implement them into a (Python) program;
  • is able to choose the right data structure(s) for the practical implementation of algorithms;
  • can work in a group on an implementation project that has multiple modular parts;
  • can document the computation results obtained with (different versions of) the implementation of an algorithm.
Content
In this project, students implement an algorithm for solving the notorious graph isomorphism (and graph automorphism counting) problem.
 
This can be accomplished on various levels of mathematical complexity, and nicely connects to all of the topics that are treated in the module.
The implementation project ends with a sort of “competition" in which students test the capability of their own implementation on a set of benchmark instances of increasing difficulty.
 
Assumed previous knowledge
Before participating in this project the student should have some experience with programming (in any programming language or, e.g., MATLAB).
As this project integrates material from the courses Algorithmic Discrete Mathematics, Languages & Machines and Algebra, participation is conditional on students that are also enrolled in the other study units of the module, or have successfully completed these study units earlier. Exceptions are possible for students with equivalent prior knowledge.
Module
Module 7
Participating study
Bachelor Applied Mathematics
Participating study
Bachelor Technical Computer Science
Required materials
Handouts
Lecture slides
Recommended materials
-
Instructional modes
Assignment
Presence dutyYes

Lecture
Presence dutyYes

Practical
Presence dutyYes

Project supervised
Presence dutyYes

Project unsupervised
Presence dutyYes

Tests
Graph-Isomorphism Algor. Implementation

CloseHelpPrint
Kies de Nederlandse taal