CS221 Test3

Card Set Information

Author:
Anonymous
ID:
78623
Filename:
CS221 Test3
Updated:
2011-04-10 15: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

The flashcards below were created by user Anonymous on FreezingBlue Flashcards. What would you like to do?


  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.

What would you like to do?

Home > Flashcards > Print Preview