Romania Clasa a XI-a Computer Science (intensive informatics)

Chapters: 5

1. Dynamic data structures

Dynamically allocated structures

Linked Lists – A linked list stores items in nodes. Each node holds data and a pointer (the address of the next node). A variable called head points to the first node; the last node points to NULL. Nodes can sit anywhere in memory, so adding or removing at the front takes only a pointer change, but finding the k-th item means walking from the head.

Terminology and special graphs · Graph algorithms

Graph Theory: Dots, Lines and Networks – A graph is a set of vertices (dots) joined by edges (lines). The degree of a vertex is how many edges touch it, and the sum of all degrees is twice the number of edges. An Euler trail uses every edge once and exists only when 0 or 2 vertices have odd degree. A tree is a connected graph with no cycles and n − 1 edges. Weighted graphs model roads and networks; Kruskal’s and Prim’s algorithms find a minimum spanning tree.
Graph Algorithms – A graph is a set of vertices joined by edges, which can carry weights. Breadth-first search (BFS) explores in layers using a queue and finds the fewest-edge path. Depth-first search (DFS) goes deep using a stack or recursion and backtracks. Trees can be traversed pre-order, in-order and post-order. Dijkstra's algorithm finds shortest paths from one vertex when weights are non-negative. Kruskal's and Prim's algorithms build a minimum spanning tree. Route inspection finds the shortest closed route using every edge; the travelling salesperson problem asks for the shortest tour of every vertex. In a flow network, the maximum flow equals the capacity of the minimum cut.

Rooted and binary trees

Trees in Data Structures: Binary Trees and Binary Search Trees – A tree stores data in nodes joined by edges, like a family tree turned upside down. The top node is the root, nodes with no children are leaves. A tree with n nodes has n − 1 edges. Depth of a node is its distance (in edges) from the root; height of the tree is the longest root-to-leaf path. In a binary tree every node has at most two children. A binary search tree (BST) keeps smaller keys on the left and bigger keys on the right, so searching skips half the tree at each step. Traversals visit every node: pre-order (root, left, right), in-order (left, root, right) and post-order (left, right, root). In-order on a BST gives sorted output.

Greedy, backtracking, divide and conquer, dynamic programming

Dynamic Programming – Dynamic programming (DP) solves a big problem by solving each smaller subproblem only once and saving the answer. It works when subproblems overlap and the best answer is built from best answers of smaller parts (optimal substructure). Top-down DP is memoization; bottom-up DP fills a table. DP often turns exponential time into polynomial time.

OOP basics

Object-Oriented Programming (OOP) – Object-oriented programming builds a program out of objects. A class is a blueprint that lists the data (attributes) and actions (methods) its objects will have. Each object is made from a class and keeps its own data. The four big ideas are encapsulation (hide data behind methods), inheritance (a new class reuses an old one), polymorphism (the same method call behaves in the right way for each object) and abstraction (show only what is needed).