Algorithms and Data Structures, MSc (Summer University)
This course provides the basic algorithmic tools indispensable for every software developer.
Computers help us compute things: To sort alphabetically the entries in a telephone directory; to compute the next frame of a video game; to find the seats available on an airplane. However, there are faster and slower ways to compute things. To be an effective programmer, you must know not only how to make a computer compute things, but how to efficiently compute things.
This course provides the basic algorithmic tools indispensible for every software developer.Topics covered are among others complexity analysis, big-O, algorithmic problem solving techniques including divide-and-conquer, concrete algorithms and data structures for search trees, sorting, hashing, graphs, shortest paths.
Basic ability to program in some imperative programming language (Java, Python, C/C++/C#, etc.), using conditions, loops, arrays, methods/procedures/functions, simple recursion and abstract data types (interfaces).
This is normally obtained by following the first semester undergraduate course Introduction to Data Science and Programming (BSc DS), Introductory Programming (BSc SWU or MSc SD), or a similar course. Knowledge of basic mathematical concepts like: sets, functions, graphs, and trees, arithmetic and geometric series. You are expected to know this from your high school education. We will make up for any lacks in that respect on the way.
The student must always meet the admission requirements of the IT University.
Intended learning outcomes
After the course, the student should be able to:
- Discuss and clearly explain the mechanics of computations and data structures involving manipulation of references, nested loops and recursion, specified in natural language, in abstract pseudocode or in concrete programming language (Java/Python)
- Implement abstractly specified computations and data structures in an imperative programming language (Java/Python).
- Analyze time and space usage of algorithms/programs
- Assess scalability of a given single-threaded software application, using asymptotic analysis.
- Choose among and make use of the most important algorithms and data structures in libraries, based on knowledge of their complexity.
- Design algorithms for ad hoc problems by using and combining known algorithms and data structures
- Describe the most important hardware and programming language factors influencing the speed at which a program runs and take them into account in assessment of speed of algorithms.
We will spend 18 hours a week on lectures and exercises. You are expected to work systematically. The course gives plenty of opportunities to gain hands-on experience with solving problems, with implementing algorithms and with using them.
The course literature is published in the course page in LearnIT.
Student Activity BudgetEstimated distribution of learning activities for the typical student
- Preparation for lectures and exercises: 10%
- Lectures: 20%
- Exercises: 20%
- Assignments: 30%
- Exam with preparation: 15%
- Other: 5%
Ordinary examExam type:
A: Written exam on premises, External (7-point scale)
A33: Written exam on premises on paper with restrictions
Written and printed books and notes