Skip to content

University Computing Flashcards: Algorithms and Data Structures

Computing — Algorithms and Data Structures Flashcards

20 interactive flashcards for university-level Algorithms and Data Structures. Press Space to flip, rate 1-4.

Additional Flashcard Topics

  • Sorting Algorithms: bubble sort O(n²), merge sort O(n log n), quicksort O(n log n) average, heapsort O(n log n). Stable sorts preserve relative order of equal elements. In-place sorts use O(1) extra space.

  • Search Algorithms: linear search O(n), binary search O(log n) on sorted arrays, hash table O(1) average. Binary search requires sorted data; hash tables require good hash functions.

  • Graph Algorithms: BFS (level-by-level), DFS (depth-first), Dijkstra’s (shortest path), Kruskal’s/Prim’s (MST). BFS uses a queue; DFS uses a stack (or recursion).

  • Dynamic Programming: solve subproblems once and store results. Optimal substructure + overlapping subproblems = DP candidate. Bottom-up (tabulation) vs top-down (memoisation).

  • Greedy Algorithms: make locally optimal choices hoping for global optimum. Greedy works when the problem has matroid structure (e.g., activity selection, Huffman coding).

  • Divide and Conquer: split problem into subproblems, solve independently, combine results. Master theorem solves recurrences: T(n) = aT(n/b) + O(n^d).

Intuition

Data structures are organised ways to store and access data. The choice of data structure determines the efficiency of operations, a linked list is great for insertion but poor for random access; an array is the opposite.

Array vs linked list intuition: Arrays give O(1) random access but O(n) insertion (shifting elements). Linked lists give O(1) insertion at a known position but O(n) access (traversal). Use arrays when you need fast lookups; use linked lists when you need frequent insertions/deletions.

Tree intuition: Binary search trees maintain sorted order while allowing O(log n) search, insert, and delete, if the tree is balanced. An unbalanced BST degenerates into a linked list with O(n) operations. Self-balancing trees (AVL, Red-Black) guarantee O(log n) by restructuring after each modification.

Hash table intuition: Hash tables map keys to array indices using a hash function. Average-case O(1) operations depend on a good hash function that distributes keys uniformly. Collisions (two keys mapping to the same index) degrade performance, chaining and open addressing are two resolution strategies.

Key Concepts

ConceptWhy It Matters
Asymptotic analysisDescribes how runtime scales with input size; the basis for algorithm comparison
Amortised analysisAverages cost over a sequence; explains why dynamic array append is O(1) on average
Balanced treesGuarantee O(log n) by maintaining height invariants through rotations
Hash tablesAverage O(1) lookup; trade space for time; collision strategy matters
Priority queuesEnables efficient access to min/max element; heaps implement this in O(log n)

Common Pitfalls

Assuming average-case complexity. Big-O without qualification means worst case. An algorithm with O(n) worst case may have O(n²) average case if the input distribution is adversarial.

Ignoring cache performance. A theoretically optimal algorithm may perform worse than a simpler one on real hardware if it has poor cache locality. Accessing elements scattered across memory causes cache misses that dominate runtime.

Confusing stability with correctness. A stable sort preserves the relative order of equal elements. Stability matters when sorting by multiple criteria but does not affect correctness of a single sort.

Forgetting that hash table performance depends on the hash function. A poor hash function clusters keys, degrading O(1) to O(n). The worst case for hash tables is O(n) per operation.

Confusing BFS with DFS. BFS explores level-by-level (queue); DFS explores depth-first (stack). BFS finds shortest paths in unweighted graphs; DFS is useful for cycle detection and topological sorting.

Cross-References