Wednesday 28 December 2016

Data Structures and Algorithms


 Abstract data types,

An abstract data type (ADT) is basically a logical description or a specification of components of the data and the operations that are allowed, that is independent of the implementation.

ADTs are a theoretical concept in computer science, used in the design and analysis of algorithms, data structures, and software systems, and do not correspond to specific features of computer languages.

There may be thousands of ways in which a given ADT can be implemented, even when the coding language remains constant. Any such implementation must comply with the content-wise and behavioral description of the ADT.


Examples

For example, integers are an ADT, defined as the values 0, 1, −1, 2, 2, ..., and by the operations of addition, subtraction, multiplication, and division, together with greater than, less than, etc. which are independent of how the integers are represented by the computer. Typically integers are represented in  as binary numbers, most often as two's complement, but might be binary-coded decimal or in ones' complement, but the user is abstracted from the concrete choice of representation, and can simply use the data as integers.

Another example can be a list, with components being the number of elements and the type of the elements. The operations allowed are inserting an element, deleting an element, checking if an element is present, printing the list etc. Internally, we may implement list using an array or a linked list, and hence the user is abstracted from the concrete implementation.
Check this out for the above two implementations of the list ADT: CS13002 Programming and Data Structures


Why ADT?

To manage the complexity of problems and the problem-solving process,  abstractions are used to allow the user to focus on the “big picture” without getting lost in the details. By creating models of the problem domain, the user can efficiently focus on the problem-solving process.


Advantages


·         Encapsulation: The user does not need any technical knowledge of how the implementation works to use the ADT. In this way, the implementation may be complex but will be encapsulated in a simple interface when it is actually used.
·         Localization of change: Code that uses an ADT object will not need to be edited if the implementation of the ADT is changed, since any changes to the implementation must still comply with the properties and abilities specified in the ADT definition.
·         Flexibility: Different implementations of an ADT may be more efficient in different situations and it is possible to use each in the situation where they are preferable. Hence this flexibility increases the overall efficiency.
·         Easy to understand and reusable code.


Implementation


Modern object-oriented languages, such as C++ and Java, support implementation of ADT in the form of a class. You can use struct in C for the same.
Check out this sample C++ code for the implementation of Complex Numbers ADT


FAQ

What is the difference between an ADT and a data structure?
 Simply put,  ADT is more of a logical description, while a Data Structure is real, concrete thing.


2.  Arrays

Declaration of array is
int x[10];
int x[]={1,2,3,4,5,6,7,8,9,0};

 


·         In C, when an array is initialized with size, then it assigns defaults values to its elements in following order.
Data Type
Default Value
bool
false
char
0
int
0
float
0.0
double
0.0f
void
wchar_t
0

3.Stacks

·         Stack is an ordered list of similar data type.
·         Stack is a LIFO structure. (Last in First out).
·         push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.
·         Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.
operations −
·         push() − Pushing (storing) an element on the stack.
·         pop() − Removing (accessing) an element from the stack.
·         When data is PUSHed onto stack.
·         To use a stack efficiently, we need to check the status of stack as well. For the same purpose, the following functionality is added to stacks −
·         peek() − get the top data element of the stack, without removing it.
·         isFull() − check if stack is full.
·         isEmpty() − check if stack is empty.


Below mentioned are the time complexities for various operations that can be performed on the Stack data structure.
·         Push Operation : O(1)
·         Pop Operation : O(1)
·         Top Operation : O(1)
·         Search Operation : O(n)




To Do Infix prefix notation

Expression Parsing

·         Infix Notation
·         Prefix (Polish) Notation
·         Postfix (Reverse-Polish) Notation
Sr. No.
Infix Notation
Prefix Notation
Postfix Notation
1
a + b
+ a b
a b +
2
(a + b) ∗ c
∗ + a b c
a b + c ∗
3
a ∗ (b + c)
∗ a + b c
a b c + ∗
4
a / b + c / d
+ / a b / c d
a b / c d / +
5
(a + b) ∗ (c + d)
∗ + a b + c d
a b + c d + ∗
6
((a + b) ∗ c) - d
- ∗ + a b c d
a b + c ∗ d -

·         Precedence and associativity determines the order of evaluation of an expression. Following is an operator precedence and associativity table (highest to lowest) −
Sr. No.
Operator
Precedence
Associativity
1
Esponentiation ^
Highest
Right Associative
2
Multiplication ( ∗ ) & Division ( / )
Second Highest
Left Associative
3
Addition ( + ) & Subtraction ( − )
Lowest
Left Associative

http://www.sanfoundry.com/



4.Queues

A Queue is a linear data structure which basically stores the data sequentially. It follows First In First Out(FIFO) order. The following section deals with various implementations of Queue. It contains programs to implement Queue using an array, linked list and to implement a priority queue to add and delete elements. In a priority queue, values come out in order by priority.

operations associated with queues −
enqueue() − add (store) an item to the queue.
dequeue() − remove (access) an item from the queue.

Few more functions are required to make the above-mentioned queue operation efficient. These are −
peek() − Gets the element at the front of the queue without removing it.
isfull() − Checks if the queue is full.
isempty() − Checks if the queue is empty.

5. Linked lists

Types of Linked List

Doubly Linked List
Circular Linked List
Basic operations supported by a list.
Insertion − Adds an element at the beginning of the list.
Deletion − Deletes an element at the beginning of the list.
Display − Displays the complete list.
Search − Searches an element using the given key.
Delete − Deletes an element using the given key.


