PolyU | Data Structures and Algorithms

This lecture introduces Data Structures and Algorithms (DSA) as the foundation for building efficient, scalable software by minimizing resource consumption relative to input size. Students learn to use Big O notation to analyze performance trade-offs and understand how choosing the right data structure and algorithmic approach is essential for solving complex computational problems effectively.

This lecture introduces arrays and linked lists as fundamental data structures, comparing their performance in terms of memory allocation, access time, and modification efficiency. You will learn how arrays utilize contiguous memory for $O(1)$ random access, while linked lists use dynamic pointers to achieve $O(1)$ insertion and deletion at known positions.

A stack is a linear data structure that follows the FILO (First In, Last Out) principle, where all insertions and deletions occur at a single end called the top. This lecture covers the fundamental operations—push, pop, and peek—and explains how to implement them using arrays while managing boundary conditions like stack overflow and underflow.

This lecture introduces the Queue data structure, which follows the First-In, First-Out (FIFO) principle using front and rear pointers for efficient element management. It highlights the limitations of naive linear array implementations, specifically the issue of artificial overflow, and introduces the concept of circular queues to optimize space usage.

This lecture introduces tree data structures, focusing on the properties and implementation of binary trees, including their representation via linked structures or arrays. It further explores the importance of tree height for computational efficiency and demonstrates the practical application of expression trees for evaluating mathematical operations.

This lecture explores the mechanics of Binary Search Trees (BSTs) and Hash Tables, focusing on efficient data storage and retrieval. Students will learn how to perform search, insertion, and deletion operations in BSTs, understand the necessity of AVL tree balancing to prevent performance degradation, and examine how hash functions and collision handling strategies enable near-constant time complexity.

This lecture introduces the Priority Queue as an abstract data type and presents the Binary Heap as an efficient implementation using a complete binary tree. By leveraging the heap's structure and array-based representation, operations like insertion and extraction can be performed in logarithmic time.

This lecture introduces graphs as a flexible data structure that generalizes trees by allowing cycles to model complex real-world relationships. Students will learn the formal mathematical definition of graphs, including key properties like vertex degree, edge direction, and weights, which are essential for choosing the right model for specific applications.

This lecture introduces fundamental graph concepts, including representation via adjacency lists and the necessity of systematic traversal to explore network structures. It focuses on Breadth-First Search (BFS), explaining how a FIFO queue enables layer-by-layer exploration to efficiently determine shortest paths in unweighted graphs.

This lecture introduces fundamental graph navigation techniques, focusing on finding efficient routes and valid sequences within networked data structures. Students will learn to apply Dijkstra’s Algorithm to solve shortest-path problems in weighted graphs and use Topological Sort to determine logical orderings in directed acyclic graphs.

This lecture introduces the concept of a Minimum Spanning Tree (MST) as a way to connect all vertices in a weighted, undirected graph with the minimum possible total edge weight. Students will learn how to model real-world infrastructure problems—such as network design, power grids, and data clustering—as graph optimization tasks.

This lecture introduces the formal definition of sorting, which requires transforming an input array into a permutation that satisfies a specific order constraint. You will learn why sorting is a critical preprocessing step for optimizing search operations and data structure construction, while exploring the key performance metrics of time complexity, space complexity, and stability.

This lecture provides a comprehensive review of data structures and algorithms, focusing on the core objective of selecting and justifying efficient solutions for computational problems. It emphasizes mastering Big O notation to analyze time and space complexity, while highlighting the critical relationship between data organization and algorithmic performance.

This lab teaches you how to convert postfix expressions to prefix notation by constructing an expression tree using a stack-based approach. You will learn to implement a binary tree structure and perform a preorder traversal to transform the expression into its equivalent prefix format.

This lab focuses on implementing a Binary Search Tree (BST) to support insertion, searching, and finding successor or predecessor values. Students will practice both iterative and recursive approaches to tree traversal to efficiently manage and query data.

This lab introduces the Priority Queue as an abstract data type implemented through a binary max-heap, which allows for efficient insertion and removal of elements. Students will learn to maintain the heap property using array-based indexing and recursive bubble-up and bubble-down operations.

This lab introduces graph data structures by using an adjacency list to model a social network where users are nodes and friendships are undirected edges. Students will learn to implement and query this network by performing operations such as adding friendships, calculating user degrees, checking connections, and aggregating data across the entire graph.

This lab introduces graph representation using adjacency lists to model social networks and implement traversal algorithms. Students will learn to process commands to build a graph and perform Depth-First Search (DFS) and Breadth-First Search (BFS) to explore connections.

This lab introduces Dijkstra's algorithm for finding the shortest paths in a network, focusing on calculating minimum latency and identifying the next hop from a source server. Students will learn to implement the algorithm using an adjacency list, a priority queue, and a parent array to reconstruct routing paths.

This lab introduces Minimum Spanning Trees (MST) as a method to connect planets with the lowest possible total Euclidean distance. Students learn to implement Prim’s algorithm to efficiently solve this problem in a dense graph by iteratively selecting the cheapest edges to connect all vertices.

This lab explores how to efficiently calculate the number of inversions in a sequence, known as the Chaos Metric, by modifying the Merge Sort algorithm. By leveraging a divide-and-conquer strategy, you will learn to optimize the counting process from an $O(N^2)$ brute-force approach to an efficient $O(N \log N)$ solution.