CMP 507 Homework #8
1. Find the all source shortest path.
void ShortestPath(void)
{
(Let MinDistance be a variable that contains edge weights as values)
(and Let Minimum(x,y) bw a function whose value is the lesser of x and y.)
/*Let v1 ? V be the origin vertex at which the shortest path starts. */
/*Initialize W and ShortestDistance[u] as follows: */
W = {v1};
ShortestDistance[v1] = 0;
for(each u in V-{v1}) ShortestDistance[u] = T[v1][u];
/* Now repeatedly enlarge W until W includes all vertices in V */
while(W!=V){
/*find the vertex w ? V-W at the minimum distance from v1 */
MinDistance = ?;
for(each v ? V-W){
if(ShortestDistance[v] < Mindistance){
MinDistance = ShortestDistance[v];
w = v;
}
}
/*add w to W*/
W = W ? {w};
/* upsate the shortest distances to vertices in V-W*/
for(each v ? V-W){
Shortestdistance[u] =
Minimum(ShortestDistance[u],
ShortestDistance[w]+T[w][u]);
}
}
}
2. Describe informally the four-color problem.
Cartographers have believed for ages that you need only four colors to color the countries on a map so that each two countries that are adjacent to
one another use different colors. The four color problem can be formulated as graph problem. Given any planar graph G = (v, E), is it possible to
assign at most four colors(c1,c2,c3,c4) to the vertices V, using function c(v) = ci, where the function c(v) send vertices v ? V into the four colors
ci, (1 ? i ? 4), such that if(v, w) is an edge in E, then c(v) ? c(w).
3. Describe and compare the division, folding, middle-squaring, and truncation hash function methods.
The division method is to choose a prime number as the table size M, and define hash function as: h(K) = K%M.
In folding, the key is divided into sections, and the sections are added together. for example, if we had 9-digit keys, such as the key K =
013402122, we could divide K into three sections: 013, 402 and 122, and we could add them together getting 537 for the value of h(k).
In middle-squaring, if we again had the 9-difit key, K = 013402122, we could tale the middle digits, 402, and square them getting h(K) = 4022 =
161604. If 161604 exceeded the table size, M, we could choose, say, the middle four digits of the result, getting h(K) = 6160.
In truncation, we simply delete part of the key and use the remaining digits(or bits or characters). For example, if K = 013402122, we could
ignore al but the last three digits. getting h(K) = 122. While truncation takes hardly any time to compute, it tends not to spread the keys randomly
and uniformly into the space of hash table location.
4. Define what it means for two keys to collide in a hash table.
A collision between two keys, K and K', occurs if, when we try to store both keys in a hash table, T, both keys have the same hash address, h(k),=
h(k').
5. What is a database system? What are the major functions performed on the database system?
A database is a collection of files concerned with a particular organization or enterprise. A database system consists of the database itself,
together with the set of machines, people, policies, and procedures that govern its use in the context of the enterprise.
The major functions are to store, retrieve and inquire information.
6. What is an ISAM file? What are the two search methods performed on an ISAM file?
ISAM is Indexed Sequential Access Method. The idea behind the ISAM technique is to write records of a file sequentially on portions of each
successive cylinder in a disk in order of increasing keys K, and then to prepare a cylinder surface index, which may be used to ascertain where
the record containing a particular search key K resides.
The two search methods are indexed method and sequential method.
7. Describe informally the external merge sort of a 100MB file on disk.
External merge sort is the method to sort huge quantity of numbers by separate the huge quantity number to several small quantity numbers,
which computer can handle very easily.
To sort a large file of 100MB, we can break it into, say, 16 files containing 6.25MB each. We could read each of the 16 small files, sort them
internally in primary memory, and write them back out on disk again.
We could conquer two input files and generate new sorted output file and save the file back to the disk. Keep conquering until all 100 MB data
sorted together.
8. Describe informally the divide-and-conquer strategy.
The divide-and-conquer sorting methods work by dividing the original unsorted array, A, into two smaller sub-arrays, L and R, sorting these two
smaller sub-arrays using recursive calls, and then combining the sorted sub-arrays, L and R to yield the final sorted result, A.
9. Describe informally the dynamic programming strategy.
Dynamic programming is an algorithm design method that can be used when the solution to a problem may be viewed as the results of a
sequence of decisions. Some applications are all pair shortest paths, traveling salesperson problem and linear programming.
10. Describe and compare the bubble sort, insertion sort, selection sort, heap sort, quick sort, binary tree sort, merge sort , shell sort,
proxmap sort, radix sort.
Bubble sort works by making repeated passes through the array, A, transposing any pair of adjacent keys, (a[i],a[i+1]), that are not in sorted
order. Eventually, it makes a pass in which in finds no pair is out of order, at which point, it terminates. Bubble Sort runs in time O(n2) in the
average case. It is the worst sorting methods ever discovered.
Insertion sort works by letting C be a subarray of array A. Initially, C, consists of just one key. As each of the remaining (n-1) keys, K, of A is
inserted into C, K is placed into C so as to maintain all keys inside C in sorted order. This can be accomplished by moving all keys in C greater
than K on space to the right, opening up a hole in C in which to insert K. Eventually, when all unsorted keys of A have been inserted into C, the
subarray c occupies the entire array A, so that A is them completely sorted. Insertion Sort runs in time O(n2) on the average, although it will
terminate fairly quickly when applied to an array A that is only slightly out -of-order initially.
In selection sort, the subarray PQ represents a priority queue by using the unsorted array representation of PQ, in which, to identify the largest
key in PQ to remove, we scan all keys in PQ to locate the position of the largest key. Selection sort runs in time O(n2).
Heap sort uses the sequential array representation of a heap to represent the priority queue, PQ. Because of this, the initial unsorted array A can
be organized into a heap in them O(n), and the largest key can be remove from a heap of k keys in time O(log k). Since the times required to
remove keys form successively smaller and smaller heaps of size n, (n-1),...,2, is no larger than a sum of numbers of the form a*?(1