Data Structures and Algorithms: Practical Workbook
Data Structures and Algorithms: Practical Workbook
Department: ________________________
Department of Computer & Information Systems Engineering NED University of Engineering & Technology, Karachi 75270, Pakistan
INTRODUCTION
Writing computer programs entails the study of how information is organized in a computer, how it can be manipulated, and how it can be utilized. Thus, it is exceedingly important for a student of computer engineering to understand the concepts of information organization and manipulation in order to pursue advanced courses in this discipline. This is what the field of data structures is all about.
Even with very large projects, difficulties usually arise not from the inability to find a solution but, rather, from the fact that there can be so many different methods and algorithms that might work that it can be hard to decide which is best, which may lead to programming difficulties, or which may be hopelessly inefficient. The greatest room for variability in algorithm design is generally in the way in which the data of the program are stored: how they are arranged in relation to each other.
The goal of this workbook, therefore, is to present elegant, yet fundamentally simple ideas for the organization and manipulation of data. It will supplement the concepts discussed in theory classes of the course Data Structures and Algorithms.
CONTENTS
Lab Session No. 1.
* * * * length concatenation substring index
Object
Page No. 1
2.
Implementation of the following word processing functions using the string processing functions length, index, substring and concatenation developed in lab session 1:
* insert * delete
3.
Implementation of the algorithm for matrix multiplication using two dimensional arrays. Storage of a two-dimensional sparse matrix in a uni-dimensional array. Application of the binary search on a list of elements stored in an array. Application of insertion and shell sorting algorithms on a list of elements stored in an array. Implementation of stack operations. Usage of stack for processing arithmetic expressions. Understanding principles of recursive programming. Implementation of queue operations. Design and implementation of linked list algorithms. Understanding binary trees and development of algorithms to incorporate them in various applications. Implementation of search through a linked binary search tree. Analysis of methods of graph representations and construction of graph traversal algorithms. Development of an algorithm for the game of Life.
11
4. 5. 6.
14 18 21
26 31 36 40 45 50
13. 14.
57 63
15.
69
___
Lab Session 01
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 01
OBJECT
Implementation of the following string processing functions: * length * concatenation * substring * index
THEORY
length
The number of characters in a string is called its length. The function length(s) returns the length of string s. concatenation
Concatenation combines the characters of two strings. For example, concatenation of string s1 with string s2 results in a string containing characters of s1 followed by those of s2. Note that string terminator of s1 is replaced by the first character of s2, but string terminator of s2 is retained. substring
Accessing a substring from a given string requires three pieces of information: a) the name of the string itself, b) the position of the first character of the substring in the given string and c) the length of the substring or the position of the last character of the substring. The function substring (s, ip, len) denotes the substring of a string s beginning in a position ip and having a length len. index
The function index(T, P) is used to find the position where a string pattern P first appears in a given string text T. This is called pattern matching.
ALGORITHMS
Algorithm A1: length(s) 1. 2. 3. 4. 5. Initialize len to 0. Set a variable to the beginning index of string s. Repeat the following step till the string terminator is encountered. len = len +1 Exit
___
Lab Session 01
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Algorithm A2: concatenate (s1, s2) 1. 2. 3. 4. 5. 6. 7. 8. Initialize i = strlen(s1) Initialize j = strlen(s2) Initialize count =0; / * This segment copies characters of s2 into array s1 * / Repeat steps 5 to 7 while count <= j s1[i] = s2[count] i = i+1 count = count + 1 Exit
Algorithm A3: substring (s, ip, len) 1. 2. 3. 4. 5. 6. 7. 8. Initialize i = ip and count = 0 Use an array dest to hold the required substring Repeat steps 4 ,5 and 6 while count < len dest[count] = s[i] count = count +1 i=i+1 Insert string terminator at end of dest Exit
Algorithm A4: index(T, P) 1. Initialize i = 0 and max = t p + 1 2. 3. 4. 5. 6. 7. 8. Repeat steps 3 to 6 while i < max Repeat for j = 0 to p 1 If P[j] T[i+j] then goto step 6 Return index i and exit i=i+1 Return 1 for no match Exit / * t and p are respectively lengths of strings T and P * /
EXERCISES
a) Implement the above algorithms in C.
___
Lab Session 01
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
b) Run your coding of Algorithm A1 with the following test cases and record your observations below. s = A computer is an idiot machine s = Data Structures is a prerequisite for compiler construction
c) Run your coding of Algorithm A2 with the following test cases and record your observations. s1 = But and s2 = ter s1 = Symmetric and s2 = Multiprocessing
___
Lab Session 01
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
d) Run your coding of Algorithm A3 with the following test cases and record your observations. s = Cray is a supercomputer, ip = 16 and len = 8 s = Unix is a multi-user operating system, ip = 24 and len = 6
e) Run your coding of Algorithm A4 with the following test cases and record your observations. T = Artificial Intelligence and P = tell T = clearly and P = early T = Parallel Processing and P = rock
f)
Design an algorithm that takes a string S and a number n as input. It then concatenates S repeatedly to itself until the length of the resultant string becomes greater than or equal to n.
___
Lab Session 01
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
h) Revise Algorithm A3 to include an error check for the situation when ip and len are out of range of s. Implement the revised algorithm in C and run your coding with a test case of your own choice.
___
Lab Session 01
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
i)
Design an algorithm that takes a string S and a char a as input. It then displays the indices of all occurrences of a in S.
___
Lab Session 02
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 02
OBJECT
Implementation of the following word processing functions using the string processing functions developed in lab session1: * insert * delete
THEORY
Insertion
Suppose in a given text T we want to insert a string P so that P begins in position ip in text T. This operation is denoted as ins(T, ip, P)
For example, if T = I am a student of Second Year Engineering, ip = 30, and P = Computer then ins(T, ip, P) = I am a student of Second Year Computer Engineering.
Deletion
Suppose we want to delete the substring that begins in position ip in a given text T and has length L. This operation is denoted as del(T, ip, L) For example, if T = VLSI stands for Very Largesse Scale Integration, ip = 26, and L = 3, then del(T, ip, L) = VLSI stands for Very Large Scale Integration.
ALGORITHMS
Algorithm A1: ins(T, ip, P) This algorithm uses temporary strings temp1 and temp2. 1. 2. 3. 4. 5. 6. temp1 = substring (T, 0, ip) temp2 = substring (T, ip, length(T) ip + 1) concatenate (temp1, P) concatenate (temp1, temp2) T = temp1 Exit
Algorithm A2: del(T, ip, L) This algorithm uses temporary strings temp1 and temp2 1. 2. 3. 4. temp1 = substring (T, 0, ip) temp2 = substring (T, ip + L, length(T) ip L + 1) T = concatenate (temp1, temp2) Exit
___
Lab Session 02
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
EXERCISES
a) Implement algorithms A1 and A2 in C.
b) Run your coding of Algorithm A1 with the following test case and record your observations. T = The founder of our country was Quaid-e-Azam, ip = 12 and P = and first Governor General.
c) Run your coding of Algorithm A2 with the following test case and record your observations. T = Database Management Systems, ip = 9 and L = 10.
___
Lab Session 02
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
d) Revise Algorithm A2 so that it deletes every occurrence of a pattern P in a given text T. Implement the revision in C and run your coding on test case of your own choice.
___
Lab Session 02
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
e) Design an algorithm that takes a string T and patterns P and Q as input. It finds P in T and inserts Q after every occurrence of P in T.
10
___
Lab Session 03
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 03
OBJECT
Implementation of the algorithm for matrix multiplication using two dimensional arrays.
THEORY
We consider two input matrices A and B of order nxn. We need to computer C=AxB, where C is of order nxn. If A is of order rAxcA, and B is of order rBxcB, then multiplication is possible only if cA=rB. C=AxB is of order rBxcA.
ALGORITHM
Algorithm: MATMUL(A,B) Here A and B both are of order nxn. 1. For i = 0 to n-1 2. For j = 0 to n-1 3. C[i][j] = 0 4. For k = 0 to n-1 5. C[i][j] = C[i][j] +A[i][k]*B[k][j] 6. End for 7. End for 8. End for 9. Return
EXERCISES
a) Implement the above algorithm in C.
11
___
Lab Session 03
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
b) Considering A is of order rAxcA, and B is of order rBxcB, revise the above algorithm and implement it in C. cA=rB, but rA, rB and cB can be different quantities.
12
___
Lab Session 03
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
j) Analyze the algorithm MATMUL() and express your result in Big O notation.
13
___
Lab Session 04
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 04
OBJECT Storage of a two-dimensional sparse matrix in a uni-dimensional array. THEORY Matrices with a high proportion of zero values are called sparse matrices. Two general forms are given below. Zero entries are left empty.
Triangular Matrix
In triangular matrix, all entries on and below the main diagonal are non-zero. In tridiagonal matrix, all entries on the main diagonal and entries immediately above and immediately below the main diagonal are non-zero. To conserve space, we store a sparse matrix in a uni-dimensional array, omitting zero entries. Consider the triangular matrix A. It has 1 non-zero entry in row 0, 2 non-zero entries in row 1, 3 non-zero entries in row 2, and n non-zero entries in row n-1. Total non-zero entries will determine the size of the uni-dimensional array U. Size of U = 1 + 2 + 3 + + n = * n * (n+1) U[0] = A[0][0], U[1] = A[1][0], U[2] = A[1][1], U[3] = A[2][0] and so on. To retrieve A[J][K], we assume, U[L] = A[J][K]. L represents the number of elements in U up to and including A[J][K]. In the rows before row J, there are 1 + 2 + 3 + + J = * J * (J+1) non-zero numbers. In row J, there are K+1 elements upto and including A[J][K]. Since the array U has starting index 0, we need to subtract 1 from L. L = * J * (J+1) + K + 1 1 = * J * (J+1) + K So, U[ * J * (J+1) + K] = A[J][K]
ALGORITHMS
A is a triangular sparse matrix of order nxn. U is a uni-dimensional array of size *n*(n+1). Algorithm A1: STORETRIANGULAR(A) 1. i=0 2. For j = 0 to n-1 3. For k = 0 to j 4. U[i] = A[j][k]
14
___
Lab Session 04
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
5. i++ 6. End for 7. End for Algorithm A2: RETRIEVETRIANGULAR(U) 1. For j = 0 to n-1 2. For k = 0 to n-1 3. If k > j, A[j][k] = 0 4. Else A[j][k] = U[*j*(j+1)+k] 5. End for 6. End for
EXERCISES
a) Implement the algorithms A1 and A2 in C.
15
___
Lab Session 04
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
b) Analyze the given algorithms and express your result in Big O notation.
c) Find the size of U for a tridiagonal matrix B. Find the formula for L if U[L] = B[J][K].
16
___
Lab Session 04
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
e)
17
___
Lab Session 05
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 05
OBJECT Application of the binary search on a list of elements stored in an array. THEORY Suppose DATA is an array that is sorted in increasing (or decreasing) numerical order or, equivalently, 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 for ITEM is reduced to a segment of elements 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 locations of the segment under consideration. The algorithm compares ITEM with the middle element DATA[MID] of the segment, where MID is computed as MID = INT((BEG + END) / 2) (INT(A) refers to the integer value of A.) If DATA[MID] = = ITEM, then the search is successful and we set LOC = MID. Otherwise a new segment of DATA is obtained as follows: a) 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 searching again. b) 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 searching again. Initially, we begin with the entire array DATA; i.e., we begin with BEG = 0 and END = N-1. If ITEM is not in DATA, then eventually we obtain BEG > END. This condition signals that the search is unsuccessful, and in such a case we assign LOC = NULL. Here NULL is a value that lies outside the set of indices of DATA.
ALGORITHM
Algorithm: BINSEARCH(DATA, ITEM) 1. Set BEG = 0, END = N-1 and MID = INT((BEG + END) / 2) 2. Repeat steps 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 4. MID = INT((BEG + END) / 2)
18
___
Lab Session 05
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
5. If DATA[MID] = ITEM, then Set LOC = MID Else Set LOC = NULL 6. Exit
EXERCISES
a)
Write a C program that makes use of the above implementation as a function. Your program should input the array from the user.
b) Analyze the binary search algorithm for the best, average and worst cases. Express your results in Big O notation.
19
___
Lab Session 05
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
c) Input an array from the user. Prompt the user if he enters unsorted data. Modify the binary search algorithm presented here so as to insert the element in the array if the search remains unsuccessful. Make sure that the array remains sorted after the insertion. Implement the revised algorithm in C.
20
___
Lab Session 06
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 06
OBJECT
Application of insertion and shell sorting algorithms on a list of elements stored in an array.
THEORY
INSERTION SORT
Suppose an array A with n elements A[1], A[2], ., A[N] is in memory. The insertion sort algorithm scans A from A [1] to A [N], inserting each element A[K] into its proper position in the previously sorted sub array A[1], A[2], , A[K-1]. That is: Pass 1. A[1] by itself is trivially sorted. Pass 2. A[2] is inserted either before or after A[1] so that: A[1], A[2] is sorted. Pass 3. A[3] is inserted into its proper place in A[1], A[2], that is, before A[1], between A[1] and A[2], or after A[2], so that: A[1], A[2],A[3] is sorted. Pass 4. A[4] is inserted into its proper place in A[1], A[2], A[3] so that: A[1], A[2], A[3], A[4] is sorted. ... Pass N. A[N] is inserted into its proper place in A[1],A[2],,A[N-1] so that: A[1], A[2],,A[N] is sorted. This sorting algorithm is frequently used where n is small. There remains only the problem of deciding how to insert A[K] in its proper place in the sorted sub array A[1], A[2],A[K-1]. This can be accomplished by comparing A[K] with A[K-1], comparing A[K] with A[K-2], comparing A[K] with A[K-3], and so on, until first meeting an element A[J] such that A[J] <= A[K]. Then each of the elements A[K-1], A[K-2],. .,A[J+1] is moved forward one location, and A[K] is then inserted in the (J+1)th position in the array. The algorithm is simplified if there always is an element A[J] such that A[J]<=A[K] ; otherwise we must constantly check to see if we are comparing A[K] with A[1]. This condition can be accomplished by introducing a sentinel element A[0] = - (or a very small number).
SHELL SORT
Shell sort is a generalization of insertion sort, which exploits the fact that insertion sort works efficiently on input that is already almost sorted. It improves on insertion sort by allowing the comparison and exchange of elements that are far apart. The last step of shell sort is a plain insertion sort, but by then, the array of data is guaranteed to be almost sorted. The algorithm for shell sort can be defined in two steps: Step 1: divide the original list into smaller lists. Step 2: sort individual sub lists using insertion sort. For dividing the original list into smaller lists, we choose a value k, which is known as increment. Based on the value of k, we split the list into k sub lists. For example, if our
21
___
Lab Session 06
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
original list is x[0], x[1], x[2], x[3], x[4],.,x[99] and we choose 5 as the value for increment, k then we get the following sub lists : First _list = x[0], x[5], x[10], x[15]x[95] Second _list = x[1], x[6], x[11], x[16]x[96] Third _list = x[2], x[7], x[12], x[17]x[97] Fourth _list = x[3], x[8], x[13], x[18]x[98] Fifth _list = x[4], x[9], x[14], x[19]x[99] th So the i sub list will contain every kth element of the original list starting from index i1. For each iteration, the list is divided and then sorted. If we use the same value of k, we will get the same sub lists and every time we will sort the same sub lists, which will not result in the ordered final list. Note that sorting the five sub lists in the above example do not ensure that the full list is sorted. So we need to change the value of k for every iteration. Since number of sub lists we get are equal to the value of k, so if we decide to reduce the value of k after every iteration, we will reduce the number of sub lists also in every iteration. Eventually, when k will be set to 1, we will have only one sub lists. Hence we know the termination condition of our algorithm is k = 1. It has been empirically found that larger number of increments gives more efficient results. Also, it is advisable not to use sequences like 1,2,4,8. or 1,3,6,9. since they may give almost the same elements in the sub lists to compare and sort which will not result in better performance.
ALGORITHMS
Algorithm A1: INSERTION(A, N) This algorithm sorts the array A with N elements using insertion sort. 1. Set A[0] : = - [Initializes sentinel element] 2. Repeat steps 3 to 5 for k = 2,3,N: 3. Set TEMP : = A[K] and PTR : = K-1 4. Repeat while TEMP < A[PTR] : (a) Set A [PTR + 1]: = A [PTR]. [Moves element forward.] (b) Set PTR : = PTR 1 [End of loop] 5. Set A[PTR + 1] : = TEMP [Insert element in proper place] [End of Step 2 loop] 6. Return Algorithm A2: SHELL(Num, N, key) This algorithm sorts the array Num with N elements using Shell sort. 1. Set k: = int (N/2) 2. While k > 0 do: a. For i from k to N-1, Repeat steps b, c, and e b. Set Key : = Num[i] and j : = i c. While j = k and Num[j k] > key, Repeat step d d. Swap Num[j] and Num[j k] e. Set k : = int ( k/2.2) 3. Use Insertion sort to sort remaining array of data.
22
___
Lab Session 06
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
EXERCISES
a) Implement algorithms A1 and A2 in C.
23
___
Lab Session 06
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
b) Analyze algorithm A1 for the worst case. Express your results in Big O notation.
c) Analyze algorithm A2 for the worst case. Express your results in Big O notation.
24
___
Lab Session 06
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
25
___
Lab Session 07
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 07
OBJECT Implementation of stack operations. THEORY A stack is a list of elements in which an element may be inserted or deleted only at one end, called the top of stack, denoted TOS. This means, in particular, that elements are removed from a stack in the reverse order of that in which they were inserted into the stack. For this reason stack is regarded as Last-In, First-Out (LIFO) structure. Special terminology is used for two basic operations associated with stacks: a. Push is the term used to insert an element into a stack. b. Pop is the term used to delete an element into a stack. Suppose we push five elements a, b, c, d, e, f, in order, onto an empty stack. Thus the stack will be represented as follows: STACK: a, b, c, d, e, f
The TOS will point to the f indicating that it is the most recently inserted item onto stack. Since the stack cant be accessed anywhere except the TOS, therefore e cant be removed before f. The key point in using stacks is that they are useful in the situations wherever decisions are postponed. For example, Keeping track of return addresses in case of procedure calls and returns. This feature is of course very valuable for interrupt processing. Implementing Recursion (to be discussed in a subsequent lab) Processing arithmetic expressions (to be discussed in a subsequent lab)
ALGORITHMS Before developing algorithms for stack operations, we must decide on stack implementation i.e., we should first answer the question how to represent a stack in the computers memory. Let the stack be represented by a linear array STACK. An integer variable TOS is used to hold the array-index of the element last inserted onto the stack, i.e., it is the top of stack. An empty stack is represented by TOS = -1. Another variable MAXSTK is maintained to indicate the maximum number of elements that can be held by the stack. Thus array implementation of stack requires an array to hold stack elements, an integer variable to point to top of stack and another integer variable to indicate the stack capacity.
26
___
Lab Session 07
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Algorithm A1: PUSH (STACK, TOS, MAXSTK, ITEM) This algorithm pushes an ITEM onto a stack. 1. /* Check for OVERFLOW. An overflow is said to occur when an attempt is made to insert onto a stack when it already contains maximum number of elements */ if (TOS = = MAXSTK 1) then PRINT OVERFLOW and return. 2. Set TOS = TOS + 1. 3. Set STACK[TOS] = ITEM. 4. Return.
Algorithm A2: POP (STACK, TOS, ITEM) This algorithm deletes the top element of STACK and assigns it to the variable ITEM 1. /* Check for UNDERFLOW. An underflow is said to occur when an attempt is made to delete from an empty stack */ if (TOS = = -1) then PRINT UNDERFLOW and return. 2. Set ITEM = STACK[TOS]. 3. Set TOS = TOS 1. 4. Return. EXERCISES a) For the array implementation of a stack, write down the necessary declaration in C.
27
___
Lab Session 07
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
In the exercises (b) to (e), show the result of operation on the stack. If overflow or underflow occurs, check the appropriate box; otherwise, show the new contents of the array, the TOS, and ITEM. (Note: Some values in the array may not be elements in the stack.)
STACK
1 2 3 4
TOS = ITEM =
STACK M A N G O
0 1 2 3 4 0 TOS = 4 ITEM = X Overflow? Underflow?
STACK
1 2 3 4
TOS = ITEM =
STACK
1 2 3 4
TOS = ITEM =
STACK H
4 0 1 2 3 4 TOS = ITEM =
___
Lab Session 07
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
f)
Show what is printed by the following segment of code. ClearStack (STACK); /* Initializes STACK as empty */ X = 4; Z = 0; Y = X + 1; PUSH (STACK, Y); PUSH (STACK, Y + 1); PUSH (STACK, X); POP (STACK, Y); X = Y + 1; PUSH (STACK, X); PUSH (STACK, Z); /* empty ( ) is a function to test for empty stack */ while (!empty (stack)) { POP (STACK, Z); Print (Z); } Print (X = , X); Print (Y = , Y); Print (Z = , Z);
g) Implement the PUSH and POP operations in C. Also write a C program to demonstrate the use of these procedures.
29
___
Lab Session 07
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
30
___
Lab Session 08
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 08
OBJECT
Usage of stack for processing arithmetic expressions
THEORY
The way we are used to seeing arithmetic expressions is called infix notation the operator is in between the operands. Infix notation can be fully parenthesized, or it can rely on a scheme of operator precedence, as well as the use of parentheses to override the rules, to express the order of evaluation within an expression. For instance, the operators x and / usually have a higher precedence over the operators + and . For example, a + b * c is sufficient to express that multiplication should be performed first. However, if we want to do the addition before multiplication, we must indicate this with the parentheses: (a + b) * c. The problem with the infix notation is its ambiguity. We must resort to an agreed-upon scheme to determine how to evaluate the expression. There are other ways of writing expressions, however, that do not require parentheses or precedence schemes. Such two schemes are postfix and prefix notations. POSTFIX NOTATION
It refers to the notation in which the operator symbol is placed post (i.e., after) its operands. For example: Infix Postfix A+B AB+ A-B ABA*B AB* A /B AB/ We translate, step by step, the following infix expressions into postfix notation using brackets [ ] to indicate a partial translation: (a + b ) * c = [ab+] * c = ab+c* a + (b * c) = a + [bc*] = abc*+ The fundamental property of postfix notation is that the order in which the operations are to be performed is completely determined by the positions of the operators and operands in the expression. Accordingly, one never needs parentheses when writing expressions in postfix notation. PREFIX NOTATION
It refers to the analogous notation in which the operator symbol appears pre (i.e., before) its operands.
31
___
Lab Session 08
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
In the honor of its designer, a Polish mathematician Jan Lukasiewicz, it is referred to as Polish notation. It has the same property associated with it as described for postfix notation. (For obvious reason, postfix notation is also termed as reverse polish notation).
ALGORITHMS
Algorithm A1: Evaluation of a Postfix Expression Suppose P is an arithmetic expression written in postfix notation. The following algorithm that uses a stack to hold operands, evaluates the VALUE of P. 1. Add a right parenthesis ) at the end of P. /* This acts as a sentinel */ 2. Scan P from left to right and repeat steps 3 and 4 for each element of P until the sentinel ) is encountered. 3. If an operand is encountered, push it onto stack. 4. If an operator op is encountered then: a) remove the two top elements of STACK. (Let T be the top element and NT be the next-to-top element.) b) evaluate NT op T c) place the result of (b) back on STACK. 5. Set VALUE equal to the top element of stack. 6. Exit Algorithm A2: Transforming Infix Expressions into Postfix Expressions Suppose Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix expression P. 1. Push ( onto STACK, and add ) at the end of Q. 2. Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the STACK is empty: 3. If an operand is encountered, add it to P. 4. If a left parenthesis is encountered, push it onto STACK. 5. If an operator op is encountered, then: a) Repeatedly pop from STACK and add to P each operator (on the top of STACK) which has the same precedence as or higher precedence than op. b) Add op to STACK. 6. If a right parenthesis is encountered, then: a) Repeatedly pop from STACK and add to P each operator (on the top of STACK) until a left parenthesis is encountered. b) Remove the left parenthesis. [Do not add the left parenthesis to P] 7. Exit
32
___
Lab Session 08
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
EXERCISES
(a) Evaluate the following postfix expressions using the algorithm described. (i) 1 4 18 6 / Symbol Scanned 1 4 18 6 / 3 + + 5 / + (ii) 3 1 + 2 ^ Symbol Scanned 3 1 + 2 ^ 7 4 2 * + 5 3 + + 5 / + STACK
+ 5
STACK
(b) Translate the following infix expression into its equivalent postfix expression using the algorithm described. ((a + b) / c ) ^ ((d e) * f) Symbol Scanned Stack ( ( a + b ) / c
33
Postfix P
___
Lab Session 08
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
34
___
Lab Session 08
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
35
___
Lab Session 09
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 09
OBJECT
Understanding principles of recursive programming.
THEORY
Recursion is an important concept in computer science. Many algorithms can be best described in terms of recursion. Recursion is the name for the case when a procedure P invokes itself or invokes a series of other procedures that eventually invokes the procedure P again. Then P is called a recursive procedure. In order to make sure that program will not continue to run indefinitely, a recursive procedure must have the following two properties: 1. There must be certain criteria, called base criteria, for which the procedure does not call itself. 2. Each time the procedure does call itself (directly or indirectly), it must be closer to the baser criteria. A recursive procedure with these two properties is said to be well-defined. FACTORIAL FUNCTION
The product of the positive integers from 1 to n, inclusive, is called n factorial and is usually denoted by n! n! = 1 x 2 x 3 x . . . (n 2) x (n 1) x n We know that 0! = 1. For every positive integer n; n! = n x (n 1)! Accordingly, the factorial function may also be defined as follows: a) If n = 0, then n! = 1. b) If n > 0, then n! = n x (n 1)! Obviously this definition is recursive, since it refers to itself when it uses (n 1)!. However, (a) the value of n! is explicitly given when n = 0 (thus 0 is the base value); and (b) the value of n! for arbitrary n is defined in terms of a smaller value of n which is closer to the base value 0. Accordingly, the definition is not circular, or in other words, the procedure is welldefined. Suppose P is a recursive procedure. During the running of an algorithm or a program that contains P, we associate a level number with each given execution of procedure P as follows. The original execution of procedure P is assigned level 1; and each time procedure P is executed because of a recursive call, its level is 1 more than the level of the execution that has made the recursive call. The depth of recursion of a recursive procedure P with a given set of arguments refers to the maximum level number of P during its execution.
ALGORITHM
This algorithm calculates n! and returns the value in the variable FACT.
36
___
Lab Session 09
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Algorithm: FACTORIAL(FACT, n) 1. if (n = = 0) then set FACT = 1 and return. 2. FACT = n x FACTORIAL(FACT, n 1 ) 3. Return.
EXERCISES
a) This exercise will demonstrate how recursion can simplify solution of some complicated problems. It addresses the problem of making combinations of a certain size out of a total group of elements. For example, if we have twenty different books to pass out to four students, we can easily see that - to be equitable - we should give each student five books. But how many combinations of five books can be made out of a group of twenty books?There is a mathematical formula to solve this problem. Given that C is the total number of combinations, Group is the total size of the group to pick from, Members is the size of each subgroup, and Group > = Members,
C(Group,Members)=
{ ( ) ( )
37
___
Lab Session 09
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
c) Implement in C, the recursive solution for factorial. Demonstrate its use in a program.
e) Design an algorithm for the problem Towers of Hanoi and implement the recursive solution in C.
38
___
Lab Session 09
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
39
___
Lab Session 10
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 10
OBJECT
Implementation of queue operations.
THEORY
A queue is a linear list of elements in which deletions can take place only at one end, called the front, and insertions can take place only at the other end, called the rear. Queues are also called first-in first-out (FIFO) lists, since the first element in a queue will be the first element out of the queue. In other words, the order in which elements enter a queue is the order in which they leave. This contrasts with stacks, which are last-in first-out (LIFO) lists. An important example of a queue in computer science occurs in a timesharing system, in which programs with the same priority form a queue while waiting to be executed. In general, queues are used in situations where a fairness criterion is to be adopted by rendering services on the basis of order of request. Array implementation of queues requires a linear array elements for containing queue elements, and two integer variables: front, to hold the array index of the front element of queue; and rear, to hold the array index of the rear element of queue. Adding an element to a queue is called ENQUEUE operation and removing an element from a queue is called DEQUEUE operation.
ALGORITHMS
Algorithm A1: ADDONE (i) This algorithm increments a number i using modulo arithmetic, so the number returned is always greater than -1 and less than the total size of the array used to hold the queue. 1. i=i mod maxlength 2. Return i Algorithm A2: MAKENULL (Q) This algorithm initializes the queue structure, so that it holds nothing. This structure has two integer memebers, front and rear, and an array member, elements. 1. Q.front = 0 2. Q.rear = maxlength-1 Algorithm A3: EMPTY (Q) This returns TRUE iff Q does not contain any element.
40
___
Lab Session 10
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
1. If ADDONE (Q.rear) = Q.front return TRUE 2. Return FALSE Algorithm A4: FRONT (Q) This algorithm is a function that returns the first element on queue Q. 1. If EMPTY (Q) then write queue is empty 2. Else return Q.elements[Q.front] Algorithm A5: ENQUEUE (x, Q) This algorithm inserts element x at the end of queue Q. 1. If ADDONE(ADDONE(Q.rear)) = Q.front then write queue is full 2. Else: a. Q.rear = ADDONE (Q.rear) b. Q.elements [Q.rear] = x Algorithm A6: DEQUEUE (var Q: QUEUE); This algorithm deletes the first element of queue Q. 1. If EMPTY (Q) then write queue is empty 2. Else Q.front = ADDONE (Q.front)
EXERCISES
a) For the array implementation of a queue, write down the necessary declaration in C.
b) Briefly elaborate the purpose of algorithm ADDONE. (Hint: Consider the case i = maxlength).
41
___
Lab Session 10
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
c) In the light of your answer to exercise (b), is it just to call Q.elements a circular array? Explain.
42
___
Lab Session 10
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
43
___
Lab Session 10
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
44
___
Lab Session 11
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 11
OBJECT
Design and implementation of linked list algorithms.
THEORY
A linked list consists of a set of nodes, each of which has two fields: an information field and a pointer to the next node in the list. S
Info next Info next Info next Info X
The diagram depicts the logical picture of a linked list. S is a pointer to the first node in the list and S = NULL obviously denotes an empty list. X denotes NULL indicating end of list. The successive elements in the list need not occupy contiguous locations in memory. This contrasts with arrays where elements must be sequentially placed in memory. Linked lists have a close relation with dynamic memory allocation that emphasizes the allocation of memory space at run time as the need arises. This is again in contrary to static memory allocation in which memory space is reserved at compile time as is done with array declaration. For the same reason, arrays are called static data structures as the size of array cant be changed during program execution. This leads to inefficient use of memory space. Linked lists obviously use memory more economically. Linked lists are regarded as dynamic data structures. In addition, the dynamic nature of memory allocation results in efficient insertions and deletions of elements in linked lists as opposed to arrays. Linked lists are of key importance in computer science. They prove to be very useful in implementing other important data structures. Several skills are vital in relation to them: (1) knowing how to declare pointer data types for list nodes; (2) knowing how to create and delete list nodes, and how to link them together; and (3) knowing how to perform various important list operations such as insertion and deletion of nodes, searching for items, printing lists, and joining lists together.
ALGORITHMS
Declarations We shall use a structure variable for representing node of a linked list. The variable comprises two fields: an integer variable info (this may be of any other type as desired) and a pointer variable next for holding the address of next node in the list. Algotithm A1: Inserting a new second node 1. Declare a pointer variable, N that points to node of type in conformance with the type of nodes in linked list.
45
___
Lab Session 11
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
2. Allocate a new node and let the pointer variable N point to it. N
? ?
info
next
3. Load the desired integer value val in the info field of newly allocated node. 4. Change the link field of the Ns referent to point to the second of node the linked list.
val
info
next
val1
val2
5. Change the link field of the first node of the linked list to point to the Ns referent. (Now pointer variable N remains of no significance)
val
info next
val1
val2
Algotithm A2: Searching for an item 1. Declare a pointer variable, N that points to node of type in conformance with the type of nodes in linked list. 2. Initially set N to point to the first node in the list. 3. While (N points to a non-null node of the list) If value in the info field of Ns referent equals the item to be searched, return the pointer node in N Else advance the pointer N to point to the next node in the list 4. Return Ns value, NULL, as the result of list search. Algotithm A3: Deleting the last node 1. Let Pnode (P for previous) and Cnode (C for current) contain pointers to list nodes. 2. If the list is not empty{ If the list has exactly one node
46
___
Lab Session 11
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
free the nodes storage, load NULL in the pointer to first node and return. Else { Initialize Pnode, Cnode to point to the first and second nodes. //Advance the Pnode, Cnode until Cnode points to the last node. While Cnode doesnt point to the last node, Advance Pnode, Cnode to the next pair of nodes. } //Now Pnode points to the next-to-last node and Cnode points to the last node on the list. Change the next-to-last node into the last node and free the space for the discarded last node. }
EXERCISES
a) Implement the declaration (as described under the head of algorithm) in C.
b) Implement all the algorithms as separate procedures and demonstrate their use in a program.
47
___
Lab Session 11
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
48
___
Lab Session 11
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
c) A doubly linked list is one in which there are two pointers in a node, one pointing to the next node and the other pointing to the previous node. Design all above algorithms for a doubly linked list and use them in a program.
49
___
Lab Session 12
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 12
OBJECT
Understanding binary trees and development of algorithms to incorporate them in various applications.
THEORY
Trees are one of the most important data structures in computer science. They come in many forms. They provide natural representations for many kinds of data that occur in applications, and they are useful for solving a wide variety of algorithmic problems. A tree is a collection of elements called nodes, one of which is distinguished as a root, with a relation (parenthood) that places a hierarchical structure on the nodes. A node, like an element of a list, can be of whatever type we wish. A structure with a unique starting node (the root), in which each node is capable of having at most two child nodes, and in which a unique path exists from the root to every other node is called a binary tree. A B
root
A binary tree has a natural implementation in linked storage. In the implementation to follow, the pointer variable root points to the root of the tree. With this pointer variable, it is easy to recognize an empty binary tree as precisely the condition root = NULL, and to create a new, empty binary tree we need only assign its root pointer to NULL. One of the most important operations on a binary tree is traversal, moving through all the nodes of the binary tree, visiting each one in turn. As for traversal of other data structures, the action we shall take when we visit each node will depend on the application. For lists, the nodes come in a natural order from first to last, and traversal follows the same order. For trees, however, there are many different orders in which we can traverse all the nodes. Let V, L and R respectively represent visiting root, traversing left subtree, and traversing right subtree. There are three standard traversal orders. 1. PREorder: 2. INorder: V L R L V R
50
___
Lab Session 12
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
3. POSTorder:
L R V
These three names are chosen according to the step at which the given node is visited. With PREorder traversal, the root is visited before the subtrees; with INorder traversal, root is visited between them; and with POSTorder traversal, the root is visited after both of the subtrees. As an example, consider the following binary tree: 1
The choice of the names PREorder, INorder, and POSTorder for the three most important traversal methods is not accidental, but relates closely to a motivating example of considerable interest, that of expression trees. An expression tree is built from simple operators of an (arithmetic or logical) expression by placing operands as the leaves of a binary tree and the operators as the interior nodes. For example, a (b x c) __
a b
x c
(a < b) or (c < d) or
< a b
51
< c d
___
Lab Session 12
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
ALGORITHMS
Declarations typedef struct treenode{ TreeEntry entry; TreeNode *left; TreeNode *right; }TreeNode; The type TreeEntry depends on the application. Algorithm A1: Create-Tree Operation This function has no precondition and results in an empty binary tree to which root points. void CreateTree (TreeNode *root) { *root = NULL; } Algorithm A2: Tree-Empty Operation It accepts root and returns TRUE or FALSE according as the tree is empty or not. boolean TreeEmpty (TreeNode *root) { return (root = = NULL); } Algorithm A3: PREorder Traversal In each of the traversal algorithms we assume existence of a function Visit that does the desired task for each node. void PREorder (TreeNode *root, void (* Visit) (TreeEntry x)) { if (root) { Visit (root entry); PREorder (root left, Visit); PREorder (root right, Visit); } } Algorithm A4: INorder Traversal void INorder (TreeNode *root, void (* Visit) (TreeEntry x)) {
52
___
Lab Session 12
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
if (root) { INorder (root left, Visit); Visit (root entry); INorder (root right, Visit); } } Algorithm A5: POSTorder Traversal void POSTorder (TreeNode *root, void (* Visit) (TreeEntry x)) { if (root) { POSTorder (root left, Visit); POSTorder (root right, Visit); Visit (root entry); } }
EXERCISES
a) Draw expression tree for the following infix expressions and then give their postfix and prefix expressions. i) log n! ii) (A+B) * (C + log (D+E!) sin (G/H)) iii) x=(-b (b2 - 4ac) ) / 2a
53
___
Lab Session 12
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
b) Write a function int TreeSize (Tree *root) that will count all the nodes of a linked binary tree.
54
___
Lab Session 12
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
c) Write a function void ClearTree (Tree *root) that will traverse a binary tree (in whatever order you find works best) and dispose of all of its nodes.
55
___
Lab Session 12
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
d) Design an algorithm to perform a double-order traversal of a binary tree, meaning that each node of the tree, the algorithm first visits the node, then traverses the left subtree (in double order), then visits the node again, then traverses its right subtree (in double order).
56
___
Lab Session 13
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 13
OBJECT
Implementation of search through a linked binary search tree.
THEORY
We have discussed two advantages of using linked lists: (1) efficiency of insertions and deletions, and (2) efficient use of memory space. One of the drawbacks of using a linked list is the time it takes to search a long list. A sequential search of all the nodes in the whole list is an O (N) operation. We already know that binary search algorithm applied on an array is an O (log2 N) operation. It would be nice if we could binary search a linked list, but there is no practical way to find the midpoint of a linked list. We can, however reorganize the lists elements into a linked structure that is just perfect for binary searching: the binary search tree. The binary search tree provides us with a structure that retains the flexibility of a linked list while allowing quicker O (log2 N) access to any node in the list. A structure with a unique starting node (the root), in which each node is capable of having at most two child nodes, and in which a unique path exists from the root to every other node. A B
root level 0
level 1
level 2
level 3
The level of a node refers to its distance from the root. If we designate the level of the root as 0, every other node is assigned a level number that is 1 more than the level of its parent. The height (or depth) of a tree is the maximum number of nodes in a branch of tree. This turns out to be 1 more than the largest level number. A binary search tree is a binary tree in which the value in any node is greater than the value in any children in its left subtree and less than the value in any children in its right subtree. For example,
57
___
Lab Session 13
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
D F
It is important to note that no two entries in a binary search tree may have equal values. ANALYZING PERFORMANCE CHARACTERISTICS
Binary search trees are interesting, in part, because they yield performance advantages. However, without going into mathematical details, we mention here the shape that a binary search tree takes in the best, worst, and average cases. Case Best Case Worst Case Average Case TREE SEARCH Tree Shape Leaves on at most two adjacent levels Exactly one internal node on each level Reasonably balanced, only occasionally deep
The most important operation for binary search trees is the one from which their name comes: a function to search through a linked binary search tree for an entry with a particular target key. To search for the target, we first compare it with the key at the root of the tree. If it is the same, then our job is done. If it is less than the root, we go to the left subtree; and if it is greater than the root, then we go to the right subtree and continue the search.
ALGORITHMS
Recursive Version TreeNode *TreeSearch (TreeNode *root, KeyType target) { if (root) if (LT (target, root entry.key)) /* LT checks whether target key is < that of node being visited */ root = TreeSearch (root left, target); else if (GT (target, root entry.key)) /* GT checks whether target key is > that of node being visited */ root = TreeSearch (root right, target); return root;}
58
___
Lab Session 13
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Recursion Removal The above function has tail recursion, that is, as the last statement executed in the function. By using a loop, it is always possible to change tail recursion into iteration. Here, we write a loop in place of the cascaded if statements, and we use the variable position to move through the tree. while (position && NE (target, position entry.key)) /* NE to check for not equal */ if (LT (target, position entry.key)) position = position left; else position = position right;
EXERCISES
a) What are the maximum and minimum numbers of levels that a binary search tree with 100 nodes can have? Justify your answer.
b) Write a non-recursive algorithm Ancestors that prints the ancestors of a given node whose info field contains a value Num. Num only occurs once in the tree.
59
___
Lab Session 13
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
c) Your CR wrote the following program to perform search for AirportCodes in the binary search tree. Comment on it with regard to correctness. If correct, explain. typedef char AirportCode [4]; typedef struct TreeNodeTag { AirportCode Struct TreeNodeTag Struct TreeNodeTag } TreeNode;
TreeNode *BinaryTreeSearch (AirportCode A, TreeNode *T) { TreeNode *N, int result; N =T; while (N != NULL) { if ( (result = strcmp (A, N Airport)) = = 0) return (N); /* N points to the node containing A */ else if (result < 0) N = N Leftlink; /* Let N point to the left subtrees root */ else N = N Rightlink; /* Let N point to the right subtrees root */ } return (N); }
60
___
Lab Session 13
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
d) Write a recursive version of the program in exercise (c) that works correctly.
61
___
Lab Session 13
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
e) Write a function TreeInsert to insert a new entry into a binary search tree whose root node is referenced by the tree node pointer *T.
62
___
Lab Session 14
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 14
OBJECT
Analysis of methods of graph representations and construction of graph traversal algorithms.
THEORY
If we are to write programs for solving problems concerning graphs, then we must find ways to represent the mathematical structure of a graph as some kind of data structure. There are several methods in common use, which differ fundamentally in the choice of abstract data type used to represent graphs, and there are several variations depending on the implementation of abstract data type. In other words, we begin with one mathematical system (a graph), then we study how it can be described in terms of abstract data types (sets, tables, and lists can all be used, as it turns out), and finally we choose implementations for the abstract data type that we select. ADJACENCY LIST
The adjacency list of a given vertex V is the list of all adjacent vertices of V. LINKED IMPLEMENTATION
Greatest flexibility is obtained by using linked lists for both the vertices and the adjacency lists. This implementation has the following declaration. typedef struct vertex Vertex; typedef struct edge Edge; struct vertex{ Edge *firstedge; Vertex *nextvertex; }; struct edge{ Vertex *endpoint; Edge *nextedge; }; typedef Vertex *Graph;
/* vertex to which the edge points */ /* next edge on the adjacency list */
CONTIGUOUS IMPLEMENTATION
Although the linked implementation is very flexible, it is sometimes awkward to navigate through the linked lists, and many algorithms require random access to vertices. Therefore the following contiguous implementation is often better. For a contiguous adjacency list, we must keep a counter, and for this we use standard notation from graph theory: The valence of a
63
___
Lab Session 14
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
vertex is defined as the number of edges on which it lies, and therefore it is also the number of vertices adjacent to it. This contiguous implementation is given below. typedef typedef int AdjacencyList [MAXVERTEX];
struct graph{ int n; /* number of vertices in the graph */ int valence [MAXVERTEX]; AdjacencyList A [MAXVERTEX]; }Graph; MIXED IMPLEMENTATION
The final implementation uses a contiguous list for the vertices and linked storage for the adjacency lists. typedef struct edge{ Vertex endpoint; struct edge *nextedge; }Edge; typedef struct graph{ int n; /* number of vertices in the graph */ Edge *firstedge [MAXVERTEX]; }Graph;
ALGORITHMS
In many problems, we wish to investigate all the vertices in a graph in some systematic order, just as with binary trees. In tree traversal, we had a root vertex with which we generally started; in graph, we do not have any one vertex singled out as special, and therefore the traversal may start at an arbitrary vertex. Although there are many possible orders for visiting the vertices of a graph, two methods are of particular importance. Algorithm A1: Depth-First Traversal Suppose that the traversal has just visited a vertex v, and let w1, w2, . . . , wk be the vertices adjacent to v. Then we shall next visit w1 and keep w2, . . . , wk waiting. After visiting w1, we traverse all the vertices to which it is adjacent before returning to traverse w2, . . . , wk. void DepthFirst (Graph G, void (* Visit) (Vertex)) /* (Post-Condition) The function Visit has been performed at each vertex of G in depth-first order. The function Traverse produces the recursive depth-first order. */ { Boolean visited [MAXVERTEX]; Vertex v; for (all v in G) visited [v] = FALSE; for (all v in G) if (!visited [v])
64
___
Lab Session 14
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Traverse (v, Visit); } The recursion is performed in the following function, to be declared along with the previous one. void Traverse (Vertex v, void(* Visit) (Vertex)) { Vertex w; visited [v] = TRUE; visit (v) ; for (all w adjacent to v) if (! visited [w] ) Traverse (w, Visit); } Algorithm A2: Breadth-First Traversal void BreadthFirst (Graph G, void (* Visit) (Vertex)) /* (Post-Condition) The function Visit has been performed at each vertex of G in breadth-first order. */ { Queue Q; Boolean visited [MAXVERTEX]; Vertex v, w; for (all v in G) visited [v] = FALSE; CreateQueue (Q); for (all v in G) if (!visited [v] ) { Enqueue (v, Q); do { Dequeue (v, Q); if (!visited [v] ) { visited [v] = TRUE; Visit (v); } for (all w adjacent to v) if (!visited [w]) Enqueue (w, Q); } while (!Empty(Q)); } }
EXERCISES
a) A graph is regular if every vertex has the valence (that is, if it is adjacent to the same number of other vertices). For a regular graph, a good implementation is to keep the vertices in a linked list and the adjacency lists contiguous. The length of all the adjacency lists is called the degree of the graph. Write C declarations for this implementation of regular graphs.
65
___
Lab Session 14
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
b) Write C function ReadGraph that will read from the terminal the vertices in an undirected graph and lists of adjacent vertices.
c) Write C function WriteGraph that will write pertinent information specifying a graph to the terminal.
66
___
Lab Session 14
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
d) Use the functions ReadGraph and WriteGraph to implement and test the breadth-first traversal algorithm.
67
___
Lab Session 14
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
e) Use the functions ReadGraph and WriteGraph to implement and test the depth-first traversal algorithm.
68
___
Lab Session 15
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
Lab Session 15
OBJECT
Development of an algorithm for the game of Life.
THEORY
The game of Life is really a simulation, not a game with players. It takes place on an unbounded rectangular grid in which each cell can either be occupied by an organism or not. Occupied cells are called alive; unoccupied cells are called dead. Which cells are alive changes from generation to generation according to the number of neighboring cells that are alive, as follows: 1. The neighbors of a given cell are the eight cells that touch it vertically, horizontally, or diagonally. 2. If a cell is alive but either has no neighboring cells alive or only one alive, then in the next generation the cell dies of loneliness. 3. If a cell is alive and has four or more neighboring cells also alive, then in the next generation the cell dies of overcrowding. 4. A living cell with either two or three living neighbors remains alive in the next generation. 5. If a cell is dead, then in the next generation it will become alive if it has exactly three neighboring cells, no more or fewer, that are already alive. All other dead cells remain dead in the next generation. 6. All births and deaths take place at exactly the same time, so that dying cells can help to give birth to another, but cannot prevent the death of others by reducing overcrowding, nor can cells being born either preserve or kill cells living in the previous generation. As a first example consider the community:
0 0 0 0 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
By rule 2 both cells will die in the next generation. Rule 5 shows that no cells will become alive, so the community dies out.
69
___
Lab Session 15
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
0 0 0 0 0 0
0 1 2 2 1 0
0 2 3 3 2 0
0 2 3 3 2 0
0 1 2 2 1 0
0 0 0 0 0 0
Each of the living cells has a neighbor count of three and hence remains alive, but the dead cells all have neighbor counts of two or less and hence none of them becomes alive. The two communities:
0 1 1 1 0 and 0 0 0 0 0
0 2 1 2 0
0 3 2 3 0
0 2 1 2 0
0 1 1 1 0
1 2 3 2 1
1 1 2 1 1
1 2 3 2 1
0 0 0 0 0
continue to alternate from generation to generation, as indicated by the neighbor counts shown.
EXERCISES
a) Determine by hand calculations what will happen to each of the communities shown, over the course of four generations.
b
70
___
Lab Session 15
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
71
___
Lab Session 15
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
b) Write a program that will show how an initial community will change from generation to generation.
72
___
Lab Session 15
NED University of Engineering & Technology Department of Computer & Information Systems Engineering
73