PolyU | データ構造とアルゴリズム

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 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 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 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.