Data Structure

Unit-1

Lectuer-1

Introduction: Basic Terminology, Data types and its classification

Lectuer-2

Algorithm complexity notations like big Oh, Ω, θ

Lectuer-3

Array

Lecture-04

Address calculation, Array as Parameters

Lecture-05

Ordered List and operations

LECTURE 6

Sparse Matrices, Storage pools, Garbage collection

LECTURE 7

Recursion-definition and processes, simulating recursion

LECTURE 8

Backtracking, Recursive algorithms, Tail recursion

LECTURE 9

Removal of recursion. Tower of Hanoi Problem

REFERENCCE

UNIT – 1

Introduction: Basic Terminology, Data types and its classification

Unit-01/Lecture-01

1.1  Introduction

Data structures are the collection of items stored in the memory along with the function for their retrieval.

Data types vs. Data Structures

A data type is a well-defined collection of data with a well-defined set of operations on it.

A data structure is an actual implementation of a particular abstract data type

1.2 Abstract Data Types (ADT) [RGPV/Dec2010 (10)] [RGPV/June2012(7)] [RGPV/Dec 2014(2)]

Data storage & operations encapsulated by an ADT.

• ADT specifies permitted operations as well as time and space guarantees.

• User unconcerned with how it’s implemented (but we are concerned with implementation in this class).

• ADT is a concept or convention:

- not something that directly appears in your code

- programming language may provide support for communicating ADT to users (e.g. classes in Java & C++)

Data Organizing Principles

• Ordering:

• Put keys into some order so that we know something about where each key is are relative to the other keys.

• Phone books are easier to search because they are alphabetized.

• Linking:

• Add pointers to each record so that we can find related records quickly.

• E.g. The index in the back of book provides links from words to the pages on which they appear.

• Partitioning:

• Divide the records into 2 or more groups, each group sharing a particular property.

• E.g. Multi-volume encyclopedias (Aa-Be, W-Z)

• E.g. Folders on your hard drive

Types of Data Structures [RGPV/Dec2013 (7)] [RGPV/June2012(7)]

Linear DS: In linear data structures, values are arranged in linear fashion. Arrays, linked lists, stacks and queues are examples of linear data structures in which values are stored in a sequence.

Non-Linear DS: This type is opposite to linear. The data values in this structure are not arranged in order. Tree, graph, table and sets are examples of non-linear data structures.

Homogenous DS: In this type of data structures, values of the same types of data are stored, as in an array.

Non-homogenous DS: In this type of data structures, data values of different types are grouped, as in structures and classes.

Dynamic DS: In dynamic data structures such as references and pointers, size and memory locations can be changed during program execution.

Static DS: Static keyword in C is used to initialize the variable to 0 (NULL). The value of a static variable remains in the memory throughout the program. Value of static variable persists. In C++ member functions are also declared as static and such functions are called as static functions and can be invoked directly.

Array: an array data structure or simply an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key.

Linked List: a linked list is a data structure consisting of a group of nodes which together represent a sequence, under the simplest form, each node is composed of a datum and a reference (in other words, a link) to the next node in the sequence;

Stack: a special type of data structure in which items are removed in the reverse order from that in which they are added, so the most recently added item is the first one removed. This is also called last-in, first-out (LIFO).

Queue: a queue is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data

Fig1.1: Types of the data structures

Tree: A tree data structure can be defined recursively (locally) as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the "children"), with the constraints that no reference is duplicated, and none points to the root.

Graph: A graph data structure consists of a finite (and possibly mutable) set of ordered pairs, called edges or arcs, of certain entities called nodes or vertices.

Unit-01/Lecture-02

Algorithm complexity notations like big Oh, Ω, θ

2.1 Complexity [RGPV/June 2011 (10)] [RGPV/Dec2013 (7)]

An essential aspect to data structures is algorithms. Data structures are implemented using algorithms. An algorithm is a procedure that we can write in natural language, or in pseudo code. An algorithm states explicitly how the data will be manipulated.

The complexity of an algorithm is a function describing the efficiency of the algorithm in terms of the amount of data the algorithm must process. Usually there are natural units for the domain and range of this function. There are two main complexity measures of the efficiency of an algorithm:

