Data Structures and Algorithms

• Data structure is a way of storing and organizing data in a computer so that it can be used efficiently.

Classification of Data Structures

• There are two major classifications: Linear and Non-linear.
• Linear data structures include link lists, stacks and queues.
• Non-linear data structures include trees and graphs.

Algorithms

• Algorithms are sequences of steps to solve any given problem.
• Algorithms have a definite beginning and a definite end.
• Algorithms contain a finite number of steps.

Characteristics of Data Structures

• Correctness: Data structure implementation should implement its interface correctly.
• Time Complexity: Running time of the execution of data structure operations must be as small as possible.
• Space complexity is also a factor.

Need for Data Structures

• Facilitates searching data.
• Necessary for managing processor speed.

Execution Time Cases

• Worst case
• Average case
• Best case

Arrays

• An array is a finite collection of similar elements stored in adjacent memory locations.
• Finite means that there are a specific number of elements in an array.
• Similar means that all the elements in an array are of the same type.
• Example: an array may contain all integers or all characters but not both.
• An array consisting of n number of elements is referenced using an index that varies from 0 to (n-1).
• The elements of A[n] containing n elements are denoted by A[0], A[1], ... A[n-1], where 0 is the lower bound, n-1 is the upper bound.
• The lowest index of an array is called its lower bound and highest index its upper bound.
• The number of elements in the array is called its range.
• An array is a set of pairs of an index and a value.
• An array is further categorized as a one-dimensional array and multi-dimensional array.
• A multi-dimensional array can be a 2-D array, 3-D array, 4-D array, etc.
• An array is judged as 1-D or 2-D by the syntax used to declare the array.
• A[5]: A 1-D array holding 5 elements.
• A[2][5]: A 2-D array with 2 rows and 5 columns holding 10 elements.
• A[2][5][3]: A 3-D array with two 2-D arrays each of which is having 5 rows and 3 columns, holding totally 30 elements.

Operations on Arrays

• Insertion
• Deletion
• Traversal
• Search

Insertion at End

• If UB = maximum N-1 then "overflow".
• Read data or value to be inserted.
• Set UB = UB+1.
• A[UB] = data.
• Stop or Exit.

Insertion at Beginning

• If UB = maximum N-1 then "overflow".
• Else Read data
• K = UB
• Repeat step
• While K >= LB
• A[K+1] = A[K]
• K = K-1
• A[LB] = data
• Stop

Insertion at a Specific Location

• Shift elements from 7 to 4 shifted to 5, moving UB to loc, from (UB+1) to (loc+1)
• Initialize a counter I = maximum UB
• Repeat, while (I > loc)
• A[I+1] = A[I]
• I = I-1
• UB = UB+1, A[loc] = data
• Exit

Deleting from beginning

• If UB=-1, then Underflow
• K = LB
• Repeat till step 5 while K < UB
• A[K] = A[K+1]
• K = K+1
• A[UB] = NULL
• UB = UB-1
• Exit

Deletion of a Particular Element

• If UB = -1, "Underflow"
• Read data
• K = LB
• Repeat step while A[K] != data
• K = K+1
• Repeat step while K =k+1

Representation of 2-D Arrays in Memory

• A 2-D array is a collection of elements placed in m rows and n columns.
• Syntax: the syntax used to declare a 2-D array includes two subscripts, of which one specifies the number of rows and the other specifies the number of columns of an array.
• e.g., A[3][4] is a 2-D array containing 3 rows and 4 columns.
• A[0][2] is an element placed at 0th row and 2nd column.
• A 2-D array is also called a matrix.

Row Major and Column Major Arrangement

• Rows and columns of a matrix are only a matter of imagination.
• When a matrix gets stored in memory all elements of it are stored linearly.
• Since computer's memory can only be viewed as consecutive units of memory.
• This leads to two possible arrangements: row-major arrangements and column-major arrangements.
• int A[3][4] = { {12, 1, -9, 23}, {14, 7, 11, 121}, {6, 78, 15, 34} }

Row Major Arrangement

• 12 1 -9 23, 14 7 11 121, 6 78 15 34
• UB = UB-1

Column-Major Arrangement

• 12 14 6, 1 7 78, -9 11 15, 23 121 34
• Since the array elements are stored in adjacent memory locations, we can access any element of the array once we know the base address of the array & no. of rows & columns present in the array.

Base Address Calculation

