NUSmods

Data Structures & Algorithms

This course introduces students to the design and implementation of fundamental data structures and algorithms. The course covers basic data structures (linked lists, stacks, queues, hash tables, binary heaps, trees, and graphs), searching and sorting algorithms, and basic analysis of algorithms.

Prerequisites

• CS1010 or its variants
• CS1231 or its variants

Contents

The notes here only span the 2nd part of the semester. The course also covers basic data structures like the Stack, Queue ADTs, simple sorting algorithms, as well as trees and how to augment them.

Algorithms

• HeapSort
• Quick-Find
• Quick-Union
• Weighted Union
• Bellman-Ford
• Dijkstra’s
• Kahn’s
• Kruskal’s
  • Red-Blue Rule
• Prim’s
• Floyd-Warshall

Paradigms

• Dynamic Programming

Problems

• Topological Sorting
• Dynamic Connectivity
• Minimum Spanning Tree
• Single Source Shortest Path
• Prize Collecting
• Vertex Cover for Trees
• All Pairs Shortest Paths

Data Structures

• Hash Table
• Heap