Transcript Exam Review - CS 357 - The University of Alabama

Data Structures
Pre-Midterm Discussion
Phillip G. Bradford
The University of Alabama
Details
• Closed book, closed notes
• No calculators, etc.
Approach to Midterm 2
• Working with costs & functionality
– Which methods work best
• Under which circumstances?
– Understand the analysis and the algorithm
development
– General approach
• About 1/3 of the exam is intended to be straight-forward
• About 1/3 of the exam is of a medium level of challenge
• About 1/3 should be challenging
Approach to Midterm 2
• There will be Big-Oh notation question(s)
• Perhaps one tracing question
Material Covered
• The chapter sections we discussed in
lecture from chapters 5 through 9
– Extendible Arrays
– Trees
• Depth & height
• P 275, proposition 6.9
• Preorder, postorder and inorder
– Priority Queues
• Heaps
Material Covered
• Priority Queues, cont.
– Select min in heaps
– Inserting a new element in a heap
– Using a heap to sort
• Dictionaries
– In an array
– Using hashing
• Load factor…
– Linear hashing & double hashing
Material Covered
• Binary Search
• Binary Search trees
– Updating BSTs
– AVL trees
• Inserting and deleting elements