CS 5390/4390, Final Exam

Date: Wednesday, December 7, 2005
Name (please type legibly, ideally in block letters): ______________________________________________________________________

Please place your name on all extra sheets. Two page of notes allowed (with notes on both sides).

1-4) In a symmetric graph with four vertices A, B, C, and D, we have the following distances: AB=1, BD=2.0, CD=3.0, and BC=1.5. Use Bellman-Ford and Dijkstra's algorithms to find the shortest paths from A to all other vertices. Use the matrix multiplication and Warshall algorithms to find all the shortest paths. Illustrate each of the algorithms step by step.

5) Give an example why the shortest path algorithms are not sufficient for the forward problem in geosciences.

6) Suppose that the values of slownesses are: s(0,0)=1, s(0,1)=1.5, s(1,0)=0.4, s(1,1)=0.3. The signal is sent from the point (0,0). Use the Fast Marching Method to find all the traveltimes.

7) Suppose that on the first iteration of the Fast Marching Algorithm, there are three boundary points, and the traveltime values at these points are estimated as 5, 10, and 2. Starting with the first value (5), and following up with the two other values (10 and 2) show how these values will be ordered into a min-heap. Reminder: we add a new value so as to make it a balanced binary tree, and then update the tree to preserve the min-heap property.

8) A signal is emitted at an angle of 60 degrees to the surface; after travelling through the original cell, with slowness 2, it reaches a vertically neighboring cell in which the slowness is 1.41 (approximately sqrt(2)). Use Snell's law to describe where the signal will go next. Reminder: sine of 30 degrees is 1/2, sine of 45 degrees is 1/sqrt(2).

9) Let us assume that the initial value of slowness in the cell is 1.2. There are three paths going through this cell:

If we use Hole's algorithms, what will be the value of the slowness in this cell on the next iteration? Explain your answer step by step.

10-12) Use the Least Squares Methods (LSM) to solve the following over-determined system of equations: x1 ~ 20.0; x1 + x2 ~ 21.0; x1 - x2 ~ 10.0. Explain where the formulas for LSM come from. Describe the above system in matrix form, and show that the matrix-based LSM leads to exactly the same solution.

13) Use the regularization technique to find the values x1 and x2 from the under-determined system of equations x1 - x2 ~ 10.0.

14-16) The travel-time is equal to the product of slowness s and length L. The measured value of slowness is 12.0, the measured value of length is 5.0. The standard deviation of the slowness is 1.0, the standard deviation of length is 0.1. Compute the resulting standard deviation of travel-time by using the following two methods:

What are the main drawbacks of these methods? Describe the Monte-Carlo method and explain how it can avoid these drawbacks.

17-19) Let us now assume that the measured values of slowness and length are the same as in the previous Problem 14-16), but that instead of the probabilistic uncertainty, we only know the upper bounds on the measurement errors:

Compute the interval of possible values of travel-time by using the following three methods: What are the main drawbacks of these methods? Briefly describe the the interval Monte-Carlo method, and explain how this method can avoid the above drawbacks.

20) Briefly describe what your project was about, what you have done as part of your project, and describe one more project presentation.