CS221 Test3

Home > Preview

The flashcards below were created by user Anonymous on FreezingBlue Flashcards.

1. vertices
2. edges
3. weighted graph
4. directed graph
5. undirected graph
6. adjacent vertices
7. path
8. length of a path
9. cycle
10. simple cycle
11. connected vertices
12. connected components
13. adjacency set
14. adjacency matrix
15. degree of a vertex
16. predecessors of a vertex
17. successors of a vertex
18. Illustrate with diagrams and explain two ways of
implementing graphs in a program, i.e. as an adjacency set, or an adjacency
matrix.
19. Explain the algorithm for searching/traversing a
graph and describe the difference in implementing the search list as a stack or
as a queue.
20. Briefly discuss how Prim's Minimal Spanning Tree
algorithm works.
21. Briefly discuss how Dijkstra's Shortest Path
algorithm works.
22. What is meant by the term greedy
algorithm?
23. Set
24. Component (base) type
25. Subset
26. Universal Set
27. Empty Set
28. Cardinality
29. 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?
30. 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?
31. 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?
32. 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?
33. Hashing
34. Hash Tables
35. Briefly explain the principle behind hashing.
36. Hash function
37. Collision
38. Collision resolution
39. Load Factor
40. Clusters
41. Double hashing
42. Linear probing
43. Perfect hash function
44. List and explain 4 techniques of collision
resolution.
45. Describe, with appropriate formulas, 5 different
approaches to calculating a hash function. (Hint: Base-26 is one of the five.)
46. Discuss some factors which should be taken into
consideration when selecting a hash table size.

Card Set Information

 Author: Anonymous ID: 78623 Filename: CS221 Test3 Updated: 2011-04-10 19:45:09 Tags: CS221 Test3 Graphs Sets Hashing Folders: Description: This is the study material needed for Test3 in CS221: Graphs, Sets, and Hashing. Show Answers:

Home > Flashcards > Print Preview