• If base address of the array is 502 & we wish to refer the element 121, then the calculation involved
• Element 121 is present at A[1][3].
• Location of 121 would be = 502 + 1*4 + 3 = 516
• In general, for an array A[m][n] the address of element A[i][j] would be
• Base address + i*n + j
• For column major arrangement: Base address + j *m + i

Address Calculation in 1-D Array

• Address of A[i] = B + W * (i - LB)
• B -> Base address of array
• W -> Storage size of one element
• I -> Subscript of element where address is to be found

Question - Address Calculation

• LB -> Lower Bound of subscript, if not specified assume 0 (zero)
• Given base address of an array B[1300 ... 1900] as 1020 & size of each element is 2 bytes, find address of B[1700].
• The given values are: B = 1020, W = 2, LB = 1300, I = 1700

2D array addressing

• Address of A[i][j] = B + W * [N*(I-LR) + (J-LC)] {Row major order}
• Address of A[i][j] = B + W * [(I-LR) + M*(J-LC)] {column major order}
• Where, B -> Base Address, I Row Subscript.
• J-> Column, W-> Storage Size of one element
• Lr -> Lower limit / start row index if not given assume zero
• Lc Lower limit / start column index if not given assume zero
• M -> No. of rows of given matrix , N -> No. of columns
• Usually no. of rows & columns of a matrix are given like A [20] [30] etc.
• but if not given as A [Lr... Ur] [Lc... Uc].
• then the no. of rows & columns are calculated using:
• No. of rows (m) = (Ur - Lr) + 1
• No. of cols (N) = (Uc - Lc) + 1

Stacks

• Linear data structures as array and a linked list allow us to insert & delete an element at any place in the list.
• However, sometimes it is required to permit the addition or deletion of elements only at one end that is either beginning or end.
• Stack and Queues are two types of data structures in which addition or deletion of an element is done at end, rather than middle.
• A stack is a data structure in which addition of a new element or deletion of an existing element always takes place at the same end.
• This end is often known as top of stack.
• A stack of plates in cafeteria on, where every new plate is added to the stack is added at top
• Every new plate taken off the stack is also from top
• When an item is added to the stack, the operation is called push and when an item is removed from the stack, the operation is called pop.
• Stack is also called as last-in-first-out (LIFO) list.
• Stack is generally implemented with two basic operations: Push and Pop.
• Stack contain an ordered collection of elements.
• An array is used to store ordered list of elements, hence it is very easy to manage a stack if we represent it using an array.
• Each of our Stacks will be maintained by a linear array
• STACK; a pointer variable TOP, which contains the location of the top element of the stack.
• A variable MAXSTK which gives the maximum number of elements that can be held by the stack.
• The condition TOP = 0 or TOP = NULL will indicate that the stack is empty.

Push Algorithm

• If TOP = MAXSTK then Print Overflow & Return (stack already filled)
• Set TOP = TOP + 1
• Set STACK[TOP] = ITEM
• Return.

Pop Algorithm

• If TOP=0 then Print UNDERFLOW & Return (Stack has an item to be removed?)
• Set ITEM = STACK[TOP]. (Assigns Top element to ITEM)
• Set TOP = TOP - 1
• Return
• 2 stack implementation in one array

Push A Algorithm

• If TOPA + 1 = TOPB OR TOPB - 1 OR TOP A = MAXSTK then Print overflow & Exit.
• TOPA = TOPA + 1
• STACK[TOPA] = Item
• Exit

Stack Applications

• Reversing a string:
• Read elements of the string and push onto the stack
• Pop elements from stack and assign to a new string, yielding a reversed string
• Factorial Calculation is a stack application
• Recursion is when function calls itself.

Polish Notation

• The process of writing the operators of an expression either before or after their operands
• The fundamental property is that the of operators and operands
• One never needs parentheses when writing an expression in polish notation. There are classified in three categories.
• Infix, operators exist between 2 operands
• Prefix , operators written before operands
• Postfix, operators come after operands

Tower of Hanoi

• Tower of Hanoi is a mathematical puzzle which consists of three towers and series of different sized rings, which must adhere to particular rules to solve the puzzle.
• Objective: The mission is to move all the disks to some tower without violating the sequence of arrangement.
• Rules: Only one disk can be moved among the towers at any given time; only the top disk can be removed; no large disk can be placed over the small disk.

Recursive Function for Tower of Hanoi

• Move top (n - 1) disks from S to A
• Move top disk from S to D
• Move top (n - 1) disks from A to D
• If N=1 then print move disk from S to D
• Else TOWER (N-1, S, D, A)
• Print move disk from S to D
• TOWER(N-1, A, S, D)