← Back to Dashboard

📚 ASD Exam Topics

Compulsory & Non-Compulsory Topics for the 2025/2026 Exam

Based on Course Announcements
⚠️

Important: Solve computational tasks with exactly the algorithm variants from the lecture slides. These exact variants will be expected on the exam.

⭐

Compulsory Algorithms (Part A - Computational)

Exam Format

About 7 simple computational tasks on Gakko. Simulate algorithms on small input data. You must pass ~50% (4/7) to pass this module.

🔍 Binary Search

Search in a sorted sequence by repeatedly dividing the search interval in half.

Lecture 3

🔄 Partition Function

Rearrange elements around a pivot: smaller left, larger right.

Lecture 3

📊 Selection Sort

Find minimum, swap to front, repeat for remaining elements.

Lecture 4

📥 Insertion Sort

Build sorted array one element at a time by inserting into correct position.

Lecture 4

🔀 Merge Sort & Merge Function

Divide, sort halves recursively, merge. Know the Merge function specifically.

Lecture 4

#️⃣ CountSort

Count occurrences of each value, place elements in order. Non-comparison sort.

Lecture 5

🔢 RadixSort

Sort digit by digit using a stable sort (like CountSort) on each position.

Lecture 5

🌳 Binary Heap Operations

Insert (sift-up), DeleteMin (sift-down), BuildHeap, HeapSort.

Lecture 8

🌲 BST Operations

Search, Insert, Delete in a Binary Search Tree.

Lecture 9
✅

Compulsory Topics (Part B - Theory)

What to Expect

Definitions, asymptotic notation, specifications, complexity analysis, code analysis, simple pseudocode writing.

📋 Specification

Initial condition, final condition, and the role of specification in algorithms.

Lecture 1

✔️ Correctness

  • Total Correctness
  • Partial Correctness
  • Stop Property
  • Proving correctness for simple algorithms
Lecture 1

🔁 Loop Invariant

Definition, how to identify and use for proving partial correctness.

Lecture 1

⏱️ Time & Space Complexity

  • Pessimistic (worst-case)
  • Average case
  • Dominating operations
  • Data size
Lecture 2

📈 Asymptotic Notation

  • Big O, Big Θ, Big Ω
  • Lowercase o, ω
  • Definitions & interpretation
  • Comparing ranks (log, polynomial, exponential, factorial)
Lecture 2

🔍 Searching Algorithms

  • Sequential Search
  • Skipping Algorithm (role of k parameter)
  • Binary Search (specification, properties)
  • Role of sortedness
Lecture 3

🔄 Sorting Problem

  • Stability (which sorts are stable?)
  • Complexity limit of comparison sorting
  • Compare all sorting algorithms
Lectures 4-5

📦 Concrete Data Structures

  • Arrays
  • Linked Lists (single, double, cyclic)
  • Complexity comparison
Lecture 7

🗃️ Abstract Data Structures

  • Stack, Queue, Deque (definition, applications)
  • Efficient implementations on array/list
  • Complexities
Lecture 7

🌳 Binary Tree

Definition, properties, relationship between nodes and height, applications.

Lecture 8

📊 Priority Queue

  • Definition & applications
  • Binary Heap (properties, array implementation)
  • Upheap/Downheap operations
Lecture 8

📖 Dictionary

  • Hash Table (concepts, collision handling)
  • BST (definition, properties)
  • AVL (definition, balance factor, rotation idea)
Lecture 9
⚡

Non-Compulsory Topics (For Grades > 4.0)

Optional Exam

Students who pass Part 1 can take a non-compulsory exam for grades higher than 4.0. These topics may appear there.

📐 Dynamic Arrays

Unbounded arrays with doubling strategy, amortized O(1) insert.

Lecture 7

⏳ Amortized Time Complexity

Aggregate, Accounting, and Potential methods.

Lecture 7

#️⃣ Universal Hashing

Randomized hash function families for guaranteed expected performance.

Lecture 9

✨ Perfect Hashing

Two-level hashing for O(1) worst-case lookups with static data.

Lecture 9

🔓 Open Hashing (Details)

Linear probing, quadratic probing, double hashing details.

Lecture 9

🌲 Splay Trees

Self-adjusting binary search trees with amortized O(log n) operations.

Lecture 9

🔄 Self-Organizing Trees

Trees that reorganize based on access patterns.

Lecture 9

🌿 Binomial Heap

Heap structure supporting O(log n) merge. Only for grades > 4.

Lecture 8