Transcript Final Review

Final Review
Dr. Yingwu Zhu
Goals
• Use appropriate data structures to solve realworld problems
– E.g., use stack to implement non-recursive BST
traversal,
– use queue to implement BST level traversal,
– use stack to implement non-recursive quicksort
• Use appropriate algorithms to slove real-world
problems
– Search algorithms
– Sorting algorithms
Goals
• Use Big-Oh notation to evaluate algorithm
efficiency
• Understand ADTs including BST, Heap,
Priority Queue, AVL trees
• Understand hashing
• Understand sorting algorithms
ADTs
•
•
•
•
•
Tree terminologies
BST
AVL Trees
Heap
Priority Queue
Trees
•
•
•
•
•
Binary trees
Complete trees
Balanced trees
Level
Height
BST
• Definition
• Recursive ADT
• Implementing a BST (recursive and nonrecursive)
–
–
–
–
–
Search
Traversals (in-order, pre-order, post-order)
Insertion
Deletion
Other operations: height, level, …
BST
•
•
•
•
T(n) = ?
Is BST balanced?
Lopsidedness problem!
BST  AVL trees
AVL Trees
• Definition
• Four rotation techniques
– Single rotations
– Double rotations
• Key to perform rotation: identify the nearest
ancestor with BF of +2 or -2 for the inserted item
• Two steps in double rotations
– Rotate child and grandchild nodes of the ancestor
– Rotate the ancestor and the new child node
Heap
•
•
•
•
Defintion
Recusive data structure
Semiheap
What data structures are good to
implement a heap? Why?
• Parent-child relationships
Heap
• Implementation
– Insertion
– Deletion
– removeMax
– Other operations?
• Two basic operations
– Percolate down
– Percolate up
Priority Queue
• Definition
• Using different ADTs to implement priority
queue
– Unsorted lists
– Sorted lists
– BST
– Heap
• Why heap is a good choice?
Hashing
• Why need hashing?
• Definition of hash function?
• Problem of hashing: collision
Hashing
• Collision resolution techniques
– Open addressing
• Linear probing
• Quadratic probing
• Double hashing
– Chaining
Hashing
•
Three strategies to improve hashing
performance
– Increase hash table capacity
– Use a good hash function (how to evaluate a
hash function?)
– Use a good collision resolution technique
Algorithm Efficiency
• Big-Oh notation definition T(n)
• Non-recursive algorithms
– The most executed instruction
• Recursive algorithms: telescoping principal
– Anchor case
– Inductive step
Sort
•
•
•
•
Selection sort, insertion sort, bubble sort
Heapsort
Quicksort
Mergesort
Selection Sort
• How does it work?
• T(n) = ?
Insertion Sort
• How does it work?
• T(n) = ?
• Recursive and Non-recursive algorithms
Bubble Sort
• How does it work?
• How does it detect partially sort sublist to
improve performance
• T(n) = ?
• Best case performance
• Worst case performance
• Two-way bubble sort in Exam 2
Quicksort
• How does it work?
– Devide and conquer
• Basic operation
– Split based on pivot
• T(n) = ? , best case and worst case?
Quicksort
• How to improve performance
– Median-of-three rule in pivot choice
– Short sublists are handle first in recursive alg.
– Non-recursive
– Other solutions
Mergesort
•
•
•
•
Internal and external algorithm
Basic operation: split and merge
Binary mergesort
Natural mergesort
– How does natural merge sort work?
– Exploit partially sort sublists in split and merge
• T(n) = ?
Heapsort
• Heapify process
• How does heapsort work?
– Exploits heap property
– T(n) = ?
Other Basics
•
•
•
•
•
Iterators and vectors in STL
Function templates and class templates
Overloading operators
Overloading functions
Copy constructors
About Final Exam
•
•
•
•
•
Must >= 75 to pass
Multiple choices
Short answers
Coding
Reminder: do not loose points in basic
concept questions!
• Good luck!