Course Title: Algorithms and Data Structures I – RI-UNI (Bologna) and RM, 2nd Year

Lecturer: Prof. Dr. Igor Kononenko
Assistants: Dr. Petar Vračar, Dr. Bojan Žunkovič

Course Objectives:

  1. Enhance and solidify programming knowledge (particularly recursion)
  2. Learn to design algorithms and analyze their time complexity
  3. Introduce basic abstract data types and operations on them
  4. Understand basic operations on dynamic data structures: lists, trees, and graphs

Course Outline:

  • Introduction:
    • Course overview
    • Recursion and iteration (taught in advance due to exercises)
    • Algorithm time complexity (asymptotic and actual time)
  • Basic Abstract Data Types and Their Implementations:
    • ADT List
    • ADT Set
    • ADT Stack
    • ADT Queue
  • Recursion and Iteration (already covered due to exercises)
  • Problem Solving with Algorithms
  • Problem Solving
  • Overview of Search Algorithms
  • Divide and Conquer
  • Strategies for Finding Optimal Solutions
  • Strategies for Finding Approximate Solutions
  • Stochastic Search Algorithms
  • Algorithm Development
  • ADT Map, Hash Tables; Skip Lists
  • Trees:
    • Tree as an Abstract Data Type
    • Binary Trees, e.g., Expression Trees (including context-free grammars)
    • ADT Dictionary
    • Binary Search Trees
    • Red-Black Trees
    • AVL Trees
    • B-Trees
    • ADT Priority Queue; Heap
    • Advanced Sorting: Heapsort
    • ADT Disjoint Sets
  • Graph:
    • ADT Graph
    • Critical Path
    • Shortest Path Tree
    • Minimum Spanning Tree
  • Program Correctness Proofs:
    • Loop Invariants
    • Partial and Total Correctness

PRACTICAL EXERCISES

Students complete online quizzes published in the e-learning platform by set deadlines, which are graded. Each student must achieve at least 50% in these quizzes to qualify for an exercise grade.

In laboratory exercises, each student independently completes two seminar tasks, submits them by deadlines via the e-learning platform, and defends them in two sessions during laboratory classes. Seminar task evaluations are graded.

Submitted seminar tasks are cross-checked for plagiarism. Students found plagiarizing (both the original author and the copier) receive a failing grade, are banned from participating in exercises and exams during the current academic year, and are reported to the FRI disciplinary committee for further sanctions (ranging from a ban on all exams for 6–12 months to expulsion from FRI).

Successfully defended seminar tasks (at least 50% grade) submitted by deadlines are a prerequisite for taking the exam. Seminar task grades contribute to the exercise grade, with each task potentially weighted differently. The final course grade is the average of the exercise grade and the exam grade. Both grades must be positive.

The exercise grade is valid only for the current academic year. If a student with a positive exercise grade does not pass the exam within the academic year, their exercise grade expires.

EXAM:

The exam consists of a written and, if necessary, an oral component. During the written exam, one A4 sheet of handwritten notes (written in pencil for erasability) is allowed. The sheet must be signed in pen with the student’s name, surname, and ID number (photocopies or prints are not allowed) and submitted with the written exam. During the oral exam, students can improve or lower their written exam grade.

Both the exercise grade and exam grade must be positive. The final course grade is the average of these two grades.

Core Literature:

Igor Kononenko, Marko Robnik Šikonja, Zoran Bosnić: Programming and Algorithms, FE and FRI Publishing, 2008.

Supplemental Literature:

  • A.V. Aho, J.E. Hopcroft, J.D. Ullman: Data Structures and Algorithms, Addison-Wesley, 1983.
  • J. Kozak: Data Structures and Algorithms, DMFA Slovenia, Ljubljana, 1986.
  • Thomas H. Cormen, Stein Clifford, Charles E. Leiserson, Robert L. Rivest: Introduction to Algorithms, 2nd Edition, The MIT Press, 2001.
  • N. Wirth: Computer Programming Vol. 1 and 2, DMFA, Ljubljana, 1989.
  • Robert Sedgewick: Bundle of Algorithms in Java: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms, Addison-Wesley, 2003.