Study track: Algorithms and Data Structures (ADS)
Developing algorithms for computational problems is essential in software development. The efficiency of such algorithms is intricately related to the manner data is accessed and processed. Data structures play therefore very important role when developing efficient algorithms.
You are already familiar with various general (deterministic) algorithmic paradigms such as divide-and-conquer and dynamic programming. You already know some data structures such as priority queues and binary search trees. You have seen how they can be used to solve some basic computational problems such as sorting and shortest path. But this is only the top of the iceberg.
Randomized algorithms employ a certain degree of randomness to guide their logic in the pursuit of good performance on average. Randomization plays a crucial role in developing fast algorithms. Exploiting geometrical properties of some computational problems can also lead to very efficient algorithms. Finally, there is a rich variety of data structures that can be used to store and process data. All this is ahead of you.
A large family of so-called NP-complete problems most likely cannot be solved in polynomial time. It is often possible to decide if a particular problem belongs to this class of intractable problems. Such problem should then be approached by polynomial approximation methods with some good solution quality guarantees.
Many NP-complete problems have important real-life applications. If approximation methods fail to provide good guarantees, it is necessary to rely on heuristical methods that are fast and usually generate good (but not provably good) solutions. Finally, if data sets are of limited size, exact exponential methods can be used. These have their own non-trivial algorithmic challenges. All this and more is ahead of you.
You will obtain a solid knowledge of algorithmic paradigms, advanced algorithmic techniques, and various data structures applicable to a large spectrum of problems occurring when developing complex software in all kinds of applications. You will also be able to argue about solvability of computational problems, correctness, time- and space-complexity of algorithms.
Some track courses focus on theoretical aspects while others are oriented toward practical applications (big data, optimization, bioinformatics, software engineering).
You will find employment in various kinds of software development companies. It is also expected that considerable number of graduates will seek ph.d. positions.
If you want to follow this study track, your BSc background should include an introductory course on algorithms and data structures as well as solid working knowledge of basic discrete mathematics (elementary set theory, induction proofs, big-O notation, etc.), and linear algebra.
Sample MSc theses
To give you an idea of what an MSc thesis in the PLS track could be about, here are some representative examples of thesis titles from 2014 and 2015:
• 3D Restricted Kinetic Alpha Complexes and Application [no link]
The recommended courses in the Algorithms and Data Structures study track are shown below. Keep in mind that, like for all the study tracks, none of these are actually mandatory, and you may replace them with relevant courses from other tracks as you see fit.
|Block 1||Block 2||Block 3||Block 4|
||Advanced Programming||Advanced Computer Systems||Computability and Complexity||Randomized Algorithms|
|Advanced Algorithms and Data Structures||Machine Learning||Computational Geometry||Approximation Algorithms|
|Year 2||Discrete Optimization||Topics in Algorithms and Data Structures||Thesis|
|Algorithm Engineering||Project or elective course|