• Time complexity is a function describing the amount of time an algorithm takes in terms of the amount of input to the algorithm. "Time" can mean the number of memory accesses performed, the number of comparisons between integers, the number of times some inner loop is executed, or some other natural unit related to the amount of real time the algorithm will take. We try to keep this idea of time separate from "wall clock" time, since many factors unrelated to the algorithm itself can affect the real time (like the language used, type of computing hardware, proficiency of the programmer, optimization in the compiler, etc.). It turns out that, if we chose the units wisely, all of the other stuff doesn't matter and we can get an independent measure of the efficiency of the algorithm.
• Space complexity is a function describing the amount of memory (space) an algorithm takes in terms of the amount of input to the algorithm. We often speak of "extra" memory needed, not counting the memory needed to store the input itself. Again, we use natural (but fixed-length) units to measure this. We can use bytes, but it's easier to use, say, number of integers used, number of fixed-sized structures, etc. In the end, the function we come up with will be independent of the actual number of bytes needed to represent the unit. Space complexity is sometimes ignored because the space used is minimal and/or obvious, but sometimes it becomes as important an issue as time.

Amortized analysis : Sometimes we find the statement in the manual that an operation takes amortized time O(f(n)). This means that the total time for n such operations is bounded asymptotically from above by a function g(n) and that f(n)=O(g(n)/n). So the amortized time is (a bound for) the average time of an operation in the worst case.

The special case of an amortized time of O(1) signifies that a sequence of n such operations takes only time O(n). One then refers to this as constant amortized time.

Such statements are often the result of an amortized analysis: Not each of the n operations takes equally much time; some of the operations are running time intensive and do a lot of “pre-work” (or also “post-work”), what, however, pays off by the fact that, as a result of the pre-work done, the remaining operations can be carried out so fast that a total time of O(g(n)) is not exceeded. So the investment in the pre-work or after-work amortizes itself.

2.2 Asymptotic Notations [RGPV/Dec2010 (12)] [RGPV/Dec2012 (7)]

Asymptotic complexity is a way of expressing the main component of the cost of an algorithm, using idealized units of computational work.

Big O notation: The O (pronounced as: big-oh) is the formal method of expressing the upper bound of an algorithm's running time. It's a measure of the longest amount of time it could possibly take for the algorithm to complete.

More formally, for non-negative functions, f(n) and g(n), if there exists an integer and a constant c > 0 such that for all integers , f(n) ≤ cg(n), then f(n) is Big O of g(n). This is denoted as "f(n) = O(g(n))".

Big Omega (Ω) Notations: For non-negative functions, f(n) and g(n), if there exists an integer and a constant c > 0 such that for all integers , f(n) ≥ cg(n), then f(n) is omega of g(n). This is denoted as "f(n) = Ω(g(n))".

Theta Notation: For non-negative functions, f(n) and g(n), f(n) is theta of g(n) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)). This is denoted as "f(n) = Θ(g(n))".

For non-negative functions, f(n) and g(n), if there exists an integer  and a constant c1,c2 > 0 such that for all integers , c1g(n)≥ f(n) ≥ c2g(n), then f(n) is theta of g(n).

Fig 1.2: Relations between O, Ω, Θ

For Example: For example, consider the following expression.
3n³ + 6n² + 6000 = (n³)

BACK

Unit-01/Lecture-03

Array

Array Definition, Representation and Analysis of Arrays, Single and Multidimensional Arrays

3.1 Array [RGPV/Dec2013 (7)] [RGPV/June 2011 (10)] [RGPV/Dec2012(7)] [RGPV/Jun2014(7)]

An array is a data structure that contains a group of elements. Typically these elements are all of the same data type. The entire array is stored contiguously in memory. Arrays can have more than one dimension. A one-dimensional array is called a vector; a two-dimensional array is called a matrix.

Fig-1.3

Suppose that A is a variable that refers to an array. Then the element at index k in A is referred to as A[k]. The first element is A[0], the second is A[1], and so forth. “A[k]” is really a variable, and it can be used just like any other variable. You can assign values to it, you can use it in expressions, and you can pass it as a parameter to a subroutine.

Here in above example a[5] is an array with first array index 0 and last index is 4.

3.2 Properties of arrays

    Each element is the same size. Elements are stored contiguously, with the first element stored at the smallest memory address (called the base address)

3.3 Types of Arrays

One-dimensional Array or linear array: requires only one index to access an element.

A[n1]

Two-Dimensional Array: requires two indices to access an element.

A[n1][n2]

