Data Struct & Algorithms
Data Struct & Algorithms CS 245
Popular in Course
Popular in ComputerScienence
verified elite notetaker
This 13 page Class Notes was uploaded by Michele Herzog on Thursday October 29, 2015. The Class Notes belongs to CS 245 at University of San Francisco taught by David Galles in Fall. Since its upload, it has received 59 views. For similar materials see /class/231235/cs-245-university-of-san-francisco in ComputerScienence at University of San Francisco.
Reviews for Data Struct & Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/29/15
Data Structures and Algorithms CSZ4520098MT2 Midterm 2 Review David Galles Department of Computer Science University of San Francisco MTzo n log n Sorting 0 Merge Sort 0 Quick Sort 0 Partition 0 Heap sort examples MT21 NonComparison Sorting 0 Bucket sort 0 Counting sort 0 Radix sort examples MT22 Hash Tables 0 Hash functions 0 Open Hashing closed addressing separate chaining 0 Examples MT23 Hash Tables 0 Closed Hashing open addressing 0 Linear Probing Primary clustering Quadratic Probing 0 PseudoRandom 0 Double Hashing examples MT24 Disjoint Sets Using Trees to represent sets 0 Parent pointer representation w arrays Union by rank Path compression examples MT25 Graphs 0 Adjacency Lists 0 Adjacency Matrices 0 Simple manipulations Convert adjacency list to adjacency matrix for instance MT26 Graphs 0 Topological Sort Calculating indegree Using indegree 0 Finding Cycles MT27 Graphs Searching 0 DFS DFS Search Tree 0 BFS 0 BFS Search Tree mm Graphs Shortest Path 0 Dijkstra s Algorithm Dijkstra Table 0 Using Heaps 0 Floyd s Algorithm MT29 Graphs Spanning Trees 0 Kruskal s Algorithm Using disjoint sets 0 Prim s Algorithm MT210 23 Trees amp BTrees 0 Definitions 0 What is a BTree of Maximum degree 5 0 Inserting 0 Finding 0 Deleting MT211 Binomial Queues 0 Defintions Binomial Tree of degree k 0 Merge 0 Insert 0 Remove Min