2.4. Data Structures and Algorithms (DSA)

2.4. Data Structures and Algorithms (DSA)

This area provides the fundamental toolkit for designing and analyzing efficient computational solutions. It covers the theoretical foundations of algorithm complexity, the practical implementation of fundamental and advanced data structures, and the design principles behind efficient algorithms for searching, sorting, graph processing, and combinatorial optimization. This knowledge forms the computational core that enables students to develop efficient solutions across all other areas of computational mathematics.

Table 2.4: List of KUs in the Data Structures and Algorithms area.

2.4.1. DSA/Algorithmic Complexity and Asymptotic Analysis  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Topics:
Core

  • Complexity measures and asymptotic notation
  • Best, average, and worst-case analysis
  • Recurrence relations and solving techniques
  • Empirical analysis of algorithms
  • Space complexity and trade-offs

Learning Outcomes:
Core:

  1. Analyze algorithms using asymptotic notation (Big O, Omega, Theta) [Usage]
  2. Differentiate between best, average, and worst-case complexities [Assessment]
  3. Solve recurrence relations for algorithm analysis [Usage]
  4. Compare algorithms through empirical measurements [Assessment]

2.4.2. DSA/Fundamental and Advanced Data Structures  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Topics:
Core

  • Arrays, linked lists, and dynamic arrays
  • Stacks, queues, and deques
  • Hash tables and collision resolution
  • Trees and binary search trees
  • Heaps and priority queues

Learning Outcomes:
Core:

  1. Implement basic data structures from scratch [Usage]
  2. Analyze time/space complexity of data structure operations [Assessment]
  3. Select appropriate data structures for given problems [Assessment]
  4. Handle hash collisions using different strategies [Usage]

2.4.3. DSA/Searching and Sorting Algorithms  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Topics:
Core

  • Linear and binary search
  • Comparison-based sorting (QuickSort, MergeSort, HeapSort)
  • Non-comparison sorting (RadixSort, CountingSort)
  • Selection algorithms and order statistics
  • External sorting and large-scale processing

Learning Outcomes:
Core:

  1. Implement and compare searching algorithms [Usage]
  2. Analyze time/space complexity of sorting algorithms [Assessment]
  3. Select appropriate sorting algorithm for data characteristics [Assessment]
  4. Implement order statistics algorithms [Usage]

2.4.4. DSA/Graph Algorithms and Combinatorial Optimization  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Topics:
Core

  • Graph representation and traversal (BFS, DFS)
  • Shortest path algorithms (Dijkstra, Bellman-Ford)
  • Minimum spanning trees (Prim, Kruskal)
  • Network flow and matching
  • NP-completeness and approximation algorithms

Learning Outcomes:
Core:

  1. Implement graph traversal algorithms [Usage]
  2. Solve shortest path problems using appropriate algorithms [Usage]
  3. Construct minimum spanning trees [Usage]
  4. Analyze complexity of graph algorithms [Assessment]
  5. Design approximation algorithms for NP-hard problems [Usage]

2.4.5. DSA/Parallel and Distributed Algorithms  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Topics:
Core

  • Parallel computation models (PRAM)
  • Basic parallel algorithms (reduction, scan)
  • Distributed algorithms and consensus
  • Synchronization and load balancing
  • MapReduce and distributed data processing

Learning Outcomes:
Core:

  1. Analyze parallel algorithms using work-span model [Assessment]
  2. Implement parallel reduction and scan operations [Usage]
  3. Design distributed algorithms for consensus [Usage]
  4. Apply MapReduce paradigm to data processing [Usage]

Spotted a typo, an outdated course, a broken link, or have a suggestion? Let us know.

Scan to open on your phone