CONTENTS KCS 301 : DATA STRUCTURE
UNIT - 1 : ARRAYS AND LINKED LISTS
(1–1 A to 1–51 A)
Introduction: Basic Terminology, Elementary Data Organization, Built in Data Types in C. Algorithm, Efficiency of an Algorithm, Time and Space Complexity, Asymptotic notations: Big Oh, Big Theta and Big Omega, Time-Space trade-off. Abstract Data Types (ADT).
Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and Column Major Order, Derivation of Index Formulae for 1-D, 2-D, 3-D and n-D Array. Application of arrays, Sparse Matrices and their representations.
Linked lists: ArrayImplementation &Pointer Implementationof SinglyLinked Lists, Doubly Linked List, Circularly Linked List, Operations on Linked List. Insertion,Deletion,Traversal,PolynomialRepresentation&AdditionSubtraction & Multiplications of Single variable & Two variables Polynomial.
UNIT - 2 : STACKS AND QUEUES
(2–1 A to 2–38 A)
Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array & Linked Implementation of Stack in C, Application of stack: Prefix and PostfixExpressions, Evaluationof postfixexpression, Iteration and RecursionPrinciples of recursion, Tail recursion, Removal of recursion Problem solving using iteration and recursion with examples such as binary search, Fibonacci numbers and Hanoi towers. Tradeoffs between iteration and recursion. Queues: Operations onQueue: Create, Add,Delete, Full &Empty, Circularqueues, Array & linked implementation of queues in C, Dequeue & Priority Queue.
UNIT - 3 : SEARCHING & SORTING
(3–1 A to 3–24 A)
ConceptofSearching, Sequentialsearch, Index SequentialSearch, BinarySearch. Concept of Hashing & Collision resolution Techniques used in Hashing. Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Merge Sort, Heap Sort and Radix Sort.
UNIT - 4 : GRAPHS (4–1 A to 4–41 A)
Terminology used with Graph, Data Structure for Graph Representations: Adjacency Matrices, Adjacency List, Adjacency. Graph Traversal: Depth First Search & Breadth First Search, Connected Component, Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm. Transitive Closure &ShortestPath algorithm: Warshal Algorithm& Dijikstra Algorithm.
UNIT - 5 : TREES (5–1 A to 5–51 A)
Basic terminology used with Tree, Binary Trees, Binary Tree Representation: Array Representation and Pointer (Linked List) Representation, Binary Search Tree, Strictly Binary Tree, Complete Binary Tree. A Extended Binary Trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Constructing Binary Tree from given Tree Traversal, Operation of Insertation, Deletion, Searching & Modification of data in Binary Search. Threaded Binary trees, Traversing Threaded Binary trees. Huffman coding using Binary Tree. Concept & Basic Operations for AVL Tree, B Tree & Binary Heaps.
SHORT QUESTIONS (SQ–1 A to SQ–15 A)
B.TECH. (COMPUTER SCIENCE AND ENGINEERING)
THIRD SEMESTER (DETAILED SYLLABUS)
DATA STRUCTURE (KCS301)
Course Outcome ( CO) Bloom’s Knowledge Level (KL)
At the end of course , the student will be able to understand
CO 1 Describe how arrays, linked lists, stacks, queues, trees, and graphs are represented in memory, used by the algorithms and their common applications. K1, K2
CO 2 Discuss the computational efficiency of the sorting and searching algorithms. K2
CO 3 Implementation of Trees and Graphs and perform various operations on these data structure. K3
CO 4 Understanding the concept of recursion, application of recursion and its implementation and removal of recursion. K4
CO 5 Identify the alternative implementations of data structures with respect to its performance to solve a real world problem. K5, K6
DETAILED SYLLABUS 3-1-0
Unit Topic
I
Introduction: Basic Terminology, Elementary Data Organization, Built in Data Types in C. Algorithm, Efficiency of an Algorithm, Time and Space Complexity, Asymptotic notations: Big Oh, Big Theta and Big Omega, Time-Space trade-off. Abstract Data Types (ADT) Arrays: Definition, Single and Multidimensional Arrays, Representation of Arrays: Row Major Order, and Column Major Order, Derivation of Index Formulae for 1-D,2-D,3-D and n-D Array
Application of arrays, Sparse Matrices and their representations.
II
III
IV
Proposed Lecture
Linked lists: Array Implementation and Pointer Implementation of Singly Linked Lists, Doubly Linked List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal, Polynomial Representation and Addition Subtraction & Multiplications of Single variable & Two variables Polynomial. 08
Stacks: Abstract Data Type, Primitive Stack operations: Push & Pop, Array and Linked Implementation of Stack in C, Application of stack: Prefix and Postfix Expressions, Evaluation of postfix expression, Iteration and Recursion- Principles of recursion, Tail recursion, Removal of recursion Problem solving using iteration and recursion with examples such as binary search, Fibonacci numbers, and Hanoi towers. Tradeoffs between iteration and recursion. Queues: Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, Array and linked implementation of queues in C, Dequeue and Priority Queue.
Searching: Concept of Searching, Sequential search, Index Sequential Search, Binary Search. Concept of Hashing & Collision resolution Techniques used in Hashing. Sorting: Insertion Sort, Selection, Bubble Sort, Quick Sort, Merge Sort, Heap Sort and Radix Sort.
Graphs: Terminology used with Graph, Data Structure for Graph Representations: Adjacency Matrices, Adjacency List, Adjacency. Graph Traversal: Depth First Search and Breadth First Search, Connected Component, Spanning Trees, Minimum Cost Spanning Trees: Prims and Kruskal algorithm. Transitive Closure and Shortest Path algorithm: Warshal Algorithm and Dijikstra Algorithm.
08
08
08
Trees: Basic terminology used with Tree, Binary Trees, Binary Tree Representation: Array Representation and Pointer(Linked List) Representation, Binary Search Tree, Strictly Binary Tree ,Complete Binary Tree . A Extended Binary Trees, Tree Traversal algorithms: Inorder, Preorder and Postorder, Constructing Binary Tree from given Tree Traversal, Operation of Insertation , Deletion, Searching & Modification of data in Binary Search . Threaded Binary trees, Traversing Threaded Binary trees. Huffman coding using Binary Tree. Concept & Basic Operations for AVL Tree , B Tree & Binary Heaps
Text books:
1. Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J. Augenstein, “Data Structures Using C and C++”, PHI Learning Private Limited, Delhi India
2. Horowitz and Sahani, “Fundamentals of Data Structures”, Galgotia Publications Pvt Ltd Delhi India.
3. Lipschutz, “Data Structures” Schaum’s Outline Series, Tata McGraw-hill Education (India) Pvt. Ltd.
4. Thareja, “Data Structure Using C” Oxford Higher Education.
5. AK Sharma, “Data Structure Using C”, Pearson Education India.
6. Rajesh K. Shukla, “Data Structure Using C and C++” Wiley Dreamtech Publication.
7. Michael T. Goodrich, Roberto Tamassia, David M. Mount “Data Structures and Algorithms in C++”, Wiley India.
8. P. S. Deshpandey, “C and Data structure”, Wiley Dreamtech Publication.
9. R. Kruse etal, “Data Structures and Program Design in C”, Pearson Education.
10. Berztiss, AT: Data structures, Theory and Practice, Academic Press.
11. Jean Paul Trembley and Paul G. Sorenson, “An Introduction to Data Structures with applications”, McGraw Hill.
12. Adam Drozdek “Data Structures and Algorithm in Java”, Cengage Learning
Array and Linked List
CONTENTS
Part-1 : Introduction : ............................................... 1–3A to 1–5A Basic Terminology, Elementary Data Organization Built in Data Types in C
Part-2 : Algorithm, Efficiency of ............................ 1–5A to 1–8A an Algorithm, Time and Space Complexity
Part-3 : Asymptotic Notations :............................. 1–8A to 1–10A Big Oh, Big Theta, and Big Omega
Part-4 : Time-Space Trade-Off, .......................... 1–10A to 1–13A Abstract Data Types (ADT)
Part-5 : Array : Definition, Single and .............. 1–13A to 1–14A Multidimensional Array
Part-6 : Representation of Arrays : ................... 1–14A to 1–17A Row Major Order, and Column Major Order, Derivation of Index Formulae for 1-D, 2-D, 3-D and n-D Array
Part-7 : Application of Arrays, Sparse ............... 1–18A to 1–20A Matrices and their Representation
Part-8 : Linked List : Array.................................. 1–20A to 1–29A Implementation and Pointer Implementation of Singly Linked List
Part-9 : Doubly Linked List ................................. 1–29A to 1–37A
Part-10 : Circular Linked List 1–37A to 1–43A
Part-11 : Operation on a Linked........................... 1–43A to 1–49A List, Insertion, Deletion, Traversal Polynomial Representation and Addition, Subtraction and Multiplication of Single Variable and Two Variable Polynomial
Introduction
: Basic Terminology, Elementary Data Organization Built in Data Types in C.
Questions-Answers
Long Answer Type and Medium Answer Type Questions
Que 1.1. Define data structure. Describe about its need and types.
Why do we need a data type ?
Answer
Data structure :
AKTU 2014-15, Marks 05
1. A data structure is a way of organizing all data items that considers not only the elements stored but also their relationship to each other.
2. Data structure is the representation of the logical relationship existing between individual elements of data.
3. Data structure is define as a mathematical or logical model of particular organization of data items.
Data structure is needed because :
1. It helps to understand the relationship of one element with the other.
2. It helps in the organization of all data items within the memory. The data structures are divided into following categories :
1. Linear data structure :
a. A linear data structure is a data structure whose elements form a sequence, and every element in the structure has a unique predecessor and unique successor.
b. Examples of linear data structure are arrays, linked lists, stacks and queues.
2. Non-linear data structure :
a. A non-linear data structure it is a data structure whose elements do not form a sequence. There is no unique predecessor or unique successor.
b. Examples of non-linear data structures are trees and graphs. Need of data type : The data type is needed because it determines what type of information can be stored in the field and how the data can be formatted.
Que 1.2. Discuss some basic terminology used and elementary data organization in data structures.
Answer
Basic terminologies used in data structure :
1. Data : Data are simply values or sets of values. A data item refers to a single unit of values.
2. Entity : An entity is something that has certain attributes or properties which may be assigned values.
3. Field : A field is a single elementary unit of information representing an attribute of an entity.
4. Record : A record is the collection of field values of a given entity.
5. File : A file is the collection of records of the entities in a given entity set.
Data organization : Each record in a file may contain many field items, but the value in a certain field may uniquely determine the record in the file. Such a field K is called a primary key, and the values k1, k2,... in such a field are called keys or key values.
Que 1.3. Define data types. What are built in data types in C ?
Explain.
Answer
1. C data types are defined as the data storage format that a variable can store a data to perform a specific operation.
2. Data types are used to define a variable before to use in a program.
3. There are two types of built in data types in C :
a. Primitive data types : Primitive data types are classified as :
i. Integer type : Integers are used to store whole numbers.
Size and range of integer type on 16-bit machine :
ii. Floating point type : Floating types are used to store real numbers.
Size and range of floating point type on 16-bit machine :
iii. Character type : Character types are used to store characters value. Size and range of character type on 16-bit machine :
iv. Void type : Void type is usually used to specify the type of functions which returns nothing.
b. Non-primitive data types :
i. These are more sophisticated data types. These are derived from the primitive data types.
ii. The non-primitive data types emphasize on structuring of a group of homogeneous (same type) or heterogeneous (different type) items. For example, arrays, lists and files.
Questions-Answers
Que 1.4. Define algorithm. Explain the criteria an algorithm must satisfy. Also, give its characteristics. Answer
1. An algorithm is a step-by-step finite sequence of instructions, to solve a well-defined computational problem.
2. Every algorithm must satisfy the following criteria : i. Input : There are zero or more quantities which are externally supplied.
ii. Output : At least one quantity is produced.
iii. Definiteness : Each instruction must be clear and unambiguous.
iv. Finiteness : If we trace out the instructions of an algorithm, then for all cases the algorithm will terminate after a finite number of steps.
v. Effectiveness : Every instruction must be basic and essential.
Characteristics of an algorithm :
1. It should be free from ambiguity.
2. It should be concise.
3. It should be efficient.
Que 1.5. How the efficiency of an algorithm can be checked ?
Explain the different ways of analyzing algorithm.
Answer
The efficiency of an algorithm can be checked by :
1. Correctness of an algorithm
2. Implementation of an algorithm
3. Simplicity of an algorithm
4. Execution time and memory requirements of an algorithm
Different ways of analyzing an algorithm :
a. Worst case running time :
1. The behaviour of an algorithm with respect to the worst possible case of the input instance.
2. The worst case running time of an algorithm is an upper bound on the running time for any input.
b. Average case running time :
1. The expected behaviour when the input is randomly drawn from a given distribution.
2. The average case running time of an algorithm is an estimate of the running time for an “average” input.
c. Best case running time :
1. The behaviour of the algorithm when input is already in order. For example, in sorting, if elements are already sorted for a specific algorithm.
2. The best case running time rarely occurs in practice comparatively with the first and second case.
Que 1.6. Define complexity and its types.
Answer
1. The complexity of an algorithm M is the function f(n) which gives the running time and/or storage space requirement of the algorithm in terms of the size n of the input data.
2. The storage space required by an algorithm is simply a multiple of the data size n.
3. Following are various cases in complexity theory :
a. Worst case : The maximum value of f(n) for any possible input.
b. Average case : The expected value of f(n) for any possible input.
c. Best case : The minimum possible value of f(n) for any possible input.
Types of complexity :
1. Space complexity : The space complexity of an algorithm is the amount of memory it needs to run to completion.
2. Time complexity : The time complexity of an algorithm is the amount of time it needs to run to completion.
Que 1.7. What do you understand by complexity of an algorithm ? Compute the worst case complexity for the following C code : main()
{ int s = 0, i, j, n; for (j = 0; j < (3 * n); j++) { for (i = 0; i < n; i++) { s = s + i; } printf(“%d”, i);
Answer
2014-15, Marks 05
Complexity of an algorithm : Refer Q. 1.6, Page 1–6A, Unit-1. Worst case complexity : (n) + (3n) = (n)
Que 1.8. How do you find the complexity of an algorithm ? What is the relation between the time and space complexities of an algorithm ? Justify your answer with an example.
AKTU 2015-16, Marks 10
Answer
Complexity of an algorithm : Refer Q. 1.6, Page 1–6A, Unit-1. Relation between the time and space complexities of an algorithm : 1. The time and space complexities are not related to each other.
2. They are used to describe how much space/time our algorithm takes based on the input.
3. For example, when the algorithm has space complexity of :
a. O(1) i.e., constant then the algorithm uses a fixed (small) amount of space which does not depend on the input. For every size of the input the algorithm will take the same (constant) amount of space.
b. O(n), O(n2), O(log (n)) - these indicate that we create additional objects based on the length of our input.
4. In contrast, the time complexity describes how much time our algorithm consumes based on the length of the input.
5. For example, when the algorithm has time complexity of :
a. O(1) i.e., constant then no matter how big is the input it always takes a constant time.
b. O(n), O(n2), O(log (n)) - again it is based on the length of the input. For example :
function(list l) {
function(list l) { for (node in l) { print(“I got a list”); } print(node) ; } }
In this example, both take O(1) space as we do not create additional objects which shows that time and space complexity might be different.
Asymptotic Notations : Big Oh, Big Theta, and Big Omega.
Questions-Answers
Long Answer Type and Medium Answer Type Questions
Que 1.9. What is asymptotic notation ? Explain the big ‘Oh’ notation.
Answer
1. Asymptotic notation is a shorthand way to describe running times for an algorithm.
2. It is a line that stays within bounds.
3. These are also referred to as ‘best case’ and ‘worst case’ scenarios respectively.
Big ‘Oh’ notation :
1. Big-Oh is formal method of expressing the upper bound of an algorithm’s running time.
2. It is the measure of the longest amount of time it could possibly take for the algorithm to complete.
3. More formally, for non-negative functions, f (n) and g(n), if there exists an integer n0 and a constant c > 0 such that for all integers n > n0.
f (n) cg(n)
4. Then, f (n) is Big-Oh of g (n). This is denoted as : f (n) O(g (n)) i.e., the set of functions which, as n gets large, grow faster than a constant time f (n).
cg(n) f(n) n f(n) = O(g(n))
Fig. 1.9.1.
Que 1.10. What is complexity of an algorithm ? Explain various notations used to express the complexity of an algorithm. OR
What are the various asymptotic notations ? Explain Big O notation.
AKTU 2017-18, Marks 07
Answer
Complexity of an algorithm : Refer Q. 1.6, Page 1–6A, Unit-1. Notations used to express the complexity of an algorithm : 1. -Notation (Same order) :
a. This notation bounds a function to within constant factors.
b. We say f(n) = g(n) if there exist positive constants n0, c1 and c2 such that to the right of n0 the value of f(n) always lies between c1g(n) and c2g(n) inclusive.
cg(n) 2
f(n)
cg(n) 1 f(n) = (g(n)) n
Fig. 1.10.1. n0
2. Oh-Notation (Upper bound) : Refer Q. 1.9, Page 1–8A, Unit-1. 3. -Notation (Lower bound) :
a. This notation gives a lower bound for a function to within a constant factor.
b. We write f(n) = g(n)) if there are positive constants n0 and c such that to the right of n0, the value of f(n) always lies on or above cg(n).
cg(n)
f(n) = (g(n)) f(n)
Fig. 1.10.2.
4. Little - Oh notation (o) :
a. It is used to denote an upper bound that is asymptotically tight because upper bound provided by O-notation is not tight.
b. We write o(g(n)) = {f(n) : For any positive constant c > 0, if a constant n0 > 0 such that 0 < f(n) < cg(n) V n > n0}
5. Little omega notation () :
a. It is used to denote lower bound that is asymptotically tight.
b. We write(g(n)) = {f(n) : For any positive constant c > 0, if a constant n0 > 0 such that 0 < cg(n) < f(n)}
Time-Space Trade-off, Abstract Data Types (ADT).
Questions-Answers
Que 1.11. Explain time-space trade-off in brief with suitable example.
OR
What do you understand by time and space trade-off ? Define the various asymptotic notations. Derive the O-notation for linear search. AKTU 2018-19, Marks 07
Answer
Time-space trade-off :
1. The time-space trade-off refers to a choice between algorithmic solutions of data processing problems that allows to decrease the running time of an algorithmic solution by increasing the space to store data and vice-versa.
2. Time-space trade-off is basically a situation where either space efficiency (memory utilization) can be achieved at the cost of time or time efficiency (performance efficiency) can be achieved at the cost of memory.
For Example : Suppose, in a file, if data stored is not compressed, it takes more space but access takes less time. Now if the data stored is compressed the access takes more time because it takes time to run decompression algorithm.
Various asymptotic notation : Refer Q. 1.10, Page 1–9A, Unit-1.
Derivation :
Best case : In the best case, the desired element is present in the first position of the array, i.e., only one comparison is made. So, T(n) = O(1).
Average case : Here we assume that ITEM does appear, and that is equally likely to occur at any position in the array. Accordingly the number of comparisons can be any of the number 1, 2, 3, ......, n and each number occurs with the probability p = 1/n. Then T(n) = 1 . (1/n) + 2 . (1/n) + 3 . (1/n) ...... + n . (1/n) = (1 + 2 + 3 + ...... + n) . (1/n) = n . (n + 1)/2 . (1/n) = (n + 1)/2 = O((n + 1)/2) O(n)
Worst case : Worst case occurs when ITEM is the last element in the array or is not there at all. In this situation n comparison is made
So, T(n) = O(n + 1) O(n)
Que 1.12. What do you understand by time-space trade-off ?
Explain best, worst and average case analysis in this respect with an example. AKTU 2017-18, Marks 07
Answer
Time-space trade-off : Refer Q. 1.11, Page 1–10A, Unit-1.
Best, worst and average case analysis : Suppose we are implementing an algorithm that helps us to search for a record amongst a list of records. We can have the following three cases which relate to the relative success our algorithm can achieve with respect to time : 1. Best case :
a. The record we are trying to search is the first record of the list.
b. If f(n) is the function which gives the running time and / or storage space requirement of the algorithm in terms of the size n of the input data, this particular case of the algorithm will produce a
complexity C(n) = 1 for our algorithm f(n) as the algorithm will run only 1 time until it finds the desired record.
2. Worst case :
a. The record we are trying to search is the last record of the list.
b. If f(n) is the function which gives the running time and / or storage space requirement of the algorithm in terms of the size n of the input data, this particular case of the algorithm will produce a complexity C(n) = n for our algorithm f(n), as the algorithm will run n times until it finds the desired record.
3. Average case :
a. The record we are trying to search can be any record in the list.
b. In this case, we do not know at which position it might be.
c. Hence, we take an average of all the possible times our algorithm may run.
d. Hence assuming for n data, we have a probability of finding any one of them is 1/n.
e. Multiplying each of these with the number of times our algorithm might run for finding each of them and then taking a sum of all those multiples, we can obtain the complexity C(n) for our algorithm f(n) in case of an average case as following :
(n) = 1· 1 2 + 2· 1 2 + ... + n· 1 2
(n) = (1 + 2 + ... + n) · 1 2
Hence in this way, we can find the complexity of an algorithm for average case as C(n) = O((n + 1)/2)
Que 1.13. What do you mean by Abstract Data Type ?
Answer
1. An Abstract Data Type (ADT) is defined as a mathematical model of the data objects that make up a data type as well as the functions that operate on these objects.
2. An Abstract Data Type (ADT) is the specification of the data type which specifies the logical and mathematical model of the data type.
3. It does not specify how data will be organized in memory and what algorithm will be used for implementing the operations.
4. An implementation chooses a data structure to represent the ADT. 5. The important step is the definition of ADT that involves mainly two parts :
a. Description of the way in which components are related to each other.
b. Statements of operations that can be performed on the data type.
Array : Definition, Single and Multidimensional Array.
Questions-Answers
Long Answer Type and Medium Answer Type Questions
Que 1.14. Define array. How arrays can be declared ?
Answer
1. An array can be defined as the collection of the sequential memory locations, which can be referred to by a single name along with a number known as the index, to access a particular field or data.
2. The general form of declaration is : type variable-name [size];
a. Type specifies the type of the elements that will be contained in the array, such as int, float or char and the size indicates the maximum of elements that can be stored inside the array.
b. For example, when we want to store 10 integer values, then we can use the following declaration, int A[10].
Que 1.15. Write short note on types of an array.
Answer
There are two types of array :
1. One-dimensional array :
a. An array that can be represented by only one-one dimension such as row or column and that holds finite number of same type of data items is called one-dimensional (linear) array.
b. One dimensional array (or linear array) is a set of ‘n’ finite numbers of homogeneous data elements such as :
i. The elements of the array are referenced respectively by an index set consisting of ‘n’ consecutive number.
2.
ii. The elements of the array are stored respectively in successive memory locations.
‘ n’ number of elements is called the length or size of an array. The elements of an array ‘A’ may be denoted in C language as : A[0], A[1], A[2], ... A[n –1]
Multidimensional arrays :
a. An array can be of more than one dimension. There are no restrictions to the number of dimensions that we can have.
b. As the the dimensions increase the memory requirements increase drastically which can result in shortage of memory.
c. Hence a multidimensional array must be used with utmost care.
d. For example, the following declaration is used for 3-D array : int a [50] [50] [50];
Representation of Arrays : Row Major Order, and Column Major Order, Derivation of Index Formulae for
Questions-Answers
1. In row major order, the element of an array is stored in computer memory as row-by-row.
2. Under row major representation, the first row of the array occupies the first set of memory locations reserved for the array, the second row occupies the next set, and so forth.
3. In row major order, elements of a two-dimensional array are ordered as
Example
Let us consider the following two-dimensional array
a. Move the elements of the second row starting from the first element to the memory location adjacent to the last element of the first row.
b. When this step is applied to all the rows except for the first row, we have a single row of elements. This is the row major representation.
c. By application of above mentioned process, we get {a, b, c, d, e, f, g, h, i, j, k, l}
Que 1.17. Explain column major order with an example.
Answer
1. In column major order the elements of an array is stored as column-bycolumn, it is called column major order.
2. Under column major representation, the first column of the array occupies the first set of memory locations reserved for the array, the second column occupies the next set, and so forth.
3. In column major order, elements are ordered as :
Example : Consider the following two-dimensional array :
a. Transpose the elements of the array. Then, the representation will be same as that of the row major representation.
b. Then perform the process of row-major representation.
c. By application of above mentioned process, we get {a, e, i, b, f, j, c, g, k, d, h, l}.
Que 1.18. Write a short note on address calculation for 2D array. OR
Determine addressing formula to find the location of (i, j)th element of a m × n matrix stored in column major order. OR
Derive the index formulae for 1-D and 2-D array.
Answer
1. Let us consider a two-dimensional array A of size m × n. Like linear array system keeps track of the address of first element only, i.e., base address of the array (Base (A)).
2. Using the base address, the computer computes the address of the element in the ith row and jth column i.e., LOC (A[i][j]).
Formulae :
a. Column major order : LOC(A[i][j]) = Base (A) + w[m(j – lower bound for column index)
+ (i – lower bound for row index)]
LOC(A[i][j]) = Base (A) + w[mj + i] in C/C++
b. Row major order :
LOC(A[i][j]) = Base (A) + w[n(i – lower bound for column index) + (j – lower bound for row index)]
LOC(A[i][j]) = Base (A) + w[ni + j] in C/C++
where w denotes the number of words per memory location for the array A or the number of bytes per storage location for one element of the array.
Que 1.19. Explain the formulae for address calculation for 3-D array with example.
Answer
In three-dimensional array, address is calculated using following two methods :
Row major order :
Location (A[i, j, k]) = Base (A) + mn (k – 1) + n (i – 1) + (j – 1)
Column major order :
Location (A[i, j, k] ) = Base (A) + mn (k – 1) + m (j – 1) + (i – 1)
For example : Given an array [1..8, 1..5, 1..7] of integers. If Base (A) = 900 then address of element A[5, 3, 6], by using rows and columns methods are : The dimensions of A are : M = 8, N = 5, R = 7, i = 5, j = 3, k = 6
Row major order :
Location (A[i, j, k]) = Base (A) + mn (k – 1) + n (i – 1) + (j – 1)
Location (A[5, 3, 6]) = 900 + 8 × 5(6 – 1) + 5(5 – 1) + (3 – 1)
= 900 + 40 × 5 + 5 × 4 + 2 = 900 + 200 + 20 + 2 = 1122
Column major order :
Location (A[i, j, k]) = Base (A) + mn (k – 1) + m (j – 1) + (i – 1)
Location (A[5, 3, 6]) = 900 + 8 × 5(6 – 1) + 8(3 – 1) + (5 – 1) = 900 + 40 × 5 + 8 × 2 + 4 = 900 + 200 +16 + 4 = 1120
Que 1.20. Consider the linear arrays AAA [5 : 50], BBB [– 5 : 10] and CCC [1 : 8].
a. Find the number of elements in each array.
b. Suppose base (AAA) = 300 and w = 4 words per memory cell for AAA. Find the address of AAA [15], AAA [35] and AAA [55].
AKTU 2015-16, Marks 10
Answer
a. The number of elements is equal to the length; hence use the formula :
Length = UB – LB + 1
Length (AAA) = 50 – 5 + 1 = 46
Length (BBB) = 10 – (– 5) + 1 = 16
Length (CCC) = 8 – 1 + 1 = 8
b. Use the formula
LOC (AAA [i]) = Base (AAA) + w (i – LB)
LOC (AAA [15]) = 300 + 4 (15 – 5) = 340
LOC (AAA [35]) = 300 + 4 (35 – 5) = 420
AAA [55] is not an element of AAA, since 55 exceeds UB = 50.
Que 1.21. Suppose multidimensional arrays P and Q are declared as P(– 2: 2, 2: 22) and Q(1: 8, – 5: 5, – 10 : 5) stored in column major order i. Find the length of each dimension of P and Q. ii. The number of elements in P and Q. iii. Assuming base address (Q) = 400, W = 4, find the effective indices E1, E2, E3 and address of the element Q[3, 3, 3].
AKTU 2018-19, Marks 07
Answer
i. The length of a dimension is obtained by Length = Upper Bound – Lower Bound + 1
Hence, the lengths of the dimension of P are,
L1 = 2 – (– 2) + 1 = 5; L2 = 22 – 2 + 1 = 21
The lengths of the dimension of Q are,
L1 = 8 – 1 + 1 = 8; L2 = 5 – (– 5) + 1 = 11; L3 = 5 – (– 10) + 1 = 16
ii. Number of elements in P = 21 × 5 = 105 elements
Number of elements in Q = 8 × 11 × 16 = 1408 elements
iii. The effective index Ei is obtained from Ei = ki – LB, where ki is the given index and LB, is the Lower Bound. Hence,
E1 = 3 – 1 = 2; E2 = 3 – (– 5) = 8; E3 = 3 – (– 10) = 13
The address depends on whether the programming language stores Q in row major order or column major order. Assuming Q is stored in column major order.
E3L2 = 13 × 11 = 143
E3L2 + E2 = 143 + 8 = 151
(E3L2)L1 = 151 * 8 = 1208
(E2L2+E2)L1 + E1 = 1208 + 2 = 1210
Therefore, LOC(Q[3,3,3]) = 400 + 4(1210) = 400 + 4840 = 5240
Application of Arrays, Sparse Matrices and their Representation.
Questions-Answers
Long Answer Type and Medium Answer Type Questions
Que 1.22. Write a short note on application of arrays.
Answer
1. Arrays are used to implement mathematical vectors and matrices, as well as other kinds of rectangular tables. Many databases, small and large, consist of one-dimensional arrays whose elements are records.
2. Arrays are used to implement other data structures, such as lists, heaps, hash tables, queues and stacks.
3. Arrays are used to emulate in-program dynamic memory allocation, particularly memory pool allocation.
4. Arrays can be used to determine partial or complete control flow in programs, as a compact alternative to multiple “if” statements.
5. The array may contain subroutine pointers (or relative subroutine numbers that can be acted upon by SWITCH statements) that direct the path of the execution.
Que 1.23. What are sparse matrices ? Explain.
Answer
1. Sparse matrices are the matrices in which most of the elements of the matrix have zero value.
2. Two general types of n-square sparse matrices, which occur in various applications, as shown in Fig. 1.23.1.
3. It is sometimes customary to omit block of zeros in a matrix as in Fig. 1.23.1. The first matrix, where all entries above the main diagonal are zero or, equivalently, where non-zero entries can only occur on or below the main diagonal, is called a lower triangular matrix.
4. The second matrix, where non-zero entries can only occur on the diagonal or on elements immediately above or below the diagonal, is called tridiagonal matrix.
() Triangular matrix a () Tridiagonal matrix b Fig. 1.23.1.
Que 1.24. Write a short note on representation of sparse matrices.
Answer
There are two ways of representing sparse matrices :
1. Array representation :
i. In the array representation of a sparse matrix, only the non-zero elements are stored so that storage space can be reduced.
ii. Each non-zero element in the sparse matrix is represented as (row, column, value).
iii. For this a two-dimensional array containing three columns can be used. The first column is for storing the row numbers, the second column is for storing the column numbers and the third column represents the value corresponding to the non-zero element at (row, column) in the first two columns.
iv. For example, consider the following sparse matrix :
The above matrix can be represented as :
2. Linked representation :
i. In the linked list representation each node has four fields. These four fields are defined as :
a. Row : Index of row, where non-zero element is located.
b. Column : Index of column, where non-zero element is located.
c. Value : Value of non-zero element located at index – (row, column).
d. Next node : Address of next node.
Example :
Que 1.25. Explain the upper triangular and lower triangular sparse matrices. Suggest a space efficient representation for sparse matrices.
Answer
1. The matrix, where all entries above the main diagonal are zero or equivalently, where non-zero entries can only occur, on or below the main diagonal, is called lower triangular matrix.
2. A matrix in which all the entries below the main diagonal are zero is called upper triangular matrix. Space efficient representation for sparse matrices : Refer Q. 1.24, Page 1–19A, Unit-1. Linked List : Array Implementation and Pointer Implementation of Singly Linked List.
Questions-Answers
Long Answer Type and Medium Answer Type Questions
Que 1.26. Define the term linked list. Write a C program to implement singly linked list for the following function using array : i. Insert at beginning ii. Insert at end iii. Insert after element iv. Delete at end v. Delete at beginning vi. Delete after element vii. Display in reverse order
Answer
i. Linked list :
1. A linked list, or one-way list, is a linear collection of data elements, called nodes, where the linear order is given by means of pointers.
Information part of third node Next pointer field of third node
Fig. 1.26.1.
2. Each node is divided into two parts: the first part contains the information of the element, and the second part, called the link field or next pointer field, contains the address of the next node in the list.
Program :
#include<stdio.h> #include<conio.h> #include<alloc.h> struct node { int info; struct node *link; } ; struct node *first; void main( )
i. Insert at beginning : void insert_beginning( ) { struct node *ptr; ptr = (struct node*)malloc(sizeof(struct node)); if (ptr == NULL) { printf (“overflow\n” ) ; return; } printf (“input new node information”); scanf (“%d”, &ptr -> info) ; ptr -> link = first; first = ptr; }
ii. Insert at end : void insert_end( ) { struct node *ptr; *cpt; ptr = (struct node*)malloc(sizeof(struct node)); if (ptr == NULL) { printf (“Link list is overflow\n”); return; } printf (“input new node information”); scanf (“%d”, &ptr -> info); cpt = first; while (cpt -> link != NULL) cpt = cpt -> link;
cpt -> link = ptr; ptr -> link = NULL;
iii. Insert after element :
void insert_given_node( ) { struct node *ptr, *cpt; int data;
ptr = (struct node*)malloc(sizeof(struct node)); if (ptr == NULL) { printf (“overflow\n”); return; }
printf (“input new node information”); scanf (“%d”, &ptr -> info);
printf (“input information of node after which insertion will be made”) ; scanf (“%d”, &data) ; cpt = first; while (cpt -> info != data) cpt = cpt -> link; ptr -> link = cpt -> link; cpt -> link = ptr; }
iv. Delete at end : void delete_end( ) { struct node *ptr, *cpt; if (first == NULL) { printf (“underflow\n”); return; }
ptr = first; while (ptr -> link != NULL) { cpt = ptr; ptr = ptr -> link; } cpt -> link = NULL; free (ptr); }
v. Delete at beginning : void delete_beginning( ) { struct node *ptr; if (first == NULL) { printf (“underflow\n”) ; return; }
ptr = first; first = ptr -> link; free (ptr) ; }
vi. Delete after element : void delete_given_info( ) { struct node *ptr, *cpt; int data; if (first == NULL) { printf (“underflow\n” ) ; return; } ptr = first; printf (“input information of node to be deleted”) ; scanf (“%d”, & data); while (ptr -> info != data) { cpt = ptr; ptr = ptr -> link; } cpt -> link = ptr -> link; free (ptr); }
vii. Display in reverse order : reverse_list( ) { ptr = First; cpt = NULL; while (ptr != NULL) { cpt = ptr -> link; ptr -> link = tpt; cpt = ptr; ptr = cpt; } }
Que 1.27. Write algorithm of following operation for linear linked list :
i. Traversal ii. Insertion at beginning iii. Search an element iv. Delete node at specified location v. Deletion at end
Answer
i. Traversing a linked list : Let LIST be a linked list in memory. This algorithm traverses LIST, applying an operation PROCESS to each element of LIST. The variable PTR points to the node currently being processed.
1. Set PTR := START [Initializes pointer PTR]
2. Repeat Steps 3 and 4 while PTR != NULL
3. Apply PROCESS to PTR -> INFO
4. Set PTR := PTR -> LINK [PTR now points to the next node] [End of Step 2 loop]
5. Exit
ii. Insertion at beginning : Here START is a pointer variable which contains the address of first node. ITEM is the value to be inserted.
1. If (START == NULL) Then
2. START = New Node [Create a new node]
3. START->INFO = ITEM [Assign ITEM to INFO field]
4. START->LINK = NULL [Assign NULL to LINK field]
Else
5. Set PTR = START [Initialize PTR with START]
6. START = New Node [Create a new node]
7. START->INFO = ITEM [Assign ITEM to INFO field]
8. START->LINK = PTR [Assign PTR to LINK field] [End of If]
9. Exit
iii. Search an element : Here START is a pointer variable which contains the address of first node. ITEM is the value to be searched.
1. Set PTR = START, LOC = 1 [Initialize PTR and LOC]
2. Repeat While (PTR != NULL)
3. If (ITEM == PTR -> INFO) Then [Check if ITEM matches with INFO field]
4. Print: ITEM is present at location LOC
5. Return
6. Else
7. PTR = PTR -> LINK [Move PTR to next node]
8. LOC = LOC + 1 [Increment LOC]
9. [End of If]
10. [End of While Loop]
11. Print: ITEM is not present in the list
12. Exit
iv. Delete node at specified position : Here START is a pointer variable which contains the address of first node. PTR is a pointer variable which contains address of node to be deleted. PREV is a pointer variable which points to previous node. ITEM is the value to be deleted.
1. If (START == NULL) Then [Check whether list is empty]
2. Print: Linked-List is empty.
3. Else If (START -> INFO == ITEM) Then [Check if ITEM is in 1st node]
4. PTR = START
5. START = START -> LINK [START now points to 2nd node]
6. Delete PTR
7. Else
8. PTR = START, PREV = START
9. Repeat While (PTR != NULL)
10. If (PTR -> INFO == ITEM) Then [If ITEM matches with PTR->INFO]
11. PREV -> LINK = PTR -> LINK [Assign LINK field of PTR to PREV]
12. Delete PTR
13. Else
