DOC PREVIEW
CMU CS 15122 - Exam

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Final Exam15-122 Principles of Imperative ComputationFrank Pfenning, Tom Cortina, William LovasDecember 10, 2010Name: 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 Generic DynamicIntegers Sort Graphs Tries Traversal ProgrammingProb 1 Prob 2 Prob 3 Prob 4 Prob 5 Prob 6 TotalScoreMax 40 30 60 40 40 40 250Grader11 Integers (40 pts)Task 1 (15 pts). For each of the following expressions, indicate whether it is always true, alwaysfalse, true or false, abort (must abort), sometimes undefined (there are some values for x and ywhere the result is not defined). For both languages we assume declarationsint x = ...;int y = ...;so x and y are both properly initialized to arbitrary values.Expression Value in C0 Value in Cx + 0 == xx + y == y + x0 - x == -xx > 0 || x + 1 > x1/0 == 1/0Task 2 (10 pts). Write a C0 function bit which returns bit number i in the two’s complementrepresentation 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 xand y interpreted as unsigned numbers. So, for example, uleq(x,-1) is true for all x. You mayuse the bit function from Task 2.bool uleq(int x, int y) {}22 Generic Sort (30 pts)The sorting functions we studied in C0 just sorted arrays of integers into ascending order. Inpractice, we would want a sorting function that can sort arrays of arbitrary data according to anarbitrary ordering. In this problem we will sketch portions of such a generic sorting function andhow to use it.Assume we have, in C, an in-place sorting function sort with declarationvoid 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 sortingan array A of pointers to arbitrary data, taking as argument a generic comparison function leqon arbitrary data elements. Only show the function prototype, the way it would appear in aninterface, do not give its definition.Task 2 (5 pts). In order to obtain a generic sort function, we have to replace comparisonsA[i] <= A[j]in the original sorting function. Show the new form of the comparison (without writing the restof the function).3Task 3 (10 pts). Assume we have data structure of weighted edges in an undirected graph, wherevertices 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_leqto compare edges, taking into account that you want to pass a pointer to this function to thefunction sort.Task 4 (5 pts). Assume we have an array E containing e edges that we would like to sort byincreasing weight (as we have to, for example, in Kruskal’s algorithm). Based on your answers inTasks 1–3, write out the correct function call to sort E in place, using the generic function sort.43 Graphs (60 pts)Task 1 (15 pts). We can apply Kruskal’s algorithm to find a minimum spanning tree for the graphon the left0"1"2"3"4"5"6"7"0"1"2"3"4"5"6"7"with the edge weights shown below on the left. In the table below on the right, fill in the edges inthe order considered by Kruskal’s algorithm and indicate for each whether it would be added tothe spanning tree (Yes) or not (No). Do not list edges that would not even be considered. Whenyou are done, draw in the spanning tree above on the right.edge weight0 − 6 510 − 1 320 − 2 294 − 3 345 − 3 187 − 4 465 − 4 400 − 5 606 − 4 517 − 0 317 − 6 257 − 1 21edge considered added?5For 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; /* one endpoint */int u2; /* other endpoint */int weight;};typedef struct edge* edge;struct graph {int num_vertices; /* number of vertices */int num_edges; /* number of edges */edge* edges; /* edge array */};typedef struct graph* graph;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 isavailable.graph graph_new(int n, int e) {}6Task 3 (15 pts). Complete the following function to compute a minimum spanning tree for agiven graph G, to be stored in H. Assume that H is initialized with graph_new(n, n-1) wheren = G->num_vertices. The auxiliary data structure eqs is there to efficiently detect cycles. Itmaintains equivalence classes of vertices via union/find; for this problem it is only importantthat cycle(eqs, u, v) returns true if adding the edge from u to v would create a cycle. For thistask you should assume the given graph G is connected, that is, there is a path between any twovertices. You may use functions edge_leq and sort from Problem 2 (Generic Sort).void mst (graph G, graph H) {assert(G != NULL && H != NULL); /* graph must not be null */int n = G->num_vertices;int e = G->num_edges;edge* E = G->edges;edge* M = H->edges;ufs eqs = singletons(n); /* initialize union-find data structure */__________________________________ ; /* prepare edges to be considered */int i = 0, k = 0;while (________________________________){ if (!cycle(eqs, E[i]->u1, E[i]->u2)) {/* adding edge i would not create a cycle */______________________________ ;k++;}i++;}return;}7Task 4 (10 pts). A connected component of a graph is a set of vertices where each node can reachevery other node in the component along the given edges, and which is connected to no additionalvertices. For example, the graph below has 3 connected components.Explain, in words, how to use Kruskal’s algorithm to compute the number of connected com-ponents in a graph.8Task 5 (10 pts).Show how to modify the mst function from Task 3 so that it returns the number of connectedcomponents of the graph, and H (initialized as in Task 3) contains the graph consisting of mini-mum spanning trees


View Full Document

CMU CS 15122 - Exam

Download Exam
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Exam and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Exam 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?