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
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
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
- Natural-language steps; flowchart; pseudocode; state transitions; precondition/postcondition; loop invariant; termination
- 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
- Time/space complexity; best/average/worst case; asymptotic notation O, Ξ©, Ξ; lower/upper bounds
- 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
- Array; dynamic array; linked list; singly/doubly/circular list; stack; queue; deque; priority queue
- 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
- Tree; binary tree; binary search tree; AVL/red-black tree; heap; trie; B/B+ tree; segment tree; Fenwick tree
- 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
- Directed/undirected; weighted/unweighted; adjacency matrix/list; edge list; degree; path; cycle; connectivity
- 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
- Linear/binary search; hash-based lookup; interpolation and indexed search concepts
- 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
- Brute force; divide-and-conquer; greedy; dynamic programming; backtracking; branch-and- bound
- 9
Special algorithmic problems
- 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
- String matching; edit distance; suffix arrays/trees; compression; parsing; scheduling; routing; knapsack; subset sum
- 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
- Induction; loop invariants; invariants for data structures; proof of termination; refinement; model checking overview
- 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
- P, NP, NP-completeness, NP-hardness; reductions; undecidability; parameterized complexity
