Consider the algorithm below, which operates on a given array A of n numbers. Th

Question

Consider the algorithm below, which operates on a given array A of n numbers. The algorithm assumes that arrays are indexed from item 0 (hence, n items are indexed from 0 to n - 1). What is the purpose of the algorithm? Show your work/reasoning. Using a loop invariant, prove that it correctly functions. Find a tight Theta-bound for its running time complexity. Clearly explain. For each of the two situations below, pick a data structure (from those discussed in lecture) that is best suited for that use-case. If more than one data structure is best, discuss the trade-offs. For example, if you want to store the names of the calendar months and access them by month number then an array is best because the number of months Ls fixed and access by index is O(1). You want to store your company phone directory such that you can lookup a phone number by person's name. You want to be able to add/remove people as well. You want to keep track of decisions made while trying to escape a maze such that if you make a wrong decision (get stuck at a dead end), you are able to easily backtrack and continue out of the maze.

Explanation / Answer

1)
a) this algorithm is to sort the numbers increasing order...
since it was checking for number..if greater than ...we are swapping places.
b)Since in both loops we are using maximum limit as n which was not modifying inside these
two loops...so they will exit at propert time.
c)Since it was two loops..they both will execute (n+1) steps.
so the both loops take (n+1)*(n+1) = ~~O(n^2)

---------------------------------------------------------------------------
2)
a)
Since you want to store phone directory....the names are stored as per aplhabetic order.
So you want to add, look up (search), and also able to delete...
So best datastructure to handle this "TRIE"...to insert and search it was best algorithm.
If we use binary search tree it would take O(n+logn) time where in TRIE algorithm
it would take only O(n) time.

b)
This type of maze problem better data structure algorithm was back tracking algorithm.
It is similar to brute force approach...Every time it will check for good decisions...
at any time if wrong decision came across, then it will go back step and check whether
there is a way for good decision...this process will be continue until solution is
got to user.
It uses O(2^n) run time

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.