Reference no: EM131226736
Question 1. Show a recursion tree for T(n) = T(n-1) + T(n-2) + 1. Provide upper and lower asymptotic bounds on T(n).
Question 2. Consider the weighted graph G in Figure 23.1. Wherever there is a weight w(u,v), replace that weight with 20-w(u,v).
(a) Display this new weighted graph.
(b) Trace Kruskal's Algorithm on the graph. That is, show the order in which edges are added to the minimum-spanning tree.
(c) Trace Prim's Algorithm on the graph for two different roots, a and e. That is, show the order in which edges are added to the minimum-spanning tree.
Question 3. Trace the Bellman-Ford Algorithm on the graph in Figure 24.4 using z as the start vertex.
Question 4. Trace Dijkstra's Algorithm on the graph in Figure 24.6 using z as the start vertex.
Question 5. Suppose (u,v) is the minimum-weight edge incident on u in a graph G, where G is undirected, connected, and weighted. Assume all weights are distinct. Show that (u,v) belongs to some minimum spanning tree of G. Hint: If T is a spanning tree without (u,v), show to construct a spanning tree T0 that includes (u,v) and has a lower total weight
Question 6. Using the the Bellman-Ford algorithm as a subroutine, write an algorithm in pseudocode to determine if a directed graph G contains a cycle. What is the running time of your algorithm
Question 7. In pseudocode, write an algorithm to count all the simple paths in a graph, including paths of length 0. Don't worry about creating an efficient algorithm. Hint: Write it recursively with one parameter equal to the vertices not in the current path. What is the running time of your algorithm?
|
Small and unknown firm
: Because it's a relatively small and unknown firm, its liquidity risk premium is about 1.8% even on relatively short debt like this. What pure interest rate is implied by these assumptions? Round your answer to one decimal place.
|
|
What determines one sexual orientation
: Why is it important to understand what determines one's sexual orientation? Consider ethical, legal, and social implications. If you do not think it is important to understand the origins, please explain.
|
|
Calculate the resistance
: Calculate both, as well as the resistances at 5.05 mA and at 1 mA (the mean currents of each kind). What do you conclude?
|
|
Successfully without worrying about inflation
: First we want to make sure you understand how to combine use of these formulas successfully without worrying about inflation. Later in the course after many of you have posted we can have some discussion on how to account for inflation.
|
|
Trace the bellman-ford algorithm
: Display new weighted graph - Trace Kruskal's Algorithm on the graph. That is, show the order in which edges are added to the minimum-spanning tree.
|
|
Explain the process of coagulation relating to water
: Explain the process of coagulation and flocculation relating to water. Explain the process of filtration systems from waterborne illnesses. What is cholera? How is one exposed to it and where can it be found?
|
|
What factors affect language acquisition
: What factors affect language acquisition? Which factor do you believe has the largest influence on language acquisition? Why? When we do perceive mispronunciations correctly, is that learned or innate?
|
|
What is the growth rate of stock dividends
: The current dividend for Company Y's stock is $3.20/per share. The current Company Y's stock price is $21.25/per share. Suppose this stock's discount rate is the same as that in question a) of problem 3. What is the growth rate of this stock's div..
|
|
Describe the project management activities and variables
: Describe information system problems resulting from poor project management. Define project management. List and describe the project management activities and variables addressed by project management.
|