Question

You are writing a program to provide driving directions. You start with the simple case of driving along Interstate 55. You have a list of cities along I55: Chicago, Downers Grove, Bolingbrook, Plainfield, Joliet, Channahon, etc. You know the distance from each city to the next one on the list. You want to be able to determine the distance between any pair of cities. Assuming there is a total of n cities, one way to do this is to have as a data structure an array D where D[k] is the distance from city k to city k+1. The algorithm for finding the distance from city i to city j then adds up the entries from D[i] to D[j-1]. The data structure requires n entries and the algorithm performs, in the worst case, n additions. Another way is to have as a data structure an n x n table T where T[i, j] is the distance from city i to city j. The algorithm for finding the distance between city i to city j simply prints out the value of T[i, j]. The data structure here requires n^2 entries and so n^2 steps to initialize, and the distance algorithm performs a single look-up. Please submit a data structure containing n entries and requiring n steps to initialize and a distance algorithm written in pseudocode performing a constant number of operations to determine the distance between any two cities.

Answer 1

DATA STRUCTURE

class dataStruct
  
   integer array
   array size
  
   constructor:
       for loop of 0 to array size
           initialize array of length "array size"
  

ALGORITHM

   create dataSTruct
   initialize values

   returning distance till integer array [ some index ]
   create variable distance = 0
   for loop of 0 to (some index - 1)
       distance = distance + array distance on index from 0 to (some index)
   print distance

COMMENT DOWN FOR ANY QUERIES AND,

LEAVE A THUMBS UP IF THIS ANSWER HELPS YOU.