Here, the first index is the row number; the second index the number within the row.

                                                                                      [RGPV/Dec2012(7)] [RGPV/Dec2013(2)                           

Multidimensional Array: requires two or more indices to access an element. in other words  an array with more than one index is a multidimensional array.

A[n1][n2]…..[nm];

3.4 Operations performed on the array:

1.      Traversing: Visiting each element of the array

2.      Searching: Finding an element in the array.

3.      Sorting: Arranging elements of the array in increasing/decreasing order

4.      Merging: Creating sorted array from two or more sorted arrays.

5.      Insertion : Adding an element in the array

6.      Deletion: Removing an element from the array

Traversing a linear array TRAVERSE (LA, N):

Here LA is a linear array with lower bound LB and upper bound UB. This algorithm traverses LA applying an operation PROCESS to each element of LA.

1. [Initialize counter] Set k: =LB.

2. Repeat steps 3 and 4 while k <=UB.

3. [Visit Element] Apply PROCESS to LA [k].

4. [Increase Counter] Set k: =k + 1.

[End of step 2 loop]

5. Exit.

Algorithm for Insertion: (Inserting into Linear Array) INSERT (LA, N, K, ITEM)

Here LA is a linear array with N elements and K is a positive integer such that K<=N. The algorithm inserts an element ITEM into the K^th position in LA.

1. [Initialize counter] Set J: = N.

2. Repeat Steps 3 and 4 while j >= k;

3. [Move jth element downward.] Set LA [J + 1]: =LA [J].

4. [Decrease counter] Set J: = J-1

[End of step 2 loop]

5. [Insert element] Set LA [K]:=ITEM.

6. [Reset N] Set N:=N+1

7. EXIT.

Algorithm for Deletion: (Deletion from a Linear Array) DELETE (LA, N, K, ITEM)

Here LA is a Linear Array with N elements and K is the positive integer such that K<=N. This algorithm deletes the K^th element from LA.

1. Set ITEM: = LA [k].

2. Repeat for J = K to N – 1.

[Move J + 1st element upward] Set LA [J]: = LA [J +1].

[End of loop]

3. [Reset the number N of elements in LA] Set N: = N-1

4. EXIT

3.5 2D Array Representation:

1.      Column-major

2.      Row-major

Arrays may be represented  in Row-major form or Column-major form.  In Row-major form, all the elements of the first row are printed, then the elements of the second row and so on up to the last row.  In Column-major form, all the elements of the first column are printed, then the elements of the second column and so on up to the last column.

BACK

Unit-01/Lecture-04

Address calculation, Array as Parameters

4.1 Address calculation in one-dimensional Array [RGPV/Jun 2014 (7)]

Since array elements are stored in contiguous memory locations, the computer needs to not to know the address of every element but the address of only first element. The address of first element is called base address of array. Given the address of first element, address of any other element is calculated using the formula:-

Loc (A [k]) =base (A) + w * k        in C/C++/java

Where k is the index of array whose address we want to calculate and w is the number of bytes per storage location of for one element of array.

If not given explicitly, we take index set as 1,2,3,4,……n where n the upper bound of the array.

4.2 Address calculation in two-dimensional Array [RGPV/June2010 (10)] [RGPV/Dec2010 (8)] [RGPV/Jun 2014 (7)]

The address of the element in the i^th row and j^th column is given by:

(i)         Row major order:-

Loc(A[i][j])=base(A) + w (n*i + j)                      in C/C++/java

Loc (A[i][j])=base(A) w[n(I - lbr) +(j – lbc)]      in general

Where array is m x n matrix, lbc is the lower bound of column; lbr is the lower bound of row.

Fig-1.4

(ii)      Column major order:

Loc(A[i][j])=base(A) + w (m *j + i)                     in C/C++/java

Loc(A[i][j])=base(A) w[m(j - lbc) +(i – lbr)]       in general

Where array is m x n matrix, lbc is the lower bound of column; lbr is the lower bound of row.

Example: Single Dimension Array

Given the base address of an array B[1300.....1900] as 1020 and size of each element is 2 bytes in the memory. Find the address of B[1700].

Solution:

The given values are: B = 1020, LB = 1300, W = 2, I = 1700

Address of A [ I ] = B + W * ( I – LB )

= 1020 + 2 * (1700 – 1300)

= 1020 + 2 * 400

= 1020 + 800

= 1820 [Ans]

Examples: Two Dimension array

Q 1. An array X [-15..........10, 15...............40] requires one byte of storage. If beginning location is 1500 determine the location of X [15][20].

Solution:       

As you see here the number of rows and columns are not given in the question. So they are calculated as:

Number or rows say M = (Ur – Lr) + 1 = [10 - (- 15)] +1 = 26

Number or rows say N = (Uc – Lc) + 1 = [40 - 15)] +1 = 26

