CSCI 2300 Lab 4 Fall 2015, 2/25/2014

This lab is about graphs and algorithms. You are welcome to start working on the lab ahead of time. Please read Chapter 2 and beginning of Chapter 3. There are four Problems - Do any three to get full credit.

This counts as one Problem.
Please plot n, vs T(n), Q(n), X(n), for the following functions, by using a C++ program to produce comma separated values and the exporting this file into a spreadsheet program to produce a plot. Always round off the arguments to integers.
- T(n)= T(n/2) + n, T(0)=0
- Q(n) = Q(n-1) + 2n , Q(0) =0
- R(n) = 2*R(n-1)+1, R(0)=0
- X(n) = 3*X(n/2)+1, X(0) =0
```
int main(void)
{
  int n;

  for (n = 10; n <=1000; n=n+10)
    cout << n<<","<< T(n) <<","<< Q(n) << "," << X(n)  << "\n";
   exit(1);
}
```
- Write the first 15 values of R and guess what function it is. (R(n) was not included in the main program above why?)
- Solve the Recurrence Relation P(n) = P(n-1) + 2, P(4) = 4 (use telescoping)
This is considered as one problem.
- Please take a look at Graph (Friendship Graph) List the nodes, List number of edges, degress of each node and average degree. If your browser does not display the svg files here is an image graph (same graph) (Interested readers may look at Frienship you can count on )
- Construct a simple connected graph with 10 vertices, such that almost all vertices have distinct degrees (almost all because exactly two vertices will ha ve the same degree).
Add a DFS procedure to the Graph Class (Sample) and Sample Data (input) for unweighted graph. and display the DFS spanning tree and the prenumbering and postnumbering of vertices (Please read the given Graph Class carefully and see the different functions associated with Graph Class - You are welcome to use your own Graph Class).
Find the maximum number of edges a connected undirected graph with n nodes can have. What is the maximum degree in such a graph and what is the average degree in such a graph?