For every topic here, identify the problem being solved, how the data is represented, which operations are actually performed, and what condition defines correctness. Then discuss how time and space requirements grow as input size increases. A data structure is best learned through its main operations and trade-offs; an algorithm is best learned by tracing it on a small input, and only afterward memorizing its complexity.
A. Algorithm Properties and Asymptotic Analysis
An algorithm is a finite, unambiguous procedure for solving a class of problems, and useful design criteria include correctness (it produces the right answer), finiteness (it terminates), definite steps (each step is unambiguous), well-defined valid inputs and outputs, and resource efficiency. Algorithms can be represented as pseudocode, flowcharts, or actual code, and the right representation depends on input size, required speed, available memory, and the specific constraints of the problem. Example: two algorithms can produce the exact same sorted output, yet one may scale far better than the other as the input list grows larger — correctness alone does not tell you which one to actually use in practice.
Algorithm analysis estimates how time and memory requirements grow as input size (n) increases, and asymptotic notation focuses specifically on this rate of growth rather than machine-specific timing in seconds. Big-O gives an upper bound on growth in common usage; Θ (theta) expresses a tight bound (both upper and lower); Ω (omega) gives a lower bound — and as n grows very large, constant factors matter much less than which growth class an algorithm actually belongs to. Example: a single loop over n items is typically O(n); two nested loops each running n times are typically O(n²); binary search on a sorted, randomly-accessible collection is O(log n) — searching 1,000 sorted items with binary search takes only about ten halving steps, dramatically fewer than checking every item one at a time. The standard growth classes worth being able to compare directly are O(1), O(log n), O(n), O(n log n), O(n²), exponential, and factorial — in that order, from fastest-growing-acceptable to catastrophically slow for large inputs.
B. Abstract Data Types: Lists, Stacks, and Queues
An abstract data type (ADT) defines the allowed operations and expected behaviour of a data structure without forcing any one particular internal representation — the same ADT can be implemented in more than one way, and choosing between implementations is itself a meaningful design decision. A stack is last-in-first-out (LIFO): items are pushed on and popped off from the same end, and its two core operations are push and pop. A queue is first-in-first-out (FIFO): items are enqueued at one end and dequeued from the other. Example: a browser’s back-history behaves like a stack (the most recently visited page is the first one you go back to), while a printer’s job queue behaves like a queue (jobs are printed in the order they were submitted). Lists may be implemented using arrays (contiguous memory, fast indexed access, costly insertion/deletion in the middle) or linked structures (nodes connected by pointers, cheap insertion/deletion, no fast direct indexing) — this array-versus-linked-list trade-off recurs throughout data structures and is worth understanding deeply rather than memorizing as a rule.
C. Searching, Sorting, Hashing, and Recursion
Searching finds a target item; sorting arranges data into order; the right algorithm choice for either depends on data size, existing order, available memory, and what guarantees are actually required. Linear search checks items one at a time, sequentially; binary search repeatedly halves a sorted search range. Bubble sort is simple to understand but inefficient for large data; merge sort runs in O(n log n) by repeatedly merging sorted sublists; quick sort is efficient on average but has a worse worst-case; heap sort uses a heap data structure and also achieves O(n log n) time. Tracing each algorithm by hand on a tiny list, and only then memorizing its complexity class, is far more durable exam preparation than memorizing complexity tables in isolation.
A hash table uses a hash function to map keys directly to storage locations, giving average-case constant-time lookup — dramatically faster than searching through items one by one. Collisions (two different keys hashing to the same location) can be handled with chaining (storing multiple colliding items together at that location) or linear probing (searching forward for the next free location), among other strategies. Example: a phone-book key can be hashed into a specific bucket, and if two different keys happen to collide, both end up stored in the same chain at that bucket.
Recursion solves a problem by having a function call itself on a smaller instance of the same problem, repeating this until a base case is reached that can be answered directly without further recursion. A correct recursive solution absolutely requires both a correct base case and guaranteed progress toward that base case on every recursive call; without both, recursion can run indefinitely or exhaust the call stack (the same call stack introduced in the programming fundamentals section) and crash. Tracing a small recursive example, such as computing a factorial or performing a tree traversal, by hand, step by step, is the most reliable way to actually internalize how recursion unwinds.
D. Trees and Graphs
Trees represent hierarchical relationships; graphs represent more general networks of vertices (nodes) connected by edges. A binary tree allows at most two children per node. A binary search tree (BST) keeps its keys ordered so that searching, insertion, and deletion can all follow a consistent left-or-right comparison rule; an AVL tree adds automatic rebalancing to keep its height controlled as items are inserted or removed, preventing the search-time degradation an unbalanced BST can suffer; a 2-3 tree maintains a balanced multiway structure using a different balancing strategy entirely. Graphs may be directed (edges have a specific direction) or undirected, and weighted (edges carry a cost or distance) or unweighted; the two standard traversal strategies are breadth-first search, BFS (explore level by level, outward from the start), and depth-first search, DFS (follow one path as deep as possible before backtracking). Example: a file-system’s folder structure is naturally viewed as a tree, while a road network connecting cities is naturally represented as a graph, since roads can connect any two cities without a strict hierarchical relationship between them. Balanced trees improve worst-case search depth precisely because they actively prevent the tree from degenerating into something resembling a long, inefficient linked list.
E. Heuristic Search, Genetic Algorithms, and Encryption Basics
Heuristic search uses problem-specific guidance to explore promising states first, rather than blindly examining every possibility in an unordered way — a heuristic is simply an estimate of how close a given state is to the goal, and it can dramatically speed up a search, though it does not guarantee finding the absolute best answer unless both the algorithm and the specific heuristic satisfy certain required conditions. Example: a route-finding algorithm can prioritize exploring cities that appear closer to the destination, rather than exploring every possible route with equal priority, which is exactly the intuition behind best-first and A*-style search. Genetic algorithms imitate biological selection, crossover, and mutation to search a solution space, following a repeating cycle: population, then fitness evaluation, then selection of the fittest, then crossover (combining solutions) and mutation (introducing small random changes), producing a new generation — it is important to remember these are stochastic optimization methods inspired by evolution, not literal biological processes.
Encryption transforms readable data (plaintext) into unreadable ciphertext using a cryptographic algorithm and a key. DES (Data Encryption Standard) is a historical symmetric block cipher, meaning both encryption and decryption use the same shared secret key; DES is no longer considered secure for modern protection because its effective key size is too small for today’s computing power, though it remains genuinely useful for understanding how block ciphers work conceptually. RSA is a public-key (asymmetric) algorithm based on modular arithmetic and the computational difficulty of factoring very large integers; asymmetric cryptography uses a mathematically related pair of keys — a public key that can be shared openly, and a private key that must be kept secret — with which key does which job (encrypting versus decrypting, or signing versus verifying) depending on whether the specific use case is confidentiality or authentication.
Algorithms and Data Structures key takeaways: always identify the problem, data representation, operations, and correctness condition before analyzing growth rate. Big-O, Θ, and Ω describe upper, tight, and lower growth bounds respectively, and constant factors matter far less than growth class for large inputs. Stacks (LIFO) and queues (FIFO) are opposite access disciplines built from the same underlying list concept. Hash tables trade the possibility of collisions for average-case constant-time access. Recursion always needs both a correct base case and guaranteed progress toward it. Balanced trees actively prevent the search-time degradation an unbalanced tree can suffer. Heuristic search trades a guarantee of optimality for speed, under specific conditions. DES is a historically important but now insecure symmetric cipher; RSA’s asymmetric key pair solves a fundamentally different problem than any symmetric cipher can.