1. Compare and Contrast Dynamic vs Static memory and where in RAM memory each ty

Question

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.

Explanation / Answer

1.

1. Inside a dynamic RAM chip, each memory cell holds one bit of information and is made up of two parts i.e., a transistor and a capacitor where as in static RAM, a form of flip-flop holds each bit of memory.

2. Static RAM containing six transistors is faster than dynamic RAM.

3. Static RAM is very expensive and faster so that it is used in designing cache part of the RAM while dynamic RAM forms the larger system RAM space.

Virtual memory is a memory management technique which comes in to picture when physical space shortages are happened. In the Virtual Memory the Physical Memory (Hard Disk) will be treated as the Logical Memory. Means with the help of virtual Memory we can also increase the size of Logical Memory as from the Physical Memory.

2.

1. Access in Linked list data structure is done in sequential way whereas it is done in random manner in Array data structure.

2. In array data structure elements are stored in consecutive memory locations and in linked list pointers are used to store the elements.

3. In Linked List we have to Just Change the Pointer address field (Pointer),So Insertion and Deletion Operations are quite easy to implement. In contrsat space has to be created to perform operations in array structure.

4. Stack uses Static Memory Allocation and Linked List Uses Dynamic Memory Allocation.

3. Abstract data types are mathematical models of a set of data values or information that share similar behavior or qualities and that can be specified and identified independent of specific implementations. An ADT is a collection of data and associated operations for manipulating that data. ADTs support abstraction, encapsulation, and information hiding.They provide equal attention to data and operations.

4. In a linked list, the items are linked together through a single next pointer. In a binary tree, each node can have 0, 1 or 2 subnodes, where (in case of a binary search tree) the key of the left node is lesser than the key of the node and the key of the right node is more than the node. As long as the tree is balanced, the searchpath to each item is a lot shorter than that in a linked list. Thus the binary tree is fast for lookup, but not nessecarily fast for insertion or deletion.

5. Binary search algorithm is based on the logic of reducing your input size by half in every step until your search succeeds or input gets exhausted. Binary Search is particularly used in cases where the size of the input set ofdata is large and hence this approach provides better result in comparison with the linear search technique. It is difficult to perform a binary search on a linked list.

This is because in an array, accessing the middle index between two given array indices is easy and fast. It usually involves finding out the average of the two indices and accessing that particular element. Thus the running time is constant .i.e. O (1).However in linked list, To access the middle node, we need to traverse the entire list, node by node and keep a count of the elements, and then traversing again up to half the counted value to go to the middle element. So we choose gor alternative.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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