(i) Column Major Wise Calculation of above equation

The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15, Lc = 15, M = 26

Address of A [ I ][ J ] = B + W * [ ( I - Lr ) + M * ( J - Lc ) ]

= 1500 + 1 * [(15 - (-15)) + 26 * (20 - 15)]

= 1500 + 1 * [30 + 26 * 5]

= 1500 + 1 * [160]

= 1660 [Ans]

(ii) Row Major Wise Calculation of above equation

The given values are: B = 1500, W = 1 byte, I = 15, J = 20, Lr = -15, Lc = 15, N = 26

Address of A [ I ][ J ] = B + W * [ N * ( I - Lr ) + ( J - Lc ) ]

= 1500 + 1* [26 * (15 - (-15))) + (20 - 15)]

= 1500 + 1 * [26 * 30 + 5]

= 1500 + 1 * [780 + 5]

= 1500 + 785

= 2285 [Ans]

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

What is a 2 dimensional array ? Describe the formula for calculating the address of any element of a  2D array.

June 2010

10

Q.2

Consider a 2D array declared in “C” A[20][30].Element type is integer.If the base address is 1076,what wil be the address of A[17][29] ? Memory is byte oriented.

Dec 2010

8

Q.3

How is physical memory allocated for a two dimension array? If each element of an array X[20][50] requires 4 bytes of storage base address of data is 2000 ,determine the location of x[0][10] when the array is stored as

1)Row major 2) Column major

June 2014

7

Unit-01/Lecture-05

Ordered List and operations

5.1 Bubble Sort

Suppose the list of numbers A [1], A [2], A [3], …, A[n] is in memory. The bubble sort algorithm works as

Step 1: Compare A [1] and A[2] and arrange them in the desired order, so that A [1] < A [2]. Then compare A [2] and A [3] and arrange them so that A [2] < A [3]. Then Compare A [3] and A [4] and arrange them so that A [3] < A [3]. Continue until we compare A [n-1] with A [n] and arrange them so that A [n-1] < A [n].

Observe that step 1 involves n-1 comparisons. When step 1 is completed, A[n] will contain the largest element.

Step 2: Repeat Step 1 with one less comparison; that is, now we stop after we compare and possibly rearrange A [n-2] and A [n-1]. When Step 2 is completed, the second largest element will occupy A [-1].

Step 3: Repeat step 1 with two fewer comparisons; that is, we stop after we compare and possibly rearrange A [n-3] and A [n-2].

……

……

……

Step n-1: Compare A [1] with A [2] and arrange them so that A [1] < A [2].

After n-1 steps, the list will be sorted in the increasing order.

Algorithm: (BUBBLE SORT) BUBBLE (DATA, N)

Here DATA is an array with N elements. This algorithm sorts the elements in DATA.

1. Repeat step 2 and 3 for K=1 to N-1

2. Set PTR :=1 [Initializes pass pointer PTR]

3. Repeat while PTR <= N-K [Executes pass]

a. If DATA [PTR]> DATA [PTR+1], then:

Interchange DATA [PTR] and DATA [PTR+1].

[End of if structure].

b. Set PTR: = PTR+1.

[End of inner loop].

4.EXIT.

Observe that there is an inner loop which is controlled by the variable PTR, and the loop is contained in an outer loop which is controlled by an index K. Also observe that PTR is used as a subscript but K is not used as a subscript, but rather as a counter.

5.2 Linear Search

Suppose data is a linear array with n elements. Given no other information about DATA, the most intuitive way to search for a given ITEM in DATA is compare ITEM with each element of DATA one by one. That is, First we check whether DATA [1] =ITEM, and then we check whether DATA [1] =ITEM, and so on. This method which traverses DATA sequentially to locate ITEM is called Linear Search or Sequential Search.

To simplify the matter, we first assign ITEM to DATA [n+1], the position following the last element of DATA. Then the outcome : LOC= N+1.

