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