csc346 test 2

Using pseudocode, describe either Prim’s or Kruskal’s algorithm for finding the

minimal spanning tree of a graph.

• start with a graph with just the vertices

• repeat n-1 times

• add the lowest weight edge that doesn’t result in a cycle when added.

Which is faster, Bellman-Ford or Dijkstra’s Algorithm? If one is faster, why does

one need to know both?

Dijkstra’s Algorithm is faster as time to compute is O(V+E) log V). Although this algorithm is quicker, it fails when edges are negative. Bellman-Ford’s algorithm does not fail.

How does Floyd-Warshall differ in what it does from what Dijkstra’s and

Bellman-Ford do?

it finds and computes the shortest path between all pairs of vertices. Both Dijkstra and Bell-man Ford algorithm do not handle every pair of given vertices.

What properties should a good hash function have?

good hash functions should have rare collisions, minimum time taken to compute function, and distributes uni-formally.

In a Hash table, is it always bad to have collisions? Why or why not?

it’s not bad to have collisions, but in an efficient hash table, they should be rare. collisions are bad if they start to degrade performance.

In the Chain Matrix Multiplication Dynamic Programming problem, two things

were memorized. What were they? Also, what was the goal of this algorithm

minimum scalar multiplications and the optimal split point were memorized. the goal was to minimize the scalar multiplications when multiplying sequences of matrices.

in a hash table, how does chaining deal with collisions?

by creating a linked list (or similar data structure) for each slot (bucket) in the hash table array

in a hash table, how does linear probing deal with collisions?

by searching for the next available slot in a sequential, stepwise manner