Final Exam 15 122 Principles of Imperative Computation Frank Pfenning Tom Cortina William Lovas December 10 2010 Name Andrew ID Section Instructions This exam is closed book with one sheet of notes permitted You have 3 hours to complete the exam There are 6 problems Read each problem carefully before attempting to solve it Consider writing out programs on scratch paper first Generic Dynamic Integers Generic Sort Graphs Tries Traversal Programming Prob 1 Prob 2 Prob 3 Prob 4 Prob 5 Prob 6 Total 40 30 60 40 40 40 250 Score Max Grader 1 1 Integers 40 pts Task 1 15 pts For each of the following expressions indicate whether it is always true always false true or false abort must abort sometimes undefined there are some values for x and y where the result is not defined For both languages we assume declarations int x int y so x and y are both properly initialized to arbitrary values Expression Value in C0 Value in C x 0 x x y y x 0 x x x 0 x 1 x 1 0 1 0 Task 2 10 pts Write a C0 function bit which returns bit number i in the two s complement representation of n Also supply a postcondition capturing the value range of the output int bit int n int i requires 0 i i 32 ensures Task 3 15 pts Write a C0 function uleq unsigned less or equal which compares two integers x and y interpreted as unsigned numbers So for example uleq x 1 is true for all x You may use the bit function from Task 2 bool uleq int x int y 2 2 Generic Sort 30 pts The sorting functions we studied in C0 just sorted arrays of integers into ascending order In practice we would want a sorting function that can sort arrays of arbitrary data according to an arbitrary ordering In this problem we will sketch portions of such a generic sorting function and how to use it Assume we have in C an in place sorting function sort with declaration void sort int A int lower int upper where in the body of the function we compare array elements only using the inequality A i A j Task 1 10 pts Give a declaration of a generic sorting function sort in C which permits sorting an array A of pointers to arbitrary data taking as argument a generic comparison function leq on arbitrary data elements Only show the function prototype the way it would appear in an interface do not give its definition Task 2 5 pts In order to obtain a generic sort function we have to replace comparisons A i A j in the original sorting function Show the new form of the comparison without writing the rest of the function 3 Task 3 10 pts Assume we have data structure of weighted edges in an undirected graph where vertices are represented as integers struct edge int u1 int u2 int weight typedef struct edge edge Here u1 is one end point of the edge u2 the other and weight its weight Write a function edge leq to compare edges taking into account that you want to pass a pointer to this function to the function sort Task 4 5 pts Assume we have an array E containing e edges that we would like to sort by increasing weight as we have to for example in Kruskal s algorithm Based on your answers in Tasks 1 3 write out the correct function call to sort E in place using the generic function sort 4 3 Graphs 60 pts Task 1 15 pts We can apply Kruskal s algorithm to find a minimum spanning tree for the graph on the left 2 2 0 0 6 7 6 7 1 1 3 5 3 4 5 4 with the edge weights shown below on the left In the table below on the right fill in the edges in the order considered by Kruskal s algorithm and indicate for each whether it would be added to the spanning tree Yes or not No Do not list edges that would not even be considered When you are done draw in the spanning tree above on the right edge considered added edge weight 0 6 51 0 1 32 0 2 29 4 3 34 5 3 18 7 4 46 5 4 40 0 5 60 6 4 51 7 0 31 7 6 25 7 1 21 5 For this problem we represent vertices by integers 0 1 and then edges as in Problem 2 Task 4 and graphs by the following structs We assume weights are integers greater or equal to 0 struct edge int u1 int u2 int weight typedef struct edge edge struct graph int num vertices int num edges edge edges typedef struct graph graph one endpoint other endpoint number of vertices number of edges edge array Task 2 10 pts Write a C function to allocate a new graph with n vertices and space for e edges where all the edges are initialized to the null pointer You may use the functions xmalloc size t nbytes and xcalloc size t nobj size t size which raise an exception if not enough memory is available graph graph new int n int e 6 Task 3 15 pts Complete the following function to compute a minimum spanning tree for a given graph G to be stored in H Assume that H is initialized with graph new n n 1 where n G num vertices The auxiliary data structure eqs is there to efficiently detect cycles It maintains equivalence classes of vertices via union find for this problem it is only important that cycle eqs u v returns true if adding the edge from u to v would create a cycle For this task you should assume the given graph G is connected that is there is a path between any two vertices You may use functions edge leq and sort from Problem 2 Generic Sort void mst graph G graph H assert G NULL H NULL int n G num vertices int e G num edges edge E G edges edge M H edges ufs eqs singletons n graph must not be null int i 0 k 0 initialize union find data structure prepare edges to be considered while if cycle eqs E i u1 E i u2 adding edge i would not create a cycle k i return 7 Task 4 10 pts A connected component of a graph is a set of vertices where each node can reach every other node in the component along the given edges and which is connected to no additional vertices For example the graph below has 3 connected components Explain in words how to use Kruskal s algorithm to compute the number of connected components in a graph 8 Task 5 10 pts Show how to modify the mst function from Task 3 so that it returns the number of connected components of the graph and H initialized as in Task 3 contains the graph consisting …