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.