# CS221 Test3

 vertices edges weighted graph directed graph undirected graph adjacent vertices path length of a path cycle simple cycle connected vertices connected components adjacency set adjacency matrix 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 matrix. 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 algorithm works. Briefly discuss how Dijkstra's Shortest Path algorithm works. What is meant by the term greedy algorithm? Set Component (base) type Subset Universal Set Empty Set Cardinality 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? Hashing Hash Tables Briefly explain the principle behind hashing. Hash function Collision Collision resolution Load Factor Clusters Double hashing Linear probing Perfect hash function List and explain 4 techniques of collision resolution. 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. AuthorAnonymous ID78623 Card SetCS221 Test3 DescriptionThis is the study material needed for Test3 in CS221: Graphs, Sets, and Hashing. Updated2011-04-10T19:45:09Z Show Answers