Prove by induction that an n-dimensional cube has a Hamiltonian An n-dimensional cube is de need as follows

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

1. (15 points Hamiltonian Paths and Cycles)

   • (2 points) Does the graph below have a Hamiltonian Path? Justify your

   • (3 points) Does the graph below have a Hamiltonian Cycle? Justify your

• (10 points) Prove by induction that an n-dimensional cube has a Hamiltonian An n-dimensional cube is de need as follows. It consists of the 2n vertices of the form (a0, a1, ..., an) where each ai is ei- ther 0 or 1. Two vertices have an edge connecting them if the vertices di er in exactly one component. The following are some examples of n-dimensional cubes.

  1. A 1-dimensional cube consists of the vertices 0 and 1 and the edge (0,1),

  2. A 2-dimensional cube consists of the vertices (0,0), (0,1), (1,0), and (1,1). The edges would be ((0,0),(0,1)), ((0,0),(1,0)), ((0,1),(1,1)), and ((1,0)(1,1))

• A 3-dimensional cube consists of the 8 vertices and 12 edges that you would draw when drawing a regular

Include your solution in your PDF le..

2. (30 points General Graph Theory)

   • (5 points Max Flow/Min Cut) In the transport network below nd the maximal ow and a matching minimal cut. I will be updating the lecture notes for Max Flow by Friday afternoon on 12/6 to complete the discussion of nding the max Include your solution in your PDF le.

 

• (5 points Handshaking) There were 10 people at a At the end of the party, one of the people (let's call him John) asked each of the other 9 people present to tell him with how many other people at the party did they shake hands. John was surprised to learn the following.

  1. Every person shook hands with at least one other person (no shaking of one's own hands allowed).

  2. No two of the nine people reported the same number of

 

How many people did John shake hands with? Justify your answer and show all work. Include your solution in your PDF le.

• (5 points Vertex Degrees) Prove that every graph with two or more nodes must have at least two vertices having the same Determine all graphs that contain just a single pair of vertices that have exactly the same degree. Justify your answers. Include your solution in your PDF le.

• (5 points Connectedness) Let G be a graph. The complement of G, G', is the graph having the same nodes, but in which (a,b) in an edge i (a,b) is not an edge in Prove that if G is disconnected, then G' is connected. Include your solution in your PDF le.

• (5 points Chess) Is it possible to move a knight on an 8 8 chessboard so that it completes every move exactly once? A move between two squares of the chessboard is completed when it it made in either direction. Justify your answer. Include your solution in your PDF le.

• (5 points Two Coloring) Is there a planar graph with 17 edges and 10 vertices that can be 2-colored?

Justify your answer. Include your solution in your PDF le.

3. (15 points NP Complete Problems) For each of the 5 following problems determine whether it is NP- Complete or whether it can be solved in polynomial Give a reference supporting your claim. Include your solution in your PDF le.

 

• Suppose you have a logic circuit consisting of AND gates, OR gates, inverters (NOT gates) that has a single output and multiple inputs. Suppose that exactly one of the gates fails so that it always gives the same output value regardless of the input values. Determine a set of input values that will detect that fault. In other words, nd a set of input values will produce a di erent output value if that particular gate gets stuck compared to when it operates

• Determine where a given graph has a spanning tree for which each node has degree 2 or less?

• Let G be a graph with weights on each edge. Determine if G has a spanning tree such that the weights of the edges in G sum to less than some number

• Suppose you have a some tasks, T, to be scheduled on m processors. Each task takes some positive amount of time to complete, and once started on a processor, it must remain on that processor until completion. Suppose that there is a deadline by which all tasks must be Find a schedule that allows you to schedule the tasks on the m processors so that you meet the deadline or determine that no such schedule exists.

• Suppose you are given a graph so that each vertex and each edge has a positive weight assigned to it. Suppose you are given two positive integers K and J. Is it possible to partition the vertices V, into subsets V1, V2, ..., Vm such that the sum of the weights of the vertices in each Vi ≤ K and for each i and j, the sum of the weights of the edges between Vi and Vj is ≤ J .

4. (15 points Red-Black Trees, B-Trees, and Binary Search Trees)

   • (10 points) Write a program to implement only the insertion function of red-black    If you are unable to implement this algorithm correctly, describe your di culties and produce the best code that can. Include your code in both the PDF and ZIP les.

   • (5 points) Create 10 sets of 10,000 positive Label the sets Prob4bData0.txt,..., Prob4bData9.txt and include them in the ZIP le. Use the BST and B-Tree programs that you created in Problem 8

of Prelim2 (if you did not code those programs, please do so now), along with the Red-Black Tree Insertion program that you created in Part (a) and your 10 sets of random integers to create BSTs, B-Trees (t = 3), and Red-Black Trees using the appropriate insertion routines. Produce a statistical analysis (mean, median, and standard deviation) of the heights of the trees generated and the actual time that it takes to create the 10,000 element trees. Include the comparison of these algorithms in the PDF le. Include your statistical analysis in both the PDF and ZIP les.

 

5. (15 points More Graph Algorithms) All the following questions relate to the   le GraphData.txt that   was used in the previous two Refer to the previous prelims for information about how this  le  is structured. Turn the graph stored in GraphData.txt into a weighted graph by assigning the weight

|node1 - node2| to the edge (node1,node2). For example, the rst line of GraphData.txt is the edge (277,

325) which gets a weight of |277 - 325| = |-48| = 48.

• (5 points Minimal Weight Spanning Tree) With the weights assigned nd the weight of a minimum weight spanning forest for the graph in GraphData.txt. Put the code you used to nd it and the value you found into the PDF le and the ZIP    In the ZIP  le only,  include a list of the edges in the minimal weight spanning tree that you found.

• (5 points Maximal Shortest Paths) Compute the shortest distances (costs) between all pairs of nodes in the weighted graph we In the PDF and ZIP les include the code that you wrote to nd these values along with the maximum of all the shortest paths and the number of pairs of vertices that have this maximum shortest path.

• (5 points Depth- rst Search) Find the length of a longest paths of nodes v0, v1, ..., vk where vi is an ancestor of vj if i < j. Include your code, this maximum length, and the number of such maximal chains in both your PDF and ZIP les.

6. (10 points GCD) All integers are positive in this problem. We know that GCD(p,p) = p, for all positive p.

• (2 points) Prove that if p and q are even integers ttCD(p, q) = 2 ttCD(p/2, q/2). Include your solution in your PDF

• (2 points) Prove that if p is odd and q is even ttCD(p, q) = ttCD(p, q/2). There is a similar result if p is even and q is Include your solution in your PDF le.

• (2 points) Prove that if p and q are both odd and p > q, ttCD(p, q) = ttCD((p q)/2, q). Include your solution in your PDF

• (4 points) Write a program to compute the GCD using the above observations and binary operations where division by 2 of an even number in binary is done by removing the trailing 0 and shifting the string to the right. Similarly, multiplying by 2 means adding a zero to the right end. Write programs that convert numbers between decimal and binary strings consisting of ASCII '0's and '1's. For example, 42 should map to the string '101010' and vice versa. Write the routines to work with binary strings. Generate 100 random pairs of integers, including many large integers, convert them to binary strings and run your binary string GCD algorithm on these numbers. Check your work using a decimal GCD Include your program and output in both the PDF and ZIP

 less.

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of