NEED HELP PLEASE

Wk4 Question 1 (Please show and explain all your work!)

You are an electrical engineer designing a new integrated circuit involving potentially millions of components. How would you use graph theory to organize how many layers your chip must have to handle all of the interconnections? Which properties of graphs come into play in such a circumstance?

Wk4 Question 2 Please show and explain all your work!)

Describe several different algorithms for determining whether a graph is planar. What is the computational complexity of each of these algorithms?

Wk4 Question 3 Please show and explain all your work!)

7. Describe dynamic algorithms for data compression based on letter frequencies as they change as characters are successively read, such as adaptive Huffman coding.

8. Explain how alpha-beta pruning can be used to simplify the computation of the value of a game tree.

9. Describe the techniques used by chess-playing programs such as Deep Blue.

10. Define the type of graph known as a mesh of trees. Ex- plain how this graph is used in applications to very large system integration and parallel computing. Writing Projects 809

11. Discuss the algorithms used in IP multicasting to avoid loops between routers.

12. Describe an algorithm based on depth-first search for finding the articulation points of a graph.

Wk4 Question 4 Please show and explain all your work!)

4. Discuss what can be learned by investigating the proper- ties of the Web graph.

5. Explain what community structure is in a graph representing a network, such as a social network, a computer network, an information network, or a biological network. Define what a community in such a graph is, and explain what communities represent in graphs representing the types of networks listed.

6. Describe some of the algorithms used to detect communities in graphs representing networks of the types listed in Question 5.

7. Describe algorithms for drawing a graph on paper or on a display given the vertices an edges of the graph. What Writing Projects 743 considerations arise in drawing a graph so that it has the best appearance for understanding its properties?