Where LOC denotes the location where ITEM first occurs in DATA, signifies the search is unsuccessful. The purpose of this initial assignment is to avoid repeatedly testing whether or not we reached the end of the array DATA.

Algorithm: (Linear Search) LINEAR (DATA, N, ITEM, LOC) [RGPV/June2010 (7)]

Here DATA is linear array with N elements, and ITEM is a given item of information. This algorithm finds the location LOC of ITEM in DATA, or sets LOC: = 0 if search is unsuccessful.

1. [Insert ITEM at the end of DATA] Set DATA [N+1]:= ITEM

2. [Initialize counter] Set LOC: =1.

3. [Search for ITEM]

Repeat while DATA [LOC]! = ITEM

Set LOC: = LOC+1.

[End of loop].

4. [Successful?] If LOC= N+1, then Set LOC: =0.

5. EXIT

Observe that Step 1 guarantees that the loop in step 3 must terminate. Without step 1 the repeat statement in step 3 must be replaced by the following statement, which involves two comparisons, not one: Repeat while LOC < =N and DATA [LOC]! = ITEM.

5.3 Binary Search [RGPV/June2011 (5)]

Suppose DATA is an array which is stored in increasing numerical order or alphabetically. Then there is an extremely efficient searching algorithm called binary search, which can be used to find the location LOC of a given ITEM of information in DATA.

The Binary Search algorithm applied to our array DATA works as follows. During each stage of our algorithm, our search of ITEM is reduced to a segment of element of DATA:

DATA [BEG], DATA [BEG+1], DATA [BEG+2], …… DATA [END]

Note that the variables BEG and END denote, respectively, the beginning and end location of the segment under consideration. The algorithm compares ITEM with the middle element DATA [MID] of the segment, where MID is obtained by

MID = INT ((BEG + END)/2)

If DATA [MID] =ITEM, then the search is successful and we set LOC:= MID. Otherwise a new segment of DATA is obtained as follows:

    If ITEM < DATA[MID], then ITEM can appear only in the left half of the segment:

DATA [BEG], DATA [BEG+1], …. DATA [MID-1]

So we reset END: = MID-1 and begin search again.

    If ITEM > DATA[MID], then ITEM can appear only in the right half of the segment:

DATA [MID+1], DATA [MID+2], … DATA[END]

So we reset BEG: = MID +1 and begin search again.

Initially we begin with the entire array DATA; i.e., we begin with BEG=1 and ENG=n or BEG=LB and END= UB.

If the ITEM is not in the DATA, then eventually we obtain

END < BEG

This condition signals that the search is unsuccessful and in such a case we assign LOC: =NULL.

Algorithm: (Binary Search) BINARY (DATA, LB, UB, ITEM, LOC)

Here DATA is stored array with lower bound LU and upper bound UB, and ITEM is given item of information. The variables BEG, END and MID denote, respectively, the beginning end and middle location of the segment of an element of DATA. This algorithm finds the location LOC of ITEM in DATA or set LOC= NULL.

1. [Initialize segment variable]

Set BEG: = LB, END: = UB and MID: = INT ((BEG+END)/2).

2. Repeat Step 3 and 4 while BEG<= END and DATA [MID]!= ITEM.

3. If ITEM < DATA[MID], then

Set END: = MID-1

ELSE:

Set BEG: = MID+1.

[End of if structure]

4. Set MID: =INT((BIG+END)/2)

[End of Step 2 loop]

5. If DATA[MID]= ITEM then

Set LOC: = MID

ELSE:

Set LOC: = NULL.

[End of if structure]

6. EXIT.

S.NO

RGPV QUESTIONS

Year

Marks

Q.1

Explain binary searching

June 2011

5

Q.2

What is linear search and binary serach.Write algorithms for both and comment on the complexity.

June  2010

7

UNIT 1/LECTURE 6

Sparse Matrices, Storage pools, Garbage collection

6.1 Sparse matrix [RGPV/June2010 (10)] [RGPV/June2011 (10)]

A matrix in which number of zero entries are much higher than the number of non zero entries is called sparse matrix. It is important to take advantage of the sparsity. Sparsity can be structured or unstructured.  A sparse matrix is a matrix that allows special techniques to take advantage of the large number of "background" (commonly zero) elements.

