Graduation Year

2010

Document Type

Thesis

Degree

M.S.Cp.E.

Degree Granting Department

Computer Science and Engineering

Major Professor

Rahul Tripathi, Ph.D.

Co-Major Professor

Lawrence O. Hall, Ph.D.

Committee Member

Sudeep Sarkar, Ph.D.

Keywords

algorithm analysis; data structures; Dijkstra's algorithm; dynamic programming; experimental algorithmics; graphs and trees

Abstract

The paper \A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges" by

Aaron Bernstein and David Karger lays out a nearly optimal algorithm for nding the

shortest distances and paths between vertices with any given single failure in constant

time without reconstructing the oracle. Using their paper as a guideline, we have

implemented their algorithm in C++ and recorded each step in this thesis. Each step

has its own pseudo-code and its own analysis to prove that the entire oracle construction

stays within the stated running time and total space bounds, from the authors. The

effciency of the algorithm is compared against that of the brute-force methods total

running time and total space needed. Using multiple test cases with an increasing

number of vertices and edges, we have experimentally validated that their algorithm

holds true to their statements of space, running time, and query time.

Share

COinS