Please I need this ASAP. Help me out.... Use C++ ,language if necessary. SHORT A
ID: 3842666 • Letter: P
Question
Please I need this ASAP. Help me out.... Use C++ ,language if necessary.
SHORT ANSWER SECTION - Provide in depth answers in your own words.
1. Compare and Contrast Dynamic vs Static memory and where in RAM memory each type of structure is placed. Describe Virtual Memory.
2. Compare and contract Linked List data structure to Array data structure.
3. (a) Briefly describe Abstract Data Types (ADT) or Abstract Data structures in general.
3. (b) 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.
4. Why is look-up faster for a Binary Tree then Linked List?
5. Why is it difficult to perform a binary search on a linked list?
6. Describe the process of analyzing the Big O Notation for a Stack or Queue.
7. 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.
(a) Array of Doubles that contains 100,000 elements.
(b) Linked List of chars contains 1,000,000 nodes.
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)
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. Compare and Contrast Dynamic vs Static memory:
Static Memory: Static Memory devices are semiconductor memories in which the stored data will remain permanently stored as long as power is applied without the need of periodically rewriting or refreshing the data into the memory. The basic element of this storage is a flip flop or a gate. SRAM, Punched Card and Tape are examples of Static Memory.
Dynamic Memory: Dynamic Memory devices are semiconductor memories in which the stored data will not remain permanently stored, even with power applied unless the data is periodically rewritten into the memory. Data is stored as charge on capacitors. The charge on capacitor has to be periodically refeshed in order to prevent it from leaking away. DRAM & Charge Coupled Device (CCD) are example of Dynamic Memory.
Static RAM (SRAM)
The word static indicates that the memory retains its contents as long as power is being supplied. However, data is lost when the power gets down due to volatile nature. SRAM chips use a matrix of 6-transistors and no capacitors. Transistors do not require power to prevent leakage, so SRAM need not be refreshed on a regular basis.
There is extra space in the matrix, hence SRAM uses more chips than DRAM for the same amount of storage space, making the manufacturing costs higher. SRAM is thus used as cache memory and has very fast access.
->Used as cache memory
Dynamic RAM (DRAM):
DRAM, unlike SRAM, must be continually refreshed in order to maintain the data. This is done by placing the memory on a refresh circuit that rewrites the data several hundred times per second. DRAM is used for most system memory as it is cheap and small. All DRAMs are made up of memory cells, which are composed of one capacitor and one transistor.