NEED RESPONSE ASAP. PLEASE ANSWER COMPLETELY. WILL GIVE THUMBS UP FOR A CORRECT
ID: 3842863 • Letter: N
Question
NEED RESPONSE ASAP.
PLEASE ANSWER COMPLETELY. WILL GIVE THUMBS UP FOR A CORRECT COMPLETE ANSWER.
1. Memory Allocation Analysis: Describe your process for calculating memory required for the following examples. Give an estimate in MB/GB of the amount of memory required in RAM.
(a) Array of Doubles that contains 100,000 elements.
(b) Linked List of chars contains 1,000,000 nodes.
2. Describe the purpose of implementing a Queue, Stack, or Hashmap on an Array or Linked List. Describe why one would implement a Queue, Stack, or Hashmap.
3. 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.
A. Empty() check method on Stack of 1000 elements with array as underlying data structure O(1) B. Traversing a Linked List from the Last Node to the Head Node O(n) C. Look Up of Node in a 100,000 element Binary Search Tree O(n^2) D. Traversing every node in Queue with array as underlying data structure O(log n) E. Accessing key in 1,000,000 element Hash Map O(n log n)Explanation / Answer
1. Memory Allocation Analysis: Describe your process for calculating memory required for the following examples. Give an estimate in MB/GB of the amount of memory required in RAM.
(a) Array of Doubles that contains 100,000 elements. : each element of double takes 8 bytes , So
1,00,000 *8 = 800000 bytes = 0.8MB
(b) Linked List of chars contains 1,000,000 nodes.
Linked list as we know uses self referential structure:
Size of Struct = 4+4 = 8 bytes [ 4 is added becuase it will take size of largest data type and pointer address is 4 bytes
1,000,000 nodes. = 1,000,000 *8 = 8000000 bytes = 8 MB
2. Describe the purpose of implementing a Queue, Stack, or Hashmap on an Array or Linked List. Describe why one would implement a Queue, Stack, or Hashmap.
We implement Queue and Stack using array and LinkedList because we can take the advantage of these data structure. It helps us the way data is organised.
Like in Queue, if we want the data in order of way we visted So we can use queue [FIFO].
Queue helps us retirve information in First In First Out
For Stack its the other way around, if we want the data to accessed in Last In first Out manner we use stack
So basically we can take advantage of these constructs in many ways. They helps us solve complex problems and we are able to relate these constructs to real world problems like
1) Standing in a line for ticket represents a queue because the person who is the the first place will get the ticket first
2) Piling books on top of the other represents Stack because the last book we kep will be our first book.
HashMap is basically used to store a Key value pair, Suppose we have one to one mapping of keys and value. We would like to use HashMap that for a given key it helps us retireve the value in fast manner.
Hence retireval of information in faster manner is the benefit of using HashMap
3. 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.
Explanation as why I chosed them
A : isEmpty can be done by jist checking my top index if top is -1 means stack is emoty hence its O(1)
B: Traversing mesna we will be accessing N elements and this will take N time
C: Look up in BST takes log N time because of its height
D:As we said when we traverse every node we require N time
E : Accessing a key in map is very fast it takes O(1) time to access
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.