CS 5390/4390, Exam #1

Date: Monday, September 23, 2005
Name (please type legibly, ideally in block letters): ______________________________________________________________________

Please place your name on all extra sheets. One 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=BD=CD=1 and AD=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)=s(0,1)=1, s(1,0)=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 3, 2, and 1. Starting with the first value (3), and following up with the two other values (2 and 1) 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 30 degrees to the surface; after travelling through the original cell, with slowness 1, it reaches a vertically neighboring cell in which the slowness is 0.5. Use Snell's law to describe where the signal will go next. Reminder: sine of 30 degrees is 1/2.