The number of zeros a matrix needs in order to be considered "sparse" depends on the structure of the matrix and the desired operations to perform on it.

Fig: Sparse Matrix

Storing sparse matrices is to only store the non-zero entries as opposed to storing all entries. Depending on the number and distribution of the non-zero entries, different data structures can be used and yield huge savings in memory when compared to a naïve approach. One example of such a sparse matrix format is, It stores an initial sparse N×N matrix M in row form using three arrays, A, IA, JA. NZ denotes the number of nonzero entries in matrix M. The array A then is of length NZ and holds all nonzero entries of M. The array IA stores at IA(i) the position of the first element of row i in the sparse array A. The length of row i is determined by IA(i+1) - IA(i). Therefore IA needs to be of length N + 1. In array JA, the column index of the element A(j) is stored. JA is of length NZ. Another possibility is to use quad trees.

A clear understanding might be had by considering an example of how the above applies to an example matrix. Consider the matrix

    1   2   0  0

    0   0   0  3

    0   0   0  4

The non-zero elements of this matrix are

   (1, 1)  ⇒ 1

   (1, 2)  ⇒ 2

   (2, 4)  ⇒ 3

   (3, 4)  ⇒ 4

This will be stored as three vectors cidx, ridx and data, representing the column indexing, row indexing and data respectively. The contents of these three vectors for the above matrix will be

  cidx = [0, 1, 2, 2, 4]

  ridx = [0, 0, 1, 2]

  data = [1, 2, 3, 4]

Storage Pool: A pool or storage pool is a collection of MDisks that jointly contain all of the data for a specified set of volumes.

Fig-1.5

All MDisks in a pool are split into extents of the same size. Volumes are created from the extents that are available in the pool. You can add MDisks to a storage pool at any time either to increase the number of extents that are available for new volume copies or to expand existing volume copies.

You can specify a warning capacity for a storage pool. A warning event is generated when the amount of space that is used in the storage pool exceeds the warning capacity. This is especially useful in conjunction with thin-provisioned volumes that have been configured to automatically consume space from the storage pool.

You can add only MDisks that are in unmanaged mode. When MDisks are added to a storage pool, their mode changes from unmanaged to managed.

You can delete MDisks from a group under the following conditions:

• Volumes are not using any of the extents that are on the MDisk.
• Enough free extents are available elsewhere in the group to move any extents that are in use from this MDisk.

Garbage collection [RGPV/Dec2012 (7)] [RGPV/June2011 (5)] [RGPV/Dec 2014 (7)]

6.2               

Garbage collection (GC) is a form of automatic memory management. The garbage collector, or just collector, attempts to reclaim garbage, or memory occupied by objects that are no longer in use by the program. Garbage collection was invented by John McCarthy around 1959 to solve problems in Lisp.

The basic principles of garbage collection are:

• Find data objects in a program that cannot be accessed in the future.
• Reclaim the resources used by those objects.

Advantages of Garbage collection:

Garbage collection frees the programmer from manually dealing with memory deallocation. As a result, certain categories of bugs are eliminated or substantially reduced:

1.      Dangling pointer bugs, which occur when a piece of memory is freed while there are still pointers to it, and one of those pointers is de-referenced. By then the memory may have been re-assigned to another use, with unpredictable results.

2.       Double free bugs, which occur when the program tries to free a region of memory that has already been freed, and perhaps already been allocated again.

3.       Certain kinds of memory leaks, in which a program fails to free memory occupied by objects that have become unreachable, which can lead to memory exhaustion. (Garbage collection typically does not deal with the unbounded accumulation of data that is reachable, but that will actually not be used by the program.)

4.      Efficient implementations of persistent data structures

Disadvantages of Garbage collection:

1.      Garbage collection consumes computing resources in deciding which memory to free, even though the programmer may have already known this information.

2.      The moment when the garbage is actually collected can be unpredictable, resulting in stalls scattered throughout a session. Unpredictable stalls can be unacceptable in real-time environments, in transaction processing, or in interactive programs.

3.  Non-deterministic GC is incompatible with RAII based management of non-GCed resources.

BACK

UNIT 1/LECTURE 7

Recursion-definition and processes, simulating recursion

7.1 Recursion [RGPV/Dec 2010 (12)] [RGPV/Dec 2012 (7)] [RGPV/June 2012 (7)][RGPV/June 2014][RGPV/Dec 2014]

Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller sub-problems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

