PDSA: Programming, Data Structures and Algorithms using Python

Topics covered

• Python refresher

  • Variables
  • Control flow
  • Functions
  • Lists, tuples and dictionaries

Expected skills: Use Python fundamentals to express an algorithm.

Topics covered

• Complexity, sorting & searching

  • Big-O, Big-Ω and Big-Θ
  • Best, average and worst cases
  • Linear versus binary search
  • Selection sort
  • Insertion sort
  • Merge sort

Expected skills: Analyse basic search and sorting methods and compare their complexity.

Topics covered

• Basic data structures

  • Arrays
  • Lists
  • Stacks
  • Queues
  • Hashing and dictionaries
  • Abstract data types

Expected skills: Select a basic data structure and explain its supported operations.

Topics covered

• Graph algorithms I

  • Adjacency matrix and adjacency list
  • BFS
  • DFS
  • Reachability
  • Connected components

Expected skills: Represent graphs and use traversals to study connectivity.

Topics covered

• Graph algorithms II

  • Topological sort
  • Directed acyclic graphs
  • Dijkstra and Bellman–Ford
  • Minimum spanning trees
  • Prim and Kruskal

Expected skills: Choose suitable algorithms for graph ordering, shortest paths and spanning trees.

Topics covered

• Union-find, heaps & binary search trees

  • Disjoint sets
  • Priority queues
  • Binary heaps
  • Heapify
  • Heapsort
  • Binary search tree operations

Expected skills: Use disjoint sets, heaps and search trees and trace their operations.

Topics covered

• Balanced trees & greedy algorithms

  • AVL trees
  • Rotations
  • Greedy design
  • Interval scheduling
  • Huffman coding

Expected skills: Explain AVL balancing and reason about greedy choices.

Topics covered

• Divide & conquer

  • Recurrences
  • Quicksort
  • Counting inversions
  • Closest-pair problem

Expected skills: Decompose a problem and analyse a divide-and-conquer approach.

Topics covered

• Dynamic programming

  • Memoization versus tabulation
  • Longest common subsequence
  • Edit distance
  • Matrix chain multiplication
  • Knapsack
  • Grid dynamic programming

Expected skills: Define states and transitions for standard dynamic-programming problems.

Topics covered

• String & pattern matching

  • Naive string matching
  • Efficient string matching
  • Text problems

Expected skills: Compare string-matching approaches and apply them to text.

Topics covered

• Flows, linear programming & complexity classes

  • Maximum flow and minimum cut
  • Linear programming intuition
  • P
  • NP
  • NP-completeness

Expected skills: Explain the roles of flow models, linear programming and complexity classes.

Topics covered

• Summary

  • Consolidation
  • Revision

Expected skills: Review algorithmic techniques and practise choosing an appropriate approach.