Advanced Algorithms and Data Structures

Faculteit Science and Engineering
Jaar 2019/20
Vakcode INBGAD-10
Vaknaam Advanced Algorithms and Data Structures
Niveau(s) bachelor
Voertaal Engels
Periode semester I b
ECTS 5
Rooster rooster.rug.nl

Uitgebreide vaknaam Advanced Algorithms and Data Structures
Leerdoelen At the end of the course, the student is able to:
1) describe several fundamental algorithms and data structures that play a central role in Computing Science.
2) describe algorithms in both pseudocode and in a programming language.
3) reason about algorithms and data structures concerning correctness and efficiency.
4) analyse algorithms and data structures by means of experiments.
5) report about activities that involve the knowledge and skills listed above.
Omschrijving You learn a core subject in computer science related to the art of problem solving: the practical design and theoretical analysis of algorithms and data structures.
We will look at algorithmic complexity, such as the resource consumption of an algorithm, in terms of formal analysis of computing time and memory requirements. Our approach will be scientific, focusing on asymptotic behaviour: what is the increase in resource consumption when the size of the input increases? How can this asymptotic behaviour be proven formally and what are typical examples of efficient algorithmic strategies to solve common problems in Computer Science?
We will cover the following topics: problem solving strategies, such as Divide & Conquer, Dynamic Programming, Greedy, automata and graph algorithms, elementary data structures and algorithmic complexity classes. More specific: sorting algorithms, medians and order statistics, hash tables, search trees, minimum spanning trees, shortest paths, maximum flow networks, string matching and NP-completeness. These algorithms form the foundation of many computing systems, from web search to network protocols and efficient strategies for problem solving. The topics taught are relevant, independent of your decision to go to industry or continuing an academic career.
Many examples and strategies are taken from industrial coding interviews and many of above mentioned concepts have found their way into approximate solutions proposed in machine learning and AI.
Some assignments will be theoretical, and some practical (in C or Python).

Please note:
Since this is an advanced course it is designed to prepare you for more realistic situations you might encounter in your future job. This means that in the duration of the course more and more strategies become available to solve a problem and the most efficient one must be identified by you. Some test cases for evaluation of assignments will remain hidden, needing you to think about test cases.
Uren per week
Onderwijsvorm Hoorcollege (LC)
(The assignments and the exam are mandatory)
Toetsvorm Opdracht (AST), Schriftelijk tentamen (WE)
(The assignments (both of a theoretical nature, and some programmed in C or Python, the A grade) are worth together 60% of the grade; the exam (the E grade) is worth 40% of the grade. Both A and E grades must be above 5.0. You need at least 300 points in the practicals and 200 in the exam and the total sum must be >550 Points to be able to pass the course (5.5 will be rounded to 6).)
Vaksoort bachelor
Coördinator K. Bunte, PhD.
Docent(en) K. Bunte, PhD. , V. Degeler, PhD.
Verplichte literatuur
Titel Auteur ISBN Prijs
Introduction to Algorithms (third edition, MIT Press, 2009) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein 9780262033848
Entreevoorwaarden The course unit recommends prior knowledge acquired from courses Algorithms and Data Structures in C, Discrete Structures, and Object-Oriented Programming from the degree programme Computing Science or equivalent.
More specifically we assume:
- basic knowledge of probability theory (Bernoulli trials, Indicator variables, conditional probability, etc.)
- that you have implemented algorithms like Insertion sort, Merge Sort, Counting Sort, Quicksort and search in Graph structures.
If the above is missing or forgotten it is recommended to recap in self study before starting the course.
Opmerkingen
Opgenomen in
Opleiding Jaar Periode Type
BSc Computing Science 2 semester I b verplicht
BSc Courses for Exchange Students: Artificial Intelligence & Computing Science - semester I b Computing Science
BSc Econometrics and Operations Research/EOR  (keuzevakken BSc EOR) 3 semester I b keuze