Storage Management

Question 1

What are Algorithms?

Answer 1

Algorithm
◦ An algorithm is a finite sequence of well-defined, computer-implementable
(optional) instructions, typically to solve a class of specific problems or to perform a
computation.
◦ Algorithms are always unambiguous and are used as specifications for performing
calculations, data processing, automated reasoning, and other tasks.
◦ An algorithm must terminate

Question 2

What is a Computer Program?

Answer 2

Program
◦ A computer program is a collection of instructions that can be executed by a
computer to perform a specific task
◦ A computer program is usually written by a computer programmer in a
programming language.
◦ A programs implements an algorithm
◦ A program may or may not terminate. For example, an OS

Question 3

On what basis algorithms are compared?

Answer 3

1. Time
2. Space

Question 4

What are Counting Models in analysis of algorithms?

Answer 4

Counting Models
* Core Idea: Total running time = Sum of cost × frequency for all operations
◦ Need to analyze program to determine set of operations
◦ Cost depends on machine, compiler
◦ Frequency depends on algorithm, input data
* Machine Model: Random Access Machine (RAM) Computing Model
◦ Input data & size
◦ Operations
◦ Intermediate Stages
◦ Output data & size

Question 5

What are Asymptotic Analysis in Analysis of Algorithm?

Answer 5

Asymptotic Analysis
* Core Idea: Cannot compare actual times; hence compare Growth or how time increases
with input size
◦ Function Approximation (tilde (˜) notation)
◦ Common Growth Functions
◦ Big-Oh (O(.)), Big-Omega (Ω(.)), and Big-Theta (Θ(.)) Notations
◦ Solve recurrence with Growth Functions

Question 6

What are some of the common order of growth classifications?

Answer 6

O(1), O(N), O(log N), O(N log N), O(N^2), O(N^3) and 2^N

Question 7

What are various data configurations or scenarios for analysis?

Answer 7

Best Case
▷ Minimum running time on an input
◦ Worst Case
▷ Running time guarantee for any input of size n
◦ Average Case
▷ Expected running time for a random input of size n
◦ Probabilistic Case
▷ Expected running time of a randomized algorithm
◦ Amortized Case
▷ Worst case running time for any sequence of n operations

Question 8

What are Data Structures?

Answer 8

A data structure specifies the way of organizing and storing
in-memory data that enables efficient access and modification of the data.
Linear Data Structures
◦ Non-linear Data Structures
* Most data structure has a container for the data and typical operations that its needs to perform.
Efficiency is measured in terms of time and space taken for these operations.

Question 9

What are some of key operations relating to data structures

Answer 9

1. Create
2. Insert
3. Delete
4. FInd/ Search
5. Close

Question 10

What are Linear Data Structures?

Answer 10

A Linear data structure has data elements arranged in linear or sequential manner such
that each member element is connected to its previous and next element.
Examples of linear data structures are Array, Linked List, Queue, Stack, etc.
Different examples of linear data structure:
* Array: The data elements are stored at contiguous locations in memory.
* Linked List: The data elements are not required to be stored at contiguous locations in memory. Rather each element stores a link (a pointer to a reference) to the location of the next element.
* Queue: It is a FIFO (First In First Out) data structure. The element that has been
inserted first in the queue would be removed first. Thus, insert and removal of the elements in this take place in the same order.
* Stack: It is a LIFO (Last In First Out) data structure. The element that has been
inserted last in the stack would be removed first. Thus, insert and removal of the
elements in this take place in the reverse order.

Question 11

What are characteristics of Arrays?

Answer 11

1. Random access using its index at constant time.
2. Elements are stored in contiguous locations.
3. Fixed Sizes, not flexible
4. Insertion / removal at random location/arbitrary position is costlier O(N) but insertion / removal at end is O(1)

Question 11

What are characteristics of Linked Lists?

Answer 11

1. Elements are not required to be contiguous
2. Each element is stored in a node. A node has two parts:
   ◦ Info: stores the element.
   ◦ Link: stores the location of the next node
3. Flexible in size
4. insertion or removal of an element at/from any arbitrary position is efficient.
5. Random access not possible. Only sequential access.

Question 12

What is Linear Search?

Answer 12

The algorithm starts with the first element, compares with the given key value and returns yes if they
match.
* If it does not match, then it proceeds sequentially comparing each element of the list with the given key
until a match is found or the full list is traversed.

Question 13

What is Binary Search?

Answer 13

1. Input is sorted list.
2. Compares middle element and based on the result eliminates half of the search inputs thus reducing the search time to O(Log N)

Question 14

What are Non linear data structures?

Answer 14

Nonlinear data structures are those data structures in which data items are not
arranged in a sequence and each element may have multiple paths to connect to other elements.

Common Non-Linear Data Structures include:
◦ Graph: Undirected or Directed, Unweighted or Weighted, and variants
◦ Tree: Rooted or Unrooted, Binary or n-ary, Balanced or Unbalanced, and variants
◦ Hash Table: Array with lists (coalesced chains) and one or more hash functions
◦ Skip List: Multi-layered interconnected linked list

Question 15

What are Graphs Data Structure?

Answer 15

Graphs: Graph G is a collection of vertices V (store the elements) and connecting
edges (links) E between vertices: G =< V, E > where E ⊆ V × V
A graph may be:
◦ Undirected or Directed
◦ Unweighted or Weighted
◦ Cyclic or Acyclic
◦ Disconnected or Connected

Question 16

What is a Tree Data Structure?

Answer 16

Tree: Is a connected acyclic graph representing hierarchical relationship

A tree may be:
◦ Rooted or Unrooted
◦ Binary or n-ary
◦ Balanced or Unbalanced
◦ Disconnected (forest) or Connected

Properties of a Tree: Root, Parent, Child, Leaf, Internal nodes, Subtree, Path, Siblings,
Arity: Number of children of a node., Levels, Height

Question 17

What are some of the facts regarding Tree Data Structure?

Answer 17

• Fact 1: A tree with n nodes has n − 1 edges
• Fact 2: The maximum number of nodes at level l of a binary tree is 2l
  .
• Fact 3: If h is the height of a binary tree of n nodes, then:
  ◦ h + 1 ≤ n ≤ 2
  h+1 − 1
  ◦ ⌈lg(n + 1)⌉ − 1 ≤ h ≤ n − 1
  ◦ O(lg n) ≤ h ≤ O(n)
  ◦ For a k-ary tree, O(lgk n) ≤ h ≤ O(n)

Question 18

What is a Hash Table(Hash Map)?

Answer 18

Hash Table (Hash Map): implements an associative array abstract data type, a
structure that can map keys to values by using a hash function to compute an index
(hash code), into an array of buckets or slots, from which the desired value can be found

A hash table may be using:
◦ Static or Dynamic Schemes
◦ Open Addressing
◦ 2-Choice Hashing

Question 19

What are Binary Search Trees?

Answer 19

Binary Search Tree (BST): Is a tree in which all the nodes hold the following:
◦ The value of each node in the left sub-tree is less than the value of its root
◦ The value of each node in the right sub-tree is greater than the value of its root

Searching: Worst Case - O(N) ; Best Case - O(Log N)

Question 20

What is storage hierarchy?

Answer 20

Based on Speed/Cost per bit
1. Fastest - Primary Storage - Cache , Main Memory - Volatile, very fast
2. Secondary Storage- Non volatile, Moderately fast - Flash Memory, Magnetic Disk
3. Tertiary Storage - Non-Volatile, Slow - Optical Disk, Magnetic Tapes.

Question 21

Magnetic disc architecture?

Answer 21

Surface of platter divided into circular tracks

Each track is divided into sectors

A sector is the smallest unit of data read or written
◦ Sector size typically 512 bytes
◦ Sectors / track: 500 to 1k (inner) to 1k to 2k (outer)

Cylinder i consists of i th track of all the platters

Disk Controller: interfaces between the computer system and the disk drive hardware

Disk Interface Standards Families: ATA, SATA, SCSI, SAS, several variants

Question 22

Magnetic Disks Performance Measures

Answer 22

Access Time: time from a read or write request issue to start of data transfer:

Seek Time: time to reposition the arm over the correct track

Rotational Latency: time for the sector to be accessed to appear under the head

Data-transfer Rate: the rate at which data can be retrieved from or stored to the disk

Mean Time To Failure (MTTF): Avg. time the disk is expected to run continuously without any failure

Question 23

What are Solid State Disks?

Answer 23

solid state disks: Use multiple flash storage devices to provide higher transfer rate of 100
to 200 MB/sec

Question 24

What is a DNA Digital Storage?

Answer 24

DNA digital data storage is the process of encoding and decoding binary data to and from
synthesized strands of DNA.

Question 25

What is Quantum Memory?

Answer 25

Quantum memory is the quantum-mechanical version of ordinary computer memory
* Whereas ordinary memory stores information as binary states (represented by ”1”s and
”0”s), quantum memory stores a quantum state for later retrieval
* These states hold useful computational information known as qubits
* Quantum memory is essential for the development of many devices in quantum
information processing applications such as quantum network, quantum repeater, linear
optical quantum computation or long-distance quantum communication
* Unlike the classical memory of everyday computers, the states stored in quantum
memory can be in a quantum superposition, giving much more practical flexibility in
quantum algorithms than classical information storage

Question 26

Database File Organization?

Answer 26

A database is
◦ A collection of files. A file is
▷ A sequence of records. A record is
− A sequence of fields

A database file is partitioned into fixed-length storage units called blocks
◦ Blocks are units of both storage allocation and data transfer

Question 27

40