All recursive algorithms must obey three important laws:

1. A recursive algorithm must have a base case.
2. A recursive algorithm must change its state and move toward the base case.
3. A recursive algorithm must call itself, recursively.

Types of recursion

Single recursion and multiple recursion: Recursion that only contains a single self-reference is known as single recursion, while recursion that contains multiple self-references is known as multiple recursion.

Indirect recursion: Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f.

Anonymous recursion: Recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions, and is known as anonymous recursion.

Example: Factorial

One of the simplest examples of a recursive definition is that for the factorial function:

factorial( n ) = if ( n = 0 ) then 1

                 else n * factorial( n-1 )

A natural way to calculate factorials is to write a recursive function which matches this definition:

function fact( int n )

            {

            if ( n == 0 ) return 1;

            else return n*fact(n-1);

            }

Illustration:

Call fact(5)

            fact(5)                              =       120

               ↓                                             ↑

          5*fact(4)                            =     5*24=120

                 ↓                                           ↑

              4*fact(3)                        =     4*6=24

                      ↓                                      ↑

                  3*fact(2)                    =     3*2=6

                         ↓                                   ↑

                       2*fact(1)              =      2*1=2

                              ↓                              ↑

                           1*fact(0)         =       1*1=1

                                  ↓                          ↑

                                  1     à       =          1

Example: Recursive Algorithm for Sequential Search

Algorithm  SeqSearch(L, i, j, x)

Input: L is an array, i and j are positive integers, i j, and x is the key to be searched for in L.

Output: If x is in L between indexes i and j, then output its index, else output 0.

Algorithm:

if i <= j , then

{

   if L(i) = x, then return i ;

   else return SeqSearch(L, i+1, j, x)

}

           else return 0.

Example : Algorithm for testing whether or not a number x is a natural number

Algorithm   Natural(a number x)

Input: A number x

Output: "Yes" if x is a natural number, else "No"

Algorithm:

if x < 0,   then return "No"

else

    if x = 0,   then return "Yes"

            else return Natural( x - 1 )

BACK

UNIT 1/LECTURE 8

Backtracking, Recursive algorithms, Tail recursion

8.1 Backtracking

Backtracking is a methodical way of trying out various sequences of decisions, until you find one that “works”. The term "backtrack" was coined by American mathematician D. H. Lehmer in the 1950s.

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

Backtracking can be applied only for problems which admit the concept of a "partial candidate solution" and a relatively quick test of whether it can possibly be completed to a valid solution.

Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles.

The backtracking algorithm enumerates a set of partial candidates that, in principle, could be completed in various ways to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.

Conceptually, the partial candidates are the nodes of a tree structure, the potential search tree. Each partial candidate is the parent of the candidates that differ from it by a single extension step; the leaves of the tree are the partial candidates that cannot be extended any further.

It is an:

·         Useful technique for optimizing search under some constraints

·         Requires less than m trials to determine the solution

·          Form a solution (partial vector) one component at a time, and check at every step if this has any chance of success.

·         If the solution at any point seems not-promising, ignore it.

·         If the partial vector(x1; x2; : : : ; xi)does not yield an optimal solution, ignore  m_i+1………m_n possible test vectors even without looking at them

All the solutions require a set of constraints divided into two categories: explicit and implicit constraints

Explicit constraints:  are rules that restrict each xi to take on values only from a given set.

·         Explicit constraints depend on the particular instance I of problem being solved.

·         All tuples that satisfy the explicit constraints define a possible solution space for I.\

·         Examples of explicit constraints

*   x_i>0, or all nonnegative real numbers

*   x_i={0,1}

*   l_i<x_i<u_i

Implicit constraints: are rules that determine which of the tuples in the solution space of I satisfy the criterion function.

·         Implicit constraints describe the way in which the xi s must relate to each other.

8.2 Tail Recursion

Tail recursion is a special case of recursion where the calling function does no more computation after making a recursive call.

Tail recursion is important because it can be implemented more efficiently than general recursion. When we make a normal recursive call, we have to push the return address onto the call stack then jump to the called function. This means that we need a call stack whose size is linear in the depth of the recursive calls. When we have tail recursion we know that as soon as we return from the recursive call we're going to immediately return as well, so we can skip the entire chain of recursive functions returning and return straight to the original caller. That means we don't need a call stack at all for all of the recursive calls, and can implement the final call as a simple jump, which saves us space. Here

