CSC 382 Non-Comprehensive Final Due Date 12/15/11 at 5PM My Mailbox CS Department

CSC 382 – Non-Comprehensive Final Due date 12/15/11 at 5PM – my mailbox CS department

CSC 382 Version 2 (Graph-theory and Backtracking) --- Due Date 12/15/11 (drop-it in mailbox not later than 5 PM)

Must sign name on every page and last 4 digits of SSN

NAME: SS#:xxx-xx-

1)Define each of the following terms (20)

a)Graph G=(V,E ).

b)A walk, and a path of a graph G=(V,E ).

c)Degree of a vertex u of the graph.

d)A cycle in a graph G=(V,E).

e)Connected graph G=(V,E ).

2)Find all the spanning trees of the following graph (20)

NAME: SS#:xxx-xx-

3)Used Dijkstra’s algorithm to find the shortest path between node 1 and every other node of the following weighted graph. You must use all the data structures (Father, T, ).

Using the father array, reconstruct the shortest paths between 1 and every other node. (20)

NAME: SS#:xxx-xx-

4)Given a set S= {5, 3, 4, 1, 15, 12, 10} of integers find a subset of S whose sum is M=13 using Backtracking. (20)

NAME: SS#:xxx-xx-

5)Please answer the following questions (10)

A class has 10 students. Suppose that three students X, Y and Z do not know each other. X knows 5 students of the class, Y knows 5 students of the class. At least how many students must Z know to make sure that always there is one student that knows X, Y, and Z? (Explain by using a graph to model the relationships).

6)Explain how a cycle is found using Depth First Search in the following graph. Must show graphically how the vertex v and Father Parameters are passed and used in the recursive calls. (10)

SCRAP PAPER: Do not detach. Any answer on this page won’t count for your grade