Computer Β· Part C - Software, Algorithms and Computation Β· Major topic 9 of 39

Algorithms and Data Structures

Correct, efficient procedures and the structures used to organize information.

176 items insideAsked 1Γ— in the RPSC/RSSB papers we analysed, most recently 2013COM-09

Also look at: Science & Technology: Computer Architecture, Operating Systems, Programming and Software SystemsScience & Technology: Mathematics, Statistics and Data Foundations

  1. 1

    Historical evolution β€” key dates

    • Euclid’s algorithm gives a classic finite procedure.c. 300 BCE
    • Formal computation models define algorithms and limits of mechanical procedure.1930s
    • Numerical algorithms and sorting/searching are studied for electronic computers.1940s-1950s
    • Algorithm analysis, graphs, dynamic programming and complexity theory mature.1960s-1970s
    • Randomized, approximation, online and distributed algorithms expand the toolkit.1980s-2000s
    • Algorithms for massive data, deep learning, privacy, fairness and accelerated hardware gain importance.2010s-2020s
  2. 2

    Algorithm description

    • Natural-language steps; flowchart; pseudocode; state transitions; precondition/postcondition; loop invariant; termination
      7 more points
      • Natural-language steps
      • Flowchart
      • Pseudocode
      • State transitions
      • Precondition/postcondition
      • Loop invariant
      • Termination
    • Input domain; output contract; edge cases; correctness proof; trace; counterexample
      6 more points
      • Input domain
      • Output contract
      • Edge cases
      • Correctness proof
      • Trace
      • Counterexample
  3. 3

    Complexity analysis

    • Time/space complexity; best/average/worst case; asymptotic notation O, Ξ©, Θ; lower/upper bounds
      4 more points
      • Time/space complexity
      • Best/average/worst case
      • Asymptotic notation O, Ξ©, Θ
      • Lower/upper bounds
    • Constant/logarithmic/linear/linearithmic/quadratic/exponential/factorial growth; amortized analysis
      2 more points
      • Constant/logarithmic/linear/linearithmic/quadratic/exponential/factorial growth
      • Amortized analysis
    • Recurrence relations; substitution; recursion tree; Master theorem; potential method
      5 more points
      • Recurrence relations
      • Substitution
      • Recursion tree
      • Master theorem
      • Potential method
  4. 4

    Linear structures

    • Array; dynamic array; linked list; singly/doubly/circular list; stack; queue; deque; priority queue
      8 more points
      • Array
      • Dynamic array
      • Linked list
      • Singly/doubly/circular list
      • Stack
      • Queue
      • Deque
      • Priority queue
    • Static vs dynamic storage; indexing; traversal; insertion/deletion; iterator and invalidation
      5 more points
      • Static vs dynamic storage
      • Indexing
      • Traversal
      • Insertion/deletion
      • Iterator and invalidation
  5. 5

    Hierarchical and associative structures

    • Tree; binary tree; binary search tree; AVL/red-black tree; heap; trie; B/B+ tree; segment tree; Fenwick tree
      9 more points
      • Tree
      • Binary tree
      • Binary search tree
      • AVL/red-black tree
      • Heap
      • Trie
      • B/B+ tree
      • Segment tree
      • Fenwick tree
    • Hash table; hash function; collision handling; open addressing; chaining; load factor; bloom filter
      7 more points
      • Hash table
      • Hash function
      • Collision handling
      • Open addressing
      • Chaining
      • Load factor
      • Bloom filter
    • Disjoint-set union; union-find; path compression; union by rank/size
      4 more points
      • Disjoint-set union
      • Union-find
      • Path compression
      • Union by rank/size
  6. 6

    Graphs

    • Directed/undirected; weighted/unweighted; adjacency matrix/list; edge list; degree; path; cycle; connectivity
      8 more points
      • Directed/undirected
      • Weighted/unweighted
      • Adjacency matrix/list
      • Edge list
      • Degree
      • Path
      • Cycle
      • Connectivity
    • BFS; DFS; topological sorting; shortest path; minimum spanning tree; strongly connected components; flow/cut; matching
      8 more points
      • BFS
      • DFS
      • Topological sorting
      • Shortest path
      • Minimum spanning tree
      • Strongly connected components
      • Flow/cut
      • Matching
    • Dijkstra; Bellman-Ford; Floyd-Warshall; Kruskal; Prim; max-flow families; graph colouring
      7 more points
      • Dijkstra
      • Bellman-Ford
      • Floyd-Warshall
      • Kruskal
      • Prim
      • Max-flow families
      • Graph colouring
  7. 7

    Searching and sorting

    • Linear/binary search; hash-based lookup; interpolation and indexed search concepts
      3 more points
      • Linear/binary search
      • Hash-based lookup
      • Interpolation and indexed search concepts
    • Bubble, selection, insertion, merge, quick, heap, counting, radix and bucket sort.
    • Stability; in-place vs out-of-place; comparison lower bound; external sorting; streaming selection
      5 more points
      • Stability
      • In-place vs out-of-place
      • Comparison lower bound
      • External sorting
      • Streaming selection
  8. 8

    Algorithm design paradigms

    • Brute force; divide-and-conquer; greedy; dynamic programming; backtracking; branch-and- bound
      6 more points
      • Brute force
      • Divide-and-conquer
      • Greedy
      • Dynamic programming
      • Backtracking
      • Branch-and- bound
    • Randomized; approximation; online; streaming; local search; branch prediction-aware design; parallel algorithms
      7 more points
      • Randomized
      • Approximation
      • Online
      • Streaming
      • Local search
      • Branch prediction-aware design
      • Parallel algorithms
  9. 9

    Special algorithmic problems

    Asked 1Γ— Β· last 2013

    • String matching; edit distance; suffix arrays/trees; compression; parsing; scheduling; routing; knapsack; subset sum
      9 more points
      • String matching
      • Edit distance
      • Suffix arrays/trees
      • Compression
      • Parsing
      • Scheduling
      • Routing
      • Knapsack
      • Subset sum
    • Numerical methods; geometric algorithms; computational biology; recommender systems; graph mining
      5 more points
      • Numerical methods
      • Geometric algorithms
      • Computational biology
      • Recommender systems
      • Graph mining
  10. 10

    Correctness and verification

    • Induction; loop invariants; invariants for data structures; proof of termination; refinement; model checking overview
      6 more points
      • Induction
      • Loop invariants
      • Invariants for data structures
      • Proof of termination
      • Refinement
      • Model checking overview
    • Property-based testing; fuzzing; differential testing; metamorphic testing; adversarial inputs
      5 more points
      • Property-based testing
      • Fuzzing
      • Differential testing
      • Metamorphic testing
      • Adversarial inputs
  11. 11

    Advanced theory and research

    • P, NP, NP-completeness, NP-hardness; reductions; undecidability; parameterized complexity
      4 more points
      • P, NP, NP-completeness, NP-hardness
      • Reductions
      • Undecidability
      • Parameterized complexity
    • Randomized complexity; approximation ratios; online competitive analysis; fine-grained complexity; quantum algorithms
      5 more points
      • Randomized complexity
      • Approximation ratios
      • Online competitive analysis
      • Fine-grained complexity
      • Quantum algorithms