int f(int x, int y) {

  if (y == 0) {

    return x;

  }

  return f(x*y, y-1);

}

is tail recursive (since the final instruction is a recursive call) whereas this function is not tail recursive:

int g(int x) {

  if (x == 1) {

    return 1;

  }

  int y = g(x-1);

  return x*y;

}

8.3 Recursive algorithms [RGPV/June 2010(6)] [RGPV/Dec 2013(7)]

A recursive algorithm is an algorithm which calls itself with "smaller (or simpler)" input values, and which obtains the result for the current input by applying simple operations to the returned value for the smaller (or simpler) input. More generally if a problem can be solved utilizing solutions to smaller versions of the same problem, and the smaller versions reduce to easily solvable cases, then one can use a recursive algorithm to solve that problem. For example, the elements of a recursively defined set, or the value of a recursively defined function can be obtained by a recursive algorithm.

If a set or a function is defined recursively, then a recursive algorithm to compute its members or values mirrors the definition. Initial steps of the recursive algorithm correspond to the basis clause of the recursive definition and they identify the basis elements. They are then followed by steps corresponding to the inductive clause, which reduce the computation for an element of one generation to that of elements of the immediately preceding generation

BACK

UNIT 1/LECTURE 9

Removal of recursion. Tower of Hanoi Problem

9.1 Removal of Recursion:

The function which call itself (In  function body  ) again and again is known as recursive function. This function will call itself as long as the condition is satisfied.

This recursion can be removed by two ways:

     1. Through Iteration.

     2. Through Stack

Iteration: When the recursive call is the last action executed in a recursive function, an interesting situation occurs. The recursive call causes an activation record to be put on the run-time stack to hold the function's parameters and local variables. When this recursive call finishes executing, the run-time stack is popped and the previous values of the variables are restored. But because the recursive call is the last statement in the function, the function terminates without using these values. Thus the pushing and popping of activation records is a superfluous activity. All we really need to do is to change the "smaller-caller" variable(s) on the recursive call's parameter list and then "jump" back to the beginning of the function

Stacking: When the recursive call is not the last action executed in a recursive function, we cannot simply substitute a loop for the recursion. For instance, in the function RevPrint we make the recursive call and then print the value in the current node. In such a case, we must replace the stacking performed by the system with stacking performed by the programmer.

9.2 Tower of Hanoi Problem [RGPV/June 2011 (10)][RGPV/June 2014]

The Tower of Hanoi (also called the Tower of Brahma or Lucas' Tower, and sometimes pluralised) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3. No disk may be placed on top of a smaller disk.

With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2ⁿ - 1, where n is the number of disks.

Fig-1.6

Iterative solution: A simple solution for the toy puzzle: Alternate moves between the smallest piece and a non-smallest piece. When moving the smallest piece, always move it to the next position in the same direction (to the right if the starting number of pieces is even, to the left if the starting number of pieces is odd). If there is no tower position in the chosen direction, move the piece to the opposite end, but then continue to move in the correct direction.

Simpler statement of iterative solution

Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:

For an even number of disks:

    make the legal move between pegs A and B

    make the legal move between pegs A and C

    make the legal move between pegs B and C

    repeat until complete

For an odd number of disks:

    make the legal move between pegs A and C

    make the legal move between pegs A and B

    make the legal move between pegs C and B

    repeat until complete

·         In each case, a total of 2ⁿ-1 moves are made.

Recursive solution:

A key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even smaller problems until a solution is reached. For example:

    label the pegs A, B, C — these labels may move at different steps

    let n be the total number of discs

    number the discs from 1 (smallest, topmost) to n (largest, bottommost)

To move n discs from peg A to peg C:

    move n−1 discs from A to B. This leaves disc n alone on peg A

    move disc n from A to C

    move n−1 discs from B to C so they sit on disc n

The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for n−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for n = 1. This step, moving a single disc from peg A to peg B, is trivial.

Algorithm:

We could formulate a recursive algorithm to solve the problem of Hanoi to move n disks from A to C using B as auxiliary.

Step1: If n=1, move the single disk from A to C and return,

Step2: If n>1, move the top n-1 disks from A to B using C as temporary.

Step3: Move the remaining disk from A to C.

Step4: Move the n-1 disk disks from B to C, using A as temporary.

.

BACK