Compulsory tasks
š Documents
Course documents and compulsory task files
š Compulsory Tasks
Input data to compulsory computational tasks
ā
Solutions
Example input data with solutions
Solution to the compulsory analysis task
Solutions to compulsory computational tasks
š¢ Other
Announcements
My Compulsory Solutions (Michal Piecuch)
š Lecture Slides
All 201 lecture slides organized by lecture
š” Concept Index
Quick reference to key concepts with direct slide links
0
ā¼
1
Correctness of Algorithms
6 concepts
01 āļø Algorithm Correctness
Logic requirements: Total correctness = Partial + Stop property
L1 ā¢ Slide 1-302 š Specification Role
Contents and role: Input/Output conditions defining the computational task
L1 ā¢ Slide 4-1003 ā Total vs Partial Correctness
Partial: if stops, then correct. Total: stops AND correct.
L1 ā¢ Slide 1204 š Stop Property
Proof of termination (necessary for Total Correctness)
L1 ā¢ Slide 10, 1505 š Loop Invariant
Properties: Initialization, Maintenance, and Termination
L1 ā¢ Slide 12-1906 š Linear Search Invariant
[COMPULSORY] Example of proving correctness via invariants
L1 ā¢ Slide 20 ā Exam Compulsory
ā¼
2
Complexity of Algorithms
5 concepts
06 š Time & Space Complexity
[COMPULSORY] Resource usage (pessimistic, average) relative to input n
L2 ā¢ Slide 27-31 ā Exam Compulsory07 āļø Complexity Analysis
Determining complexity: identifying dominating operations and data size
L2 ā¢ Slide 28-3108 š Asymptotic Notation
[COMPULSORY] Big O, Ī©, Ī, o, Ļ: definitions, role, and usage
L2 ā¢ Slide 36-39 ā Exam Compulsory09 š Function Ranks
[COMPULSORY] Comparing ranks: log n < power < exp < factorial
L2 ā¢ Slide 41 ā Exam Compulsory
ā¼
3
Searching
8 concepts
10 š Sequential Search
Idea and complexity of linear search on unsorted data
L3 ā¢ Slide 4311 āļø Skipping Algorithm
Role of k parameter: how k influences time complexity
L3 ā¢ Slide 4612 š Binary Search
[COMPULSORY] O(log n) search in sorted sequences; exact simulation expected
L3 ā¢ Slide 48-54 ā Exam Compulsory13 š Selection Problem
Finding k-th smallest element; naive vs optimized approaches
L3 ā¢ Slide 5514 š Tournament Method
Finding Min & Max simultaneously with optimal comparisons
L3 ā¢ Slide 5615 āļø Partition Function
[COMPULSORY] Array partitioning around pivot; simulation variant is key
L3 ā¢ Slide 60 ā Exam Compulsory16 š¬ Hoare's QuickSelect
Expected O(n) selection using randomized partition technique
L3 ā¢ Slide 62
ā¼
4
Sorting (Part 1)
5 concepts
17 šÆ Selection Sort
[COMPULSORY] O(nĀ²) sorting; repeatedly finding minimum
L4 ā¢ Slide 67-70 ā Exam Compulsory18 ā”ļø Insertion Sort
[COMPULSORY] O(nĀ²) worst, O(n) best; builds sorted portion
L4 ā¢ Slide 72-76 ā Exam Compulsory19 š Merge Sort & Function
[COMPULSORY] O(n log n) stable sort; exact merge simulation expected
L4 ā¢ Slide 78-82 ā Exam Compulsory20 š Sorting Linked Lists
Comparing sorting efficiency on arrays vs linked segments
L4 ā¢ Slide 85
ā¼
5
Sorting (Part 2)
6 concepts
21 āļø Stability in Sorting
Preserving relative order; knowing which algorithms are stable
L5 ā¢ Slide 9122 ā” QuickSort
Fast expected O(n log n); uses Partition as subroutine
L5 ā¢ Slide 92-10323 š Complexity Limit Ī©(n log n)
Theoretical lower bound for comparison-based sorting
L5 ā¢ Slide 104-10524 š¢ CountSort
[COMPULSORY] O(n+k) non-comparison sort; exact phase simulation expected
L5 ā¢ Slide 106-107 ā Exam Compulsory25 š¢ RadixSort
[COMPULSORY] Digit-by-digit sorting using stable subroutine
L5 ā¢ Slide 108-109 ā Exam Compulsory
ā¼
7
Abstract Data Structures
6 concepts
26 šļø ADT Definition
Logical model of data (Specification) vs Concrete Data Structure
L7 ā¢ Slide 11227 š List Variants
Singly, Doubly, and Cyclic linked lists; properties/complexities
L7 ā¢ Slide 113-11828 š Arrays vs Linked Lists
Detailed complexity comparison of basic operations
L7 ā¢ Slide 11329 š Linear Structures
Stack (LIFO), Queue (FIFO), Deque; efficient array/list implementations
L7 ā¢ Slide 121-12530 š Amortized Analysis
Aggregate, Accounting, and Potential methods
L7 ā¢ Slide 126-13331 š Dynamic Arrays
[ADVANCED] Doubling strategy and amortized insert complexity
L7 ā¢ Slide 135
ā¼
8
Priority Queue
6 concepts
32 š³ Binary Tree Basics
Nodes vs height; level properties and complete/full tree definitions
L8 ā¢ Slide 14833 ā Priority Queue ADT
Concept, definition, and efficient implementations vs naive ones
L8 ā¢ Slide 146-14734 š³ Binary Heap
[COMPULSORY] Implementation as array; complexity of Sift-Up/Down
L8 ā¢ Slide 150-153 ā Exam Compulsory35 ā Heap Operations
[COMPULSORY] Insertion, delMin, and BuildHeap (O(n)) procedures
L8 ā¢ Slide 154-162 ā Exam Compulsory36 ā” HeapSort
[COMPULSORY] In-place O(n log n) sorting using the heap build/extract process
L8 ā¢ Slide 163-165 ā Exam Compulsory37 š² Binomial Heap
[OPTIONAL] Advanced heap variants for fast forest merging
L8 ā¢ Slide 166-168
ā¼
9
Dictionary
8 concepts
38 š Dictionary ADT
Concept, definition, and comparison of naive vs hash implementations
L9 ā¢ Slide 170-17139 #ļøā£ Hash Tables
Collision handling: Chaining vs Open Addressing (Linear Probing)
L9 ā¢ Slide 172-17840 š² Binary Search Tree
[COMPULSORY] BST property; exactly simulating Search/Insert/Delete
L9 ā¢ Slide 180-184 ā Exam Compulsory41 š BST Traversal
Inorder, Preorder, Postorder; producing sorted output from BST
L9 ā¢ Slide 18542 āļø AVL Trees
AVL Balance Factor and idea of rotations for self-balancing
L9 ā¢ Slide 188-19243 š“ā« Red-Black Trees
Binary balance through node coloring and rotation rules
L9 ā¢ Slide 193-19744 š B-Trees
Multi-way balanced search trees for external storage caching
L9 ā¢ Slide 198-20045 š Self-organising Trees
[OPTIONAL] Heuristic-based tree adjustment (Splay Trees)
L9 ā¢ Slide 201š Additional Non-Compulsory Tasks
Extra practice materials and example solutions
Additional Non-compulsory example computational tasks
Solutions to additional non-compulsory example tasks
š§ ASD Knowledge Quiz
Test your understanding of algorithms and data structures
Ready to test your skills?
35+ questions covering all 8 lectures (randomized each time)