CMP 507 Homework #7							 

1. When it would be advantageous to use a sequential array list representation 
instead a linked list representation?

	A sequential representation will perform better if there is a preponderance of 
random accesses to list items (from the perspective of time efficiency). It is more space-
efficiency when the list is long comparing to the size of the array.

2. Write a C function to implement the string operation strcpy(S,T).

void strcpy(chat *s, char* t)
{
 	 int i;
	
	for (i = 0; t[i] != '\0'; i++)
		 s[i] = t[i];
	 
	return 0;
}

3. What is the C string representation for the empty string of length zero?

	'\0'

4. What is the difference between static and dynamic memory allocation? 

With static memory allocation, the storage is allocated when a program is compiled. With 
dynamic allocation, the storage is allocated when a program is executed and ended with 
program terminated.

5. What is a heap? How is it used to support dynamic memory allocation? 

A heap is a separate region of memory, and we can allocate blocks of memory of various 
sizes from this region whenever the need arises. The storage allocated in this region is 
independent of subroutine calls and returns. Dynamic memory allocation can then take 
place using blocks allocated from this region anytime during the running of a program.	

6. What is the difference between the first-fit and best-fit policies for dynamic 
memory allocation?

	In the first-fit policy, we travel around the ring of free blocks starting at the block 
referenced by the pointer avail, until we find the first block B, such that the Size (B) >= 
n, and we use B to satisfy the request.

Under best-fit policy, we travel around the ring attempting to find a block which is the 
best fit for the request size n, as follows. Starting at block, B, referenced by the pointer 
avail, we compare size (B) to the request size n. If the size (B) == n, we have an exact fit, 
so we used block B to satisfy the request immediately by detaching it from the ring of 
free blocks and marking it as reserved. But if size (B) != n, then we continue to search 
around the ring. We stop whenever we find an exact fit. But if we travel all the way 
around the ring without having found an exact fit, we use the closed fit we discovered on 
our trip around the ring.

7. What do fragmentation and coalescing refer to in the case of heaps?
 
If  we operate a heap storage allocation system for a while, using either the first-fit policy 
or the best-fit policy, the ring of free blocks will tend to contain smaller and smaller 
blocks. This happens because we keep splitting larger blocks to satisfy requests for more 
storage. This tendency is called fragmentation.

In order to reduce the chances of encountering allocation failure, we can perform what is 
called coalescing. When we coalesce two blocks that are sitting next to one another in 
memory, we join them into a single larger block. A good time to try coalescing is when 
we free the storage of a block and return it to the ring of free blocks. This is to join it with 
its neighbors if possible before it is returned

8. Define the concept of a complete binary tree.

A complete binary tree is binary tree with leaves on either a single level or on two 
adjacent levels such that the leaves on the bottommost level are placed as far left as 
possible.

9. How can a heap be used to represent a priority queue? Discuss how to perform 
the operations of item insertion and removal in heaps used to represent the 
priority queue.
 
A heap can be use to store the items for a priority queue. In the heap, items are store so 
that the item at each parent location is larger than the items at children locations. A heap 
is an efficient representation of PQ because of this property. We think the order of items 
as the order of priority.

To insert an item, we start by adding a child location to the end of the array and consider 
the insert item as the item at this child location. Then compare the item with the item at 
its parent location. If the item of the child is larger, we exchange items between them, 
and consider the parent as a child to its parent and continue to compare and exchange 
until the item at the child location is smaller than that at the parent location.

To remove an item, we remove the root that has the highest priority and put the last item 
to the root. Then we restore the heap property by comparing items of parent with items of 
children and exchange items when items of children is larger starting from the root to the 
leaf.

10. How does it take to inset and remove items from a heap containing n items?

	insert:    O(lgn)
remove: O(lgn)

11. Write a generalized recursive traversal function in C.

typedef 	struct	NodeTag{
		char			Symbot;
		struct 	NodeTag	*Llink;
		struct 	NodeTag	*Rlink;
		} TreeNode;

void Traverse (TreeNode *T, OrderOfTraversal TraversalOrder)
{
	if (T != NULL){

	if(TraversalOrder == PreOrder){

		Vist(T);
		Traverse(T->Llink, PreOrder);
		Traverse(T->Rlink, PreOrder);
	} else if (TraversalOrder == InOrder){
		
		Traverse(T->Llink, InOrder);
		Vist(T);
		Traverse(T->Rlink, InOrder);

	} else if TraversalOrder == PostOrder){

		Traverse(T->Llink, PostOrder);
		Traverse(T->Rlink, PostOrder);
		Vist(T);
	}
     }
}

12. Write a level order binary tree traversal using queues.

	#include <stdio.h>
	#include “QueueInterface.h”

	void LevelOrderTravesal(TreeNode *T)
	{
		Queue Q; TreeNode *N;
		
		Initial (T, &Q);
		Insert (T, &Q);
		While (!Empty(&Q)){
			Remove(&Q,&N);
			If (N != NULL) {
				Print(“%c”, N->Symbol);
				Insert(N->Llink, &Q);
				Insert(N->Rlink, &Q);
			}
		}
	}

13. What is a binary search tree?

In a binary search tree, a node N with key K is inserted so that the keys in the left subtree 
of N are less than K, and the keys in the right subtree of N are greater than K.
	Keys in Left of subtree of N < Key K in node N < Keys in right subtree of N.

14. Draw diagrams illustrating four types of rotations that can be used to restore the 
property in a binary search tree?

PP. 379


15. What is the adjacency matrix for a graph G? How do the adjacency matrices for 
directed graphs differ?

Let G=(V,E) be a graph, Suppose we number the vertices in V, as v1,v2,…vn, such that 
row i corresponds to vi and column j corresponds to vj (n ? i ,j ? 1). Now, we use a table 
T[i, j] have n rows and n columns, we will fill the table T[i, j ] = 1 as if there is an edge 
e= (vi, vj) in E and T[i, j] = 0, otherwise. This is called adjacency matrices.

In an undirected graphs, the adjacency matrix is symmetric, since there is no direction on 
the edge. But in directed graphs, the edge has direction so the matrix is not symmetric.

16. What is the adjacency between depth-first searching and breadth-first searching 
in a tree, then the difference between depth-first and breadth-first searching. 
P417,418

Depth-first searching is any unvisited descendants of a given node x were always visited 
before any unvisited right brother or sisters in the tree.

Breadth-first search is we process all unvisited immediate neighbors of a given vertex x 
before processing any neighbors of x’s neighbors.

17. describe informally how Dijkstra’s shortest path algorithm works.

Dijkstra’s algorithm maintains a set S of vertices whose final shortest-path weights from 
the source s have already been determined. That is, for all vertices v ? S, we have d[v] = 
d(s, v). The algorithm repeatedly selects the vertices, u with the minimum shortest-path 
estimate, inserts u ? S into S, and relaxes all edges leaving u.

18. What is a minimum cost spanning tree?

The cost of the tree is defined as the total weights on its edges. If the spanning tree, T, of 
minimal cost that spans all the vertices in G we call it is a minimum spanning tree.

19. Describe the Prim’s algorithm to find the minimum cost spanning tree.

The Prim’s algorithm is the way that you identify which vertex to add to T is to choose 
that vertex w that is not already in the tree T such that the closest distance from w to some 
vertex in T is less than or equal to the closest distance of all the other vertices v that is not 
yet in T.

20. Describe the greedy method strategy.

Prim’s algorithm is called a greedy algorithm, because it succeeds in finding a global 
optimum by making a sequence of locally greedy choices. A locally greedy choice is a 
choice of the best among several local alternatives at a particular stage of the solution 
process.