Card Set Information
CS221 Test3 Graphs Sets Hashing
This is the study material needed for Test3 in CS221: Graphs, Sets, and Hashing.
length of a path
degree of a vertex
predecessors of a vertex
successors of a vertex
Illustrate with diagrams and explain two ways of
implementing graphs in a program, i.e. as an adjacency set, or an adjacency
Explain the algorithm for searching/traversing a
graph and describe the difference in implementing the search list as a stack or
as a queue.
Briefly discuss how Prim's Minimal Spanning Tree
Briefly discuss how Dijkstra's Shortest Path
What is meant by the term greedy
Component (base) type
What is the Union of two sets? Given example sets (A and B) show what the Union of A and B would contain. What symbol is used to represent the Union operation?
What is the Intersection of two sets? Given example sets (A and B) show what the Intersection of A and B would contain? What symbol is used to represent the Intersection operation?
What is the Difference of two sets? Given example sets (A and B) show what the Difference of A and B would contain? What symbol is used to represent the Difference operation?
What is the Symmetrical Difference of two sets? Given example sets (A and B) show what the Symmetrical Difference of A and B would contain?
Briefly explain the principle behind hashing.
Perfect hash function
List and explain 4 techniques of collision
Describe, with appropriate formulas, 5 different
approaches to calculating a hash function. (Hint: Base-26 is one of the five.)
Discuss some factors which should be taken into
consideration when selecting a hash table size.