Advanced Algorithms and Data Structures

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 digital 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 digital 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	In the academic year 2020-2021, 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 non-CS students. These places are filled on a first-come-first-served basis, with priority given to students with a strong CS-related background (e.g., CS exchange students, AI students, etc.). These students need to meet the course prerequisite requirements as mentioned on Ocasys. For more info about the enrollment procedure, see https://student.portal.rug.nl/infonet/studenten/fse/programmes/bsc-cs/general/vakintekening-procedure#cap This course was registered last year with course code INBGAD-10
Opgenomen in	Opleiding Jaar Periode Type BSc Computing Science 1 semester II b verplicht BSc Courses for Exchange Students: AI - Computing Science - Mathematics - semester II b