6. Trees.



Binary search trees,
Binary heaps,
AVL trees,
Search trees,
Graphs,
Types of graph,
Representation of graph in memory,
Applications.
Introduction to algorithms,
Searching,
Sorting,
Algorithms analysis,
Best, average, and worst case
analysis.
Asymptotic complexity, asymptotic notation. Algorithm design using divide ‐ and ‐
conquer, and greedy approach.






1. Two main measures for the efficiency of an algorithm are
c. Time and space
2. The time factor when determining the efficiency of algorithm is measured by
b. Counting the number of key operations
3. The space factor when determining the efficiency of algorithm is measured by
a. Counting the maximum memory needed by the algorithm
4. Which of the following case does not exist in complexity theory
d. Null case
5. The Worst case occur in linear search algorithm when
d. Item is the last element in the array or is not there at all
6. The Average case occur in linear search algorithm
a. When Item is somewhere in the middle of the array
7. The complexity of the average case of an algorithm is
a. Much more complicated to analyze than that of worst case
8. The complexity of linear search algorithm is
a. O(n)
9. The complexity of Binary search algorithm is
b. O(log n)
10. The complexity of Bubble sort algorithm is
c. O(n2)
11. The complexity of merge sort algorithm is
d. O(n log n)
12. The indirect change of the values of a variable in one module by another module is called
c. side effect
13. Which of the following data structure is not linear data structure?
d. None of above
14. Which of the following data structure is linear data structure?
c. Arrays
15. The operation of processing each element in the list is known as
d. Traversal
16. Finding the location of the element with a given value is:
b. Search
17. Arrays are best data structures
a. for relatively permanent collections of data
18. Linked lists are best suited
b. for the size of the structure and the data in the structure are constantly changing
19. Each array declaration need not give, implicitly or explicitly, the information about
c. the first data from the set to be stored

20. The elements of an array are stored successively in memory cells because
a. by this way computer can keep track only the address of the first element and the addresses of other elements can be calculated

1. The memory address of the first element of an array is called
d. base address

2. The memory address of fifth element of an array can be calculated by the formula
a. LOC(Array[5]=Base(Array)+w(5-lower bound), where w is the number of words per memory cell for the array

3. Which of the following data structures are indexed structures?
a. linear arrays

4. Which of the following is not the required condition for binary search algorithm?
c. There must be mechanism to delete and/or insert elements in list

5. Which of the following is not a limitation of binary search algorithm?
d. binary search algorithm is not efficient when the data elements are more than 1000.

6. Two dimensional arrays are also called
c. both of above

7. A variable P is called pointer if
a. P contains the address of an element in DATA.

8. Which of the following data structure can't store the non-homogeneous data elements?
a. Arrays

9. Which of the following data structure store the non-homogeneous data elements
b. Records

10. Each data item in a record may be a group item composed of sub-items; those items which are indecomposable are called
d. all of above

11. The difference between linear array and a record is
d. All of above

12. Which of the following statement is false?
c. pointers store the next data element of a list

13. Binary search algorithm can not be applied to
a. sorted linked list

14. When new data are to be inserted into a data structure, but there is no available space; this situation is usually called
b. overflow

15. The situation when in a linked list START=NULL is
a. underflow

16. Which of the following is two way list?
d. none of above

17. Which of the following name does not relate to stacks?
a. FIFO lists

18. The term "push" and "pop" is related to the
c. stacks

19. A data structure where elements can be added or removed at either end but not in the middle
d. Deque

20. When inorder traversing a tree resulted E A C K F H D B G; the preorder traversal would return
b. FAEKCDHGB

1.    Which data structure allows deleting data elements from front and inserting at rear?
b. Queues

2.    Identify the data structure which allows deletions at both ends of the list but insertion at only one end.
a. Input-restricted deque

3.    Which of the following data structure is non-linear type?
d. None of above

4.    Which of the following data structure is linear type?
d. All of above

5.    To represent hierarchical relationship between elements, which data structure is suitable?
c.   Tree

6.    A binary tree whose every node has either zero or two children is called
c. Extended binary tree

7.    The depth of a complete binary tree is given by
d. Dn =  log2n + 1

8.    When representing any algebraic expression E which uses only binary operations in a 2-tree,
a. the variable in E will appear as external nodes and operations in internal nodes

9.    A binary tree can easily be converted into q 2-tree
d. by replacing each empty sub tree by a new external node

10.  When converting binary tree into extended binary tree, all the original nodes in binary tree are
a. internal nodes on extended tree

11. The post order traversal of a binary tree is DEBFCA. Find out the pre order traversal
c.   ABDECF

12.  Which of the following sorting algorithm is of divide-and-conquer type?
c.   Quick sort

13.  An algorithm that calls itself directly or indirectly is known as
b. Recursion

14.  In a binary tree, certain null entries are replaced by special pointers which point to nodes higher in the tree for efficiency. These special pointers are called
d. thread

15.  The in order traversal of tree will yield a sorted listing of elements of tree in
b. Binary search trees

16.  In a Heap tree
b. Values in a node is greater than every value in children of it

17.  In a graph if e=[u, v], Then u and v are called
d. all of above

18.  A connected graph T without any cycles is called
d. All of above

19.  In a graph if e=(u, v) means
d. both b and c

20. If every node u in G is adjacent to every other node v in G, A graph is said to be
b. complete