Course 2024-2025 a.y.

Basics
– Asymptotic notation
– Sorting
– Searching

Data structures
– Arrays, lists, stacks, queues
– Heaps
– Binary trees

Graphs
– BFS, DFS
– Shortest paths: Dijkstra, Bellman–Ford

– Network flows

Algorithm design techniques
– Dynamic programming
– Greedy approach
– Linear programming

Hardness
– P versus NP, Cook–Levin theorem
– Proving NP-hardness with polynomial-time reductions

• describe classic algorithms and algorithm design techniques;
• analyse correctness and efficiency of algorithms;
• define basic concepts from computational complexity;
• understand sources of hardness of computational problems.

• implement algorithms covered in class;
• model problems stated in natural language as formal computational problems;
• design and implement algorithms, and analyse their correctness and efficiency;
• test, debug, and optimize implementations of algorithms.

• Lectures
• Practical Exercises
• Individual works / Assignments
• Collaborative Works / Assignments

Homework exercises will involve designing and analysing algorithms for posted problems. For some of them, you will present your solutions oraly in class, for others you will write them down and get feedback on your writing. Some of these exercises will be individual, on some of them you will be able to work in small teams.

There will be also individual programming assignments that involve implementing algorithms learned in class. You will submit your programs via an online system (Gradescope) that will provide you with live feedback.

There will be no midterm, and the single final exam will not distinguish between attending and non-attending students. However, throughout the semester you will have opportunities to collect points for assignments and active participation, and some of those opportunities might be available only if you are present in class. Collecting points is not mandatory. Each point guaranteess one percent of the final grade and decreases the contribution of the final exam by one percent. For instance, if you collect 40 points during the semester, your final grade (on the scale from 0 to 100) will be calculated as 40 + 0.6 * [exam-result].

The exam and assignments will test your understanding of basic concepts presented in class, and your ability to apply those concepts to new problems, explain and implement proposed solutions, and analyse their correctness and efficiency.
 

The main textbook for the course is:

– T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 3rd edition.

It contains a very formal exposition of almost all the material we are going to cover during the course, and much much more. You are going to get references to relevant fragments in the 3rd edition, but if you happen to have access to any other edition, feel free to use it instead (and just keep in mind that chapters and sections may have different numbers).

Other textbooks – which cover many of these topics and present them in a different style that some of you may prefer – include:

– S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani, Algorithms, McGraw-Hill, 2008.

– J. Erickson. Algorithms. 2019. URL: http://jeffe.cs.illinois.edu/teaching/algorithms/.

Additional materials – e.g., research papers, technical reports, notes – will be posted on Blackboard throughout the semester.