Algorithms for Data Science 2400-DS1AL
1. Introduction
-- Programming languages that we will be using
-- How to learn algorithmics by yourself
-- An example algorithm
-- Correctness of algorithms: stop condition and loop invariants
2. Basic Definitions
-- Computational model: random access machine
-- Computational problems
-- Computational complexity and asymptotic notation
3. Analysis of Algorithms
4. Divide and Conquer
-- Master theorem
5. Classical Sorting Algorithms
-- Data structure: heap
6. Dynamic Programming
7. Dictionaries
-- Arrays and lists
-- Balanced binary search trees
-- Hash tables
8. Graphs
-- Definition and applications
-- Breadth/depth first search
-- Minimum spanning trees
-- Dijkstra's algorithm
-- Floyd-Warshall algorithm
-- Kruskal's algorithm
-- Data structures: stack, queue, priority queue
-- Data structure: find&union
9. Hard Problems
-- The most important complexity classes: P, NP
-- Reductions and NP-hardness
-- Examples of NP-hard problems
-- Solving hard problems
Type of course
Course coordinators
Learning outcomes
After this course the student:
- has basic knowledge in the theory of algorithms and data structures
- knows how to design own algorithms, prove their correctness, and estimate their computational complexity
- understands the importance of using appropriate data structures and efficient algorithms
- is able to apply this knowledge in practice, by choosing the most appropriate data structures and algorithmic methods for given situations and by using them in own project.
Assessment criteria
The final grade is a weighted average of the grades from the written exam, the programming tasks, and the short tests. To pass the course (exam and exercise classes), the student has to gain at least 50% of the points from the programming tasks and the short tests as well as 50% of the points from the exam.
The participation in the exercise classes is obligatory where two excused absences are allowed.
Bibliography
Recommendations:
- Cormen T.H, Leiserson Ch.E, Rivest R.L, Stein C. Introduction to algorithms. The MIT Press.
- Banachowski L., Diks K., Rytter W. Algorytmy i struktury danych. WNT, 2011.
Additional information
Additional information (registration calendar, class conductors, localization and schedules of classes), might be available in the USOSweb system: