Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Data Structures and Algorithm Design Part II

Tsinghua University via XuetangX

Go to class Write review

Boot.dev

The Most Addictive Python and SQL Courses

DataCamp

AI Engineer - Learn how to integrate AI into software applications

Overview

Google, IBM & Meta Certificates – 40% Off

One Coursera Plus subscription covers most Professional Certificates on Coursera.

Unlock All Certificates

Data structures play a central role in computer science and are the cornerstones of efficient algorithms. Knowledge in this area has been at the kernel of related curriculums. This course aims at exploring the principles and methods in the design and implementation of various data structures and providing students with main tools and skills for algorithm design and performance analysis. Topics covered by this course range from fundamental data structures to recent research results. "Data Structures and Algorithm Design Part II" is an advanced course extending the materials in "Part I". We will cover more powerful and sophisticated data structures & algorithms, including: splay trees, B-trees, red-black trees, hash tables, priority queues, strings and sorting.

Syllabus

07.Binary Search Tree

A.introduction
B1.BST : search
B2.BST : insertion
B3.BST : removal
C.balance+equivalence
D1.AVL : rebalance
D2.AVL : insertion
D3.AVL : removal
D4.AVL : (3+4)-construction
Homework

08.ABST I

A1.Splay_Tree.splay1
A2.Splay_Tree.splay2
A3.Splay_Tree.implementation
B1.B-Tree.motivation
B2.B-Tree.structure
B3.B-Tree.search

08.ABST II

B4.B-Tree.insertion
B5.B-Tree.removal
XA1.Red-Black.motivation
XA2.Red-Black.structure
XA3.Red-Black.insertion
XA4.Red-Black.removal
Homework

09.Dictionary

B.hashing.principle
C.Hashing.Hash-Function
D1.Hashing.Solving-Collision-1
D2.Hashing.Solving-Collision-2
E.Bucketsort
Homework

10.Priority Queue

A1.motivation
A2.Basic_Implementations
B1.Complete_Binary_Heap.structure
B2.Complete_Binary_Heap.insertion
B3.Complete_Binary_Heap.removal
B4.Complete_Binary_Heap.heapification
C.Heapsort
XA1.Leftist_Heap.structure
XA2.Leftist_Heap.merge
XA3.Leftist_Heap.insertion+removal
Homework

11.String I

A.ADT
B1.Pm
B2.brute-force
C1.Kmp.memorization
C2.Kmp.lookup-table
C3.Kmp.understanding_next[]
C4.Kmp.constructing_next[]
C5.Kmp.amortization
C6.Kmp.improvement

11.String II

D1.BM_BC.begin_with_the_end
D2.BM_BC.bad_character
D3.BM_BC.constructing_bc[]
D4.Bm_BC.performance
E1.Bm_GS.good-suffix
E2.Bm_GS.constructing_gs[]
E3.Bm_GS.performance
F1.KR.fingerprint
F2.KR.hashing
Homework

12.Sorting

A1.Quicksort.algorithm
A2.Quicksort.performance
A4.Quicksort.Variation
B1.Selection.mode
B2.Selection.Median
C1.Shellsort.Shell's sequence
C2.Shellsort.Inversion
Homework

Taught by

Junhui Deng

Tags

china

Reviews

Start your review of Data Structures and Algorithm Design Part II