DATA STRUCTURE

111-2 / Spring 2023

TA: 李英碩 (LI, YING-SHUO), 林仲偉 (LIN, ZHONG-WEI)

WEEK 1 - 02/23

Topic 1. Syllabus and Python basics
    2. Complexity Analysis - Part I: Big-Oh Notations

Slide Video

PPT EE4022 Syllabus

ZIP L01: Introduction

VIDEO Introduction of Data Structure

VIDEO Big O Notation

VIDEO Big O Property

WEEK 2 - 03/02

TopicComplexity Analysis - Part II: Properties

Slide Video

ZIP L02: Complexity Analysis

VIDEO Complexity Analysis Properties 1

VIDEO Complexity Analysis Properties 2

VIDEO Complexity Analysis Properties 3

WEEK 3 - 03/09

TopicComplexity Analysis - Part III: Algorithm analysis and C++ Basics

Slide Video

ZIP L03: Linear Data Structure

VIDEO Stack and Queue

VIDEO Deque and Algorithm Analysis

VIDEO Linked list

WEEK 4 - 03/16

TopicLinear Data Structure: Stack, queue, deque, ordered/unordered linked list

Slide Video

ZIP L04: Recursion Linear Programming

VIDEO Ordered List, Recursion, and Fractals

VIDEO Recursion and Dynamic Programming

WEEK 5 - 03/23

TopicComplexity Analysis - Part IV: Master Theorem for recursion analysis

Slide Video

PPT Master Theorem

VIDEO Master Theorem: Case 1

VIDEO Master Theorem: Case 2 & Case 3

VIDEO Master Theorem: Case 4

WEEK 6 - 03/30

TopicRecursion and Dynamic Programming

Slide Video

PPT Trees

PPT AVL Trees

VIDEO Trees

VIDEO AVL Trees Part 1

VIDEO AVL Trees Part 2

WEEK 7 - 04/06

TopicBinary Tree; AVL Tree

Slide Video

PPT Splay Trees

VIDEO AVL trees Deletion and Rotation

VIDEO SPLAY trees

VIDEO SPLAY step Amortized cost

WEEK 9 - 04/20

TopicAVL Tree; Splay Tree;

Slide Video

PPT Splay Trees

VIDEO Splay Step Amortized Cost

VIDEO Top-Down Splay

VIDEO Multi-way Search Tree

WEEK 10 - 04/27

TopicSplay Tree

Slide Video

PPT Splay Trees

PPT Multi-way Search Trees

PPT Red Black Tree & AA Tree

PPT Hashing

VIDEO Locality of Splay Tree

VIDEO Red Black Tree & AA Tree

VIDEO Hashing

WEEK 11 - 05/04

Topic2-4 Tree; Red Black Tree, AA Tree

Slide Video

PPT Binary Heap

PPT Binomial Heap

VIDEO Binary Heap

VIDEO Binomial Heap

VIDEO Dijkstra Algorithm

WEEK 12 - 05/11

TopicHash, Binary Heap

Slide Video

PPT Fibonacci Heap

PPT Leftist Heap & Skew Heap

VIDEO Fibonacci Heap (1)

VIDEO Fibonacci Heap (2)

VIDEO Leftist Heap

WEEK 13 - 05/18

TopicBinomial Heap, Fibonacci Heap

Slide Video

PPT Disjoint Set

VIDEO Leftist heap merging, Skew heap

VIDEO Disjoint Set - Union & Find

VIDEO Disjoint Set - Rank Lemma Proof

WEEK 14 - 05/25

TopicDisjoint Set

Slide Video

VIDEO Disjoint Set - Hopcroft Ullman Analysis

VIDEO Disjoint Set - Tarjan Analysis 1

VIDEO Disjoint Set - Tarjan Analysis 2

WEEK 15 - 06/01

TopicSkip List, Sorting

Slide Video

PPT Skip Lists

VIDEO Skip List

VIDEO Skip List - Expectation of Scan Forward Step


EXERCISE

HOMEWORK

Name Question Answer

Homework 1

Homework 2

Homework 3

Homework 4

Homework 5

PDF Asymptotic Analysis

PDF BellNumber, Complexity, Tree

PDF AVL, Splay Trees

PDF 2-3-4 Tree, Red Black Tree, AA Tree

PDF Heaps, Disjoint Set

Not Available

Not Available

Not Available

Not Available

Not Available

PROGRAM

Name Slide Code

Program 1

Program 2

Program 3

Program 4

Program 5

PDF Stack Implementation

PDF Monotonic Routing

PDF Binary Search Tree

PDF Heap Implementation

PDF Top-k Sum of Subarray

ZIP Program1 Code

ZIP Program2 Code

ZIP Program3 Code

ZIP Program4 Code

ZIP Program5 Code