Thanks in advance, SHORT ANSWER SECTION - Provide in depth answers in your own w
ID: 3862058 • Letter: T
Question
Thanks in advance,
SHORT ANSWER SECTION - Provide in depth answers in your own words.
1. (5 Points) Describe data structures in your own words.
2. (5 Points) What is n, in Big O notation? O(n), O(n ^2), etc.
3. (10 Points) Describe best case, average case, and worst case in terms of Big O Notation. When implementing algorithms or data structures which two “Big O cases” are most important to consider and why?
3. (10 Points) Compare and Contrast Sequential Access to Random Access and give examples of algorithms or data structures that align with both concepts.
4. (10 Points) Explain the “trade offs or decisions” required when writing/creating computer programs and how the “decisions” relate to Data Structures, algorithms, and Big O notation.
5. (10 Points) Describe divide and conquer algorithms in your won words. Why are divide and conquer algorithms useful?
Big O SECTION List appropriate Worst Case Big O Notation under the different algorithms or data structure operations.
Choose from right column and place under left column.
Right column can be used more than once or not all.
Leftcolumn Right column
A. Quicksort Recursive Algorithm on an Array of 100,000 elements ========== O(1)
B. Binary Search on sorted array of 100,000 elements =====================O(n)
C. Iterating over an array =========================================O(n^2)
D. Deleting last element in an array of 10 elements===================== O(log n)
E. Accessing first element in Array of 1,000,000 elements ===============O(n log n)
Explanation / Answer
1.Data structure is a collection of elements and the relationship among them ,it gives a particular way to organise the data.User defined Data structures are also implemeted from the abstract data type (ADT) by speficying the data type and operations on the data.Data structures are the concrete implementation of specific ADT.
2.In Big-O notation let O(n) means the number of statements executed for a function to produce the result,which determines the order of magnitude of the result.
let f(n)=n2+n then O(f(n))=O(n2) (by removing smaller factors )
3.Sequential file accessing: Sequential file is a file that must be processed serially starting at h=the beginning,it is ordered on the key.it does not have any random processing capabilities.For a sequential master file if any update operation performed on it , it will re-create the master file and maintain old-master file and new-master file.Example-Merge sort
Random file accessing:These files data is accessed randomly with in the file.Example-Binary search trees, quick sort
4.Data processing is about efficiency,the mechanism for measuring the efficiency of algorithms is Big-O notation. Here there is a trade-off between speed and memory or between space and time.If we want more time efficiency then less space efficiency and vice versa. Need to choose best filt algorithms based on the requirement to get the efficency in data accessing or we can use combination as well.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.