Algorithms and Data Structures
The course creates a shared algorithmic framework, frames data structures as architectural building blocks, and fosters a culture of formal reasoning and proof. It builds the groundwork for advanced studies in software engineering and AI, guiding students from intuitive coding to structured engineering thinking.
This course delivers fundamental knowledge of data structures and algorithms as the architectural building blocks of software. It emphasises task formalisation, complexity analysis, and smart decision‑making for scalable system design.
Combining theory with hands‑on practice, the course leverages the LLM (Large Language Model) to assess formalisation skills, generate practice tasks and counterexamples, check description completeness and analyse complexity, simulate how algorithms run and how structures degrade with growing data.
Through practical assignments, students learn to formalise tasks of various natures and refine them based on feedback from the LLM, implement algorithms using different data structures, build operation and complexity tables, and justify the choice of structure and strategy for a specific task.
As a result of mastering the discipline, the student must know the concept of an algorithm and its formal properties, abstract data types (ADTs) and their invariants, basic data structures and their asymptotic complexity, fundamental algorithmic strategies, principles of complexity analysis, the role of invariants in proving correctness, and the nature of algorithmic trade‑offs (e.g., time vs. memory).
The student must also be able to formalise a problem as an algorithmic model, select an appropriate data structure for a given task, justify the choice of an algorithmic strategy, evaluate time and space complexity, prove the correctness of an algorithm, critically analyse alternative solutions (including those proposed by LLMs — Large Language Models), and apply formal reasoning to engineering decisions.
Finally, the student must be proficient in methods of algorithmic analysis, skills for well‑reasoned engineering argumentation, the professional culture of working with intelligent assistants (LLMs), and the ability to transition from formalisation to architectural thinking.
OBJECTIVES
Formation of algorithmic autonomy of thinking;
Mastering data structures as architectural primitives of digital systems;
Develop skills in formalizing tasks and proving correctness;
Creating a culture of analyzing the complexity and scalability of solutions;
Mastering the model of conscious interaction with LLM in an engineering context.
KEY TASKS
Formalization of engineering tasks without reference to a specific programming language;
Mastering abstract data types and their implementations;
Analysis of the relationship between the data structure and the algorithmic strategy;
Developing skills to prove the correctness of algorithms;
Develop the ability to critically evaluate solutions, including LLM solutions.
Main topics of the course:
1. Formalisation and State Model: task formulation independent of programming language, concepts of state and constraints, algorithm as a sequence of state transitions.
2. Abstract Data Types (ADT): invariants, distinction between abstraction and implementation, operations as a contract.
3. Basic Data Structures: arrays and linked lists (operation cost), stacks and queues (LIFO/FIFO), sets and hash tables (collisions, memory/time trade‑off).
4. Trees and Heaps: binary search trees (BST), invariants and their preservation, priority queues.
5. Graphs: representation methods (adjacency lists, adjacency matrices), traversals (BFS, DFS), relationship between traversal strategy and data structure.
6. Algorithms through the Prism of Structures: search (linear and binary), sorting (O(n 2 ) vs O(nlogn)), reduction of iterations via hashing and preprocessing.
7. Complexity Analysis and Engineering Reasoning: asymptotics, scalability, time/memory trade‑off, architectural decisions.
8. Proof of Correctness: loop invariants, counterexamples, methods of formal justification.
