Course 2023-2024 a.y.

20873 - ANALYSIS OF ALGORITHMS AND DATA STRUCTURES

Department of Computing Sciences

Course taught in English
Go to class group/s: 31
AI (8 credits - I sem. - OBS  |  INF/01)
Course Director:
ADAM POLAK

Classes: 31 (I sem.)
Instructors:
Class 31: ADAM POLAK


Mission & Content Summary

MISSION

Efficient algorithms and data structures lie at the core of computing. In this course students will get a chance to revise basic and learn advanced algorithms for fundamental computational problems. They will also learn techniques for designing and analysing algorithms, and apply them to new problems.

CONTENT SUMMARY

Dynamic programming for algorithm design

 

Analysis of greedy algorithms

 

Graph algorithms

  • Shortest paths
  • Strong connectivity and biconnectivity
  • Network flows and matchings
  • Modelling computational problems using graphs

 

Data structures

  • Binary search trees
  • Range queries

 

Hardness of computational problems

  • NP-completenes
  • Fine-grained complexity lower bounds

Intended Learning Outcomes (ILO)

KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • describe classic algorithms and data structures;
  • analyse correctness and efficiency of algorithms;
  • define basic concepts from computational complexity;
  • understand sources of hardness of computational problems.
     

APPLYING KNOWLEDGE AND UNDERSTANDING

At the end of the course student will be able to...
  • 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, using basic and advanced algorithmic techniques.

Teaching methods

  • Face-to-face lectures
  • Exercises (exercises, database, software etc.)
  • Individual assignments

DETAILS

Homework exercises will involve designing and analysing algorithms for posted problems. Students will present their solutions in class.

 

There will be also individual programming assignments that involve implementing algorithms learned in class. Students will submit their solutions via an online system that will provide them with live feedback.


Assessment methods

  Continuous assessment Partial exams General exam
  • Written individual exam (traditional/online)
    x
  • Individual assignment (report, exercise, presentation, project work etc.)
x    

ATTENDING AND NOT ATTENDING STUDENTS

There will be a final exam, homework assignments (to be presented in class), and programming assignments. Assignments are not mandatory. The final grade will be calculated by taking for each student the best outcome out of the following two ones:
(a) The final exam, homework assignments, and programming assignments each contribute 33⅓% of the final grade.
(b) The final exam contributes 100% of the final grade.

 

The exam and homework assignments will test the students' understanding of basic concepts presented in class, and their ability to apply learned algorithms and algorithm design techniques to new computational problems stated in natural language, explain and implement proposed solutions, and reason about their correctness and efficiency. The programming assigments will test the students' ability to understand and implement algorithms learned in class.


Teaching materials


ATTENDING AND NOT ATTENDING STUDENTS

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

 

Additional materials – e.g., research papers, technical reports, notes – to be posted on the course website throught the semester.

Last change 30/05/2023 10:42