Data structures using python lab manual

DATA STRUCTURES LABORATORY LAB MANUAL Academic Year

:

2017 - 2018

Course Code

:

ACS102

Regulations

:

IARE - R16

Semester

:

II Semester

Branch

:

CSE / IT / ECE / EEE

Prepared by Ms. B Padmaja Associate Professor

Department of Computer Science and Engineering

INSTITUTE OF AERONAUTICAL ENGINEERING (Autonomous) Dundigal, Hyderabad - 500 043

INSTITUTE OF AERONAUTICAL ENGINEERING (Autonomous) Dundigal, Hyderabad - 500 043

Program Outcomes (Common for all branches) PO1 PO2

PO3

PO4

PO5

PO6

PO7

PO8 PO9 PO10

PO11

PO12

Engineering knowledge: Apply the knowledge of mathematics, science, engineering fundamentals, and an engineering specialization to the solution of complex engineering problems. Problem analysis: Identify, formulate, review research literature, and analyze complex engineering problems reaching substantiated conclusions using first principles of mathematics, natural sciences, and engineering sciences. Design/development of solutions: Design solutions for complex engineering problems and design system components or processes that meet the specified needs with appropriate consideration for the public health and safety, and the cultural, societal, and environmental considerations. Conduct investigations of complex problems: Use research-based knowledge and research methods including design of experiments, analysis and interpretation of data, and synthesis of the information to provide valid conclusions. Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern engineering and IT tools including prediction and modeling to complex engineering activities with an understanding of the limitations. The engineer and society: Apply reasoning informed by the contextual knowledge to assess societal, health, safety, legal and cultural issues and the consequent responsibilities relevant to the professional engineering practice. Environment and sustainability: Understand the impact of the professional engineering solutions in societal and environmental contexts, and demonstrate the knowledge of, and need for sustainable development. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and norms of the engineering practice. Individual and team work: Function effectively as an individual, and as a member or leader in diverse teams, and in multidisciplinary settings. Communication: Communicate effectively on complex engineering activities with the engineering community and with society at large, such as, being able to comprehend and write effective reports and design documentation, make effective presentations, and give and receive clear instructions. Project management and finance: Demonstrate knowledge and understanding of the engineering and management principles and apply these to one’s own work, as a member and leader in a team, to manage projects and in multidisciplinary environments. Life-long learning: Recognize the need for, and have the preparation and ability to engage in independent and life-long learning in the broadest context of technological change. Program Specific Outcomes (CSE)

PSO1 Professional Skills: The ability to research, understand and implement computer programs in the areas related to algorithms, system software, multimedia, web design, big data analytics, and networking for efficient analysis and design of computer-based systems of varying complexity. PSO2 Problem-Solving Skills: The ability to apply standard practices and strategies in software project development using open-ended programming environments to deliver a quality product for business success. PSO3 Successful Career and Entrepreneurship: The ability to employ modern computer languages, environments, and platforms in creating innovative career paths, to be an entrepreneur, and a zest for higher studies.

2|Page

Program Specific Outcomes (IT) PSO1

PSO2

PSO3

Professional Skills: The ability to understand, analyze and develop computer programs in the areas related to algorithms, system software, multimedia, web design, big data analytics, and networking for efficient analysis and design of computer - based systems of varying complexity. Software Engineering Practices: The ability to apply standard practices and strategies in software service management using open-ended programming environments with agility to deliver a quality service for business success. Successful Career and Entrepreneurship: The ability to employ modern computer languages, environments, and platforms in creating innovative career paths to be an entrepreneur, and a zest for higher studies. Program Specific Outcomes (ECE)

PSO1

PSO2

PSO3

Professional Skills: An ability to understand the basic concepts in Electronics & Communication Engineering and to apply them to various areas, like Electronics, Communications, Signal processing, VLSI, Embedded systems etc., in the design and implementation of complex systems. Problem-Solving Skills: An ability to solve complex Electronics and communication Engineering problems, using latest hardware and software tools, along with analytical skills to arrive cost effective and appropriate solutions. Successful Career and Entrepreneurship: An understanding of social-awareness & environmentalwisdom along with ethical responsibility to have a successful career and to sustain passion and zeal for real-world applications using optimal resources as an Entrepreneur. Program Specific Outcomes (EEE)

PSO1

PSO2

PSO3

Professional Skills: An ability to understand the basic concepts in Electronics & Communication Engineering and to apply them to various areas, like Electronics, Communications, Signal processing, VLSI, Embedded systems etc., in the design and implementation of complex systems. Problem-Solving Skills: An ability to solve complex Electronics and communication Engineering problems, using latest hardware and software tools, along with analytical skills to arrive cost effective and appropriate solutions. Successful Career and Entrepreneurship: An understanding of social-awareness & environmentalwisdom along with ethical responsibility to have a successful career and to sustain passion and zeal for real-world applications using optimal resources as an Entrepreneur.

3|Page

INSTITUTE OF AERONAUTICAL ENGINEERING (Autonomous) Dundigal, Hyderabad - 500 043

ATTAINMENT OF PROGRAM OUTCOMES & PROGRAM SPECIFIC OUTCOMES S. No.

1

Experiment

SEARCHING TECHNIQUES

2

SORTING TECHNIQUES

3

SORTING TECHNIQUES

4 5 6 7 8 9 10 11 12

Program Outcomes Attained

PO1, PO2, PO3 PO1, PO2, PO3 PO1, PO2, PO3

IMPLEMENTATION OF STACK AND QUEUE

PO2, PO3

APPLICATIONS OF STACK

PO3, PO4

IMPLEMENTATION OF SINGLE LINKED LIST IMPLEMENTATION OF CIRCULAR SINGLE LINKED LIST IMPLEMENTATION OF DOUBLE LINKED LIST IMPLEMENTATION OF STACK USING LINKED LIST IMPLEMENTATION OF QUEUE USING LINKED LIST

PO2, PO3 PO2, PO3 PO2, PO3 PO3, PO4 PO3, PO4

GRAPH TRAVERSAL TECHNIQUES

PO2, PO3

IMPLEMENTATION OF BINARY SEARCH TREE

PO2, PO3

4|Page

Program Specific Outcomes Attained CSE IT ECE EEE

PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2 PSO1, PSO2

PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3 PSO1, PSO3

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

PSO2

INSTITUTE OF AERONAUTICAL ENGINEERING (Autonomous)

Dundigal, Hyderabad - 500 043

Certificate This is to Certify that it is a bonafied record of Practical work done by Sri/Kum. _____________________________________ bearing the Roll No. ______________________ of ____________ Class _______________________________________ Branch in the ____________________________ laboratory during the Academic year ___________________ under our supervision.

Head of the Department

Lecture In-Charge

External Examiner

Internal Examiner

5|Page

DATA STRUCTURES LABORATORY II Semester: CSE / ECE / EEE / IT Course Code

Category

ACS102

Foundation

Contact Classes: Nil

Tutorial Classes: Nil

Hours / Week L T P 3

Credits C 2

Practical Classes: 36

Maximum Marks CIA SEE Total 30 70 100 Total Classes: 36

COURSE OBJECTIVES: The course should enable the students to: I. II. III. IV. V.

Understand various data representation techniques in the real world. Implement linear and non-linear data structures. Analyze various algorithms based on their time and space complexity. Develop real-time applications using suitable data structure. Identify suitable data structure to solve various computing problems. LIST OF EXPERIMENTS

WEEK-1

SEARCHING TECHNIQUES

Write Python programs for implementing the following searching techniques. a. Linear search b. Binary search c. Fibonacci search WEEK-2

SORTING TECHNIQUES

Write Python programs for implementing the following sorting techniques to arrange a list of integers in ascending order. a. Bubble sort b. Insertion sort c. Selection sort WEEK-3

SORTING TECHNIQUES

Write Python programs for implementing the following sorting techniques to arrange a list of integers in ascending order. a. Quick sort b. Merge sort WEEK-4

IMPLEMENTATION OF STACK AND QUEUE

Write Python programs to a. Design and implement Stack and its operations using List. b. Design and implement Queue and its operations using List. WEEK-5

APPLICATIONS OF STACK

Write Python programs for the following: a. Uses Stack operations to convert infix expression into postfix expression. b. Uses Stack operations for evaluating the postfix expression.

6|Page

WEEK-6

IMPLEMENTATION OF SINGLE LINKED LIST

a. Write Python programs for the following operations on Single Linked List. (i) Creation (ii) insertion (iii) deletion (iv) traversal b. To store a polynomial expression in memory using single linked list. WEEK-7

IMPLEMENTATION OF CIRCULAR SINGLE LINKED LIST

Write Python programs for the following operations on Circular Linked List. (i) Creation (ii) insertion (iii) deletion (iv) traversal WEEK-8

IMPLEMENTATION OF DOUBLE LINKED LIST

Write Python programs for the following: Uses functions to perform the following operations on Double Linked List. (i) Creation (ii) insertion (iii) deletion (iv) traversal in both ways. WEEK-9

IMPLEMENTATION OF STACK USING LINKED LIST

Write a Python program to implement Stack using linked list. WEEK-10

IMPLEMENTATION OF QUEUE USING LINKED LIST

Write a Python program to implement Linear Queue using linked list. WEEK-11

GRAPH TRAVERSAL TECHNIQUES

Write Python programs to implement the following graph traversal algorithms: a. Depth first search. b. Breadth first search. WEEK-12

IMPLEMENTATION OF BINARY SEARCH TREE

Write a Python program to perform the following: a. Create a binary search tree. b. Traverse the above binary search tree recursively in pre-order, post-order and in-order. c. Count the number of nodes in the binary search tree. LIST OF REFERENCE BOOKS: Y Daniel Liang, “Introduction to Programming using Python”, Pearson. Benjamin Baka, David Julian, “Python Data Structures and Algorithms”, Packt Publishers,2017. Rance D. Necaise, “Data Structures and Algorithms using Python”, Wiley Student Edition. Martin Jones, “Python for Complete Beginners”, 2015. Zed A. Shaw, “Learn Python the Hard Way: a very simple introduction to the terrifyingly beautiful world of computers and code”, 3e, Addison-Wesley, 2014. 6. Hemant Jain, “Problem Solving in Data Structures and Algorithms using Python: programming interview guide”, 2016. 1. 2. 3. 4. 5.

WEB REFERENCES: 1. 2. 3. 4. 5. 6.

https://docs.python.org/3/tutorial/datastructures.html http://interactivepython.org/runestone/static/pythonds/index.html http://www.tutorialspoint.com/data_structures_algorithms http://www.geeksforgeeks.org/data-structures/ http://www.studytonight.com/data-structures/ http://www.coursera.org/specializations/data-structures-algorithms

7|Page

WEEK-1 SEARCHING TECHNIQUES

1.1

OBJECTIVE: a. Write a Python script to for implementing linear search technique. b. Write a Python script to for implementing binary search technique. c. Write a Python script to for implementing Fibonacci search technique.

1.2

RESOURCES: Python 3.4.0

1.3

PROGRAM LOGIC: Linear Search Algorithm Algorithm linsrch (a[], x) { // a[1:n] is an array of n elements index := 0; flag := 0; while (index < n) do { if (x = a[index]) then { flag := 1; break; } index ++; } if(flag =1) write(“Data found “); else write(“data not found”); } Example: Given a list of n elements and search a given element x in the list using linear search. a. Start from the leftmost element of list a[] and one by one compare x with each element of list a[]. b. If x matches with an element, return the index. c. If x doesn’t match with any of elements, return -1. Consider a list with 10 elements and search for 9. a = [56, 3, 249, 518, 7, 26, 94, 651, 23, 9]

8|Page

Index → Iteration 1 Iteration 2 Iteration 3 Iteration 4 Iteration 5 Iteration 6 Iteration 7 Iteration 8 Iteration 9 Iteration 10

0 56 56 56 56 56 56 56 56 56 56

1 3 3 3 3 3 3 3 3 3 3

2 249 249 249 249 249 249 249 249 249 249

3 518 518 518 518 518 518 518 518 518 518

4 7 7 7 7 7 7 7 7 7 7

5 26 26 26 26 26 26 26 26 26 26

6 94 94 94 94 94 94 94 94 94 94

7 651 651 651 651 651 651 651 651 651 651

8 23 23 23 23 23 23 23 23 23 23

9 9 9 9 9 9 9 9 9 9 9

Binary Search Algorithm Algorithm binsrch (a[], n, x) { // a[1:n] is an array of n elements low = 1; high = n; while (low < high) do { mid = (low + high)/2 ; if (x < a[mid]) then high = mid – 1; else if (x > a[mid]) then low = mid + 1; else return mid; } return 0; } Example: Given a sorted list of a[] of n elements, search a given element x in list. a. Search a sorted list by repeatedly dividing the search interval in half. Begin with an interval covering the whole list. b. If the search key is less than the item in the middle item, then narrow the interval to the lower half. Otherwise narrow it to the upper half. c. Repeat the procedure until the value is found or the interval is empty. Consider a sorted list a[] with 9 elements and the search key is 31. 0 11

1 23

2 31

3 33

4 65

5 68

Let the search key = 31. First low = 0, high = 8, mid = (low + high) = 4 a[mid] = 65 is the centre element, but 65 > 31. So now high = mid - 1= 4 - 1 = 3, low = 0, mid = (0 + 3) / 2 = 1 9|Page

6 71

7 89

8 100

a[mid] = a[1] = 23, but 23 < 31. Again low = mid +1 = 1 +1 =2, high = 3, mid = (2 + 3) /2 = 2 a[mid] = a[2] = 31 which is the search key, so the search is successful. Fibonacci Search Algorithm Algorithm fib_Search (arr, x, n) { // arr[1:n] is an array of n elements M2 := 0 ; M1 := 1 ; M := M2 +M1 ; while (fibM < n) do { M2 := M1; M1: =M; M := M2 + M1; } Offset: = -1; while (fibM > 1) do { i := min(offset+M2, n-1); if (arr[i] < x) then { M := M1; M1 := M2; M2: = M -M1; offset = i } else if (arr[i] > x) then { M:= M2; M1: = M1 -M2; M2 := M - M1; } else return i; } if(M1 and arr[offset+1] = x) then return offset+1; return -1; } Example: Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array. Fibonacci Numbers are recursively defined as F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1. 10 | P a g e

First few Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … Let a[0..n-1] be the input list and element to be searched be x. 1. Find the smallest Fibonacci Number greater than or equal n. Let this number be M (m’th Fibonacci Number). Let the two Fibonacci numbers preceding it be M1 [(m-1)’th Fibonacci Number] and M2 [(m-2)’th Fibonacci Number]. 1. While the array has elements to be inspected: Compare x with the last element of the range covered by M2 2. If x matches, return index. 3. Else If x is less than the element, move the three Fibonacci variables two Fibonacci down, indicating elimination of approximately rear two-third of the remaining array. 4. Else x is greater than the element, move the three Fibonacci variables one Fibonacci down. Reset offset to index. Together these indicate elimination of approximately front one-third of the remaining array. 2. Since there might be a single element remaining for comparison, check if M1 is 1. If Yes, compare x with that remaining element. If match, return index. Consider a list a[] with 11 elements and the search element is 85. n = 11 Index 0 1 2 3 4 5 6 a[i] 10 22 35 40 45 50 80

7 82

8 85

9 90

10 100

Smallest Fibonacci number greater than or equal to 11 is 13. M2 = 5, M1 = 8, M = M1 + M2 = 13 Initialize offset = 0 Check the element at index i = min(offset + M2, n) M2 5 3 2 1 1.4

M1 8 5 3 1

M 13 8 5 2

Offset 0 5 8 8

I = min(offset + M2, n) 5 8 10 9

A[i] 45 82 90 85

Consequence Move one down, reset offset Move one down, reset offset Move two down Return i

PROCEDURE: 1. 2.

Create: Open a new file in Python shell, write a program and save the program with .py extension. Execute: Go to Run -> Run module (F5)

1.5 SOURCE CODE: Implementation of Linear Search def l_search(a,x,l,n): if l=0: print("The element found at",pos+1,"position") else: print("Element not found") Output:

1.6

PRE LAB VIVA QUESTIONS: 1. 2. 3. 4. 5.

14 | P a g e

Define searching? Define a list? List out different types of searching techniques? Differentiate between list and dictionary?

1.7

LAB ASSIGNMENT: 1. A person has registered for voter id , he received a voter number and he need to check whether it exist in the voter or not. Use a binary searching in a recursive way to find whether the voter number exist in the list or not. 2. Use linear search technique to search for a key value in a given list of characters and print the message found or not.

1.8

POST LAB VIVA QUESTIONS: 1. Find the time complexity of linear search? 2. Find the time complexity of binary search? 3. Find the time complexity of Fibonacci search?

15 | P a g e

WEEK - 2 SORTING TECHNIQUES 2.1

OBJECTIVE: a. Write Python script for implementing Bubble sort techniques to arrange a list of integers in ascending order. b. Write Python script for implementing insertion sort techniques to arrange a list of integers in ascending order. c. Write Python script for implementing selection sort techniques to arrange a list of integers in ascending order.

2.2

RESOURCES: Python 3.4.0

2.3

PROGRAM LOGIC: Bubble Sort Algorithm Algorithm bubblesort ( x[], n) { // x[1:n] is an array of n elements for i := 0 to n do { for j := 0 to n–i-1 d0 { if (x[j] > x[j+1]) { temp = x[j]; x[j] = x[j+1]; x[j+1] = temp; } } } } Example: Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are not in order. First Pass 5 1 1 5 1 4 1 4 Second Pass 1 4 1 4 1 2 1 2 Third Pass 1 2 1 2 1 2 1 2

16 | P a g e

4 4 5 2

2 2 2 5

8 8 8 8

Compare the first two elements, and swaps since 5 > 1 Compare 5 and 4 and swap since 5 > 4 Compare 5 and 2 and swap since 5 > 2 Compare 5 and 8 and since 5 < 8, no swap.

2

5

8

2 4 4

5 5 5

8 8 8

Compare the first two elements, and as 1 < 4, no swap. Compare 4 and 2, swap since 4 > 2 Compare 4 and 5, no swap. Compare 5 and 8 and no swap.

4 4 4 4

5 5 5 5

8 8 8 8

Compare the first two elements and no swap. Compare 2 and 4, no swap. Compare 4 and 5, no swap. Compare 5 and 8, no swap.

Fourth Pass 1 2 1 2 1 2 1 2

4 4 4 4

5 5 5 5

8 8 8 8

Compare the first two elements and no swap. Compare 2 and 4, no swap. Compare 4 and 5, no swap. Compare 5 and 8, no swap.

Insertion Sort Algorithm Algorithm insertionsort (a, n) {//sort the array a[1:n] in ascending order for j:=2 to n do { item:=a[j]; i=j-1; while((i>1) and (item< a[i])) do { a[i+1]:=a[i]; i:=i-1; } a[i+1]:=item; } } Example: This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. An element which is to be inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted. Consider an unsorted list with 8 elements. 14

33

27

10

35

19

42

44

14

33

27

10

35

19

42

44

14 14 10

27 27 14

33 33 27

10 10 33

35 35 35

19 19 19

42 42 42

44 44 44

10 10 10 10 10

14 14 14 14 14

27 27 27 19 19

33 33 33 27 27

35 35 35 33 33

19 19 19 35 35

42 42 42 42 42

44 44 44 44 44

Selection Sort Algorithm Algorithm selectionSort ( low, high ) { //a[low : high] is an array of size n i=0, j=0, temp=0, ; for i: =low to high do { minindex = i; for j: =i+1 to high do { if( a[j] < a[minindex] ) then 17 | P a g e

Compares the first two elements 14 and 33 and these element are already in ascending order. Now 14 is in sorted sub-list. Compare 33 with 27 and 33 is not in correct position. So swap 33 with 27. Now we have 14 and 27 in the sorted sub-list. Next compare 33 with 10. Compare 27 with 10 and 14 with 10. Insert 10 in the proper place. Compare 33 and 35, no swap. Compare 35 with 19 Compare 33 with 19, 27 with 19, Compare 35 with 42, no swap. Compare 42 with 44, no swap.

minindex := j; } temp := a[i]; a[i] := a[minindex]; a[minindex] := temp; } } Example: The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. In every iteration of selection sort, the minimum element from the unsorted sub-array is picked and moved to the sorted subarray. Consider a list a = [64, 25, 12, 22, 11] Index List

0 64

1 25

2 12

3 22

4 11

Iteration 1

11

25

12

22

64

Iteration 2

11

12

25

22

64

Iteration 3

11

12

22

25

64

Iteration 4

11

12

22

25

64

2.4

Remarks Find the minimum element in a[0 .. 4] and place it at beginning. Find the minimum element in a[1 .. 4] and place it at beginning of a[1 .. 4] Find the minimum element in a[2 .. 4] and place it at beginning of a[2 .. 4] Find the minimum element in a[3 .. 4] and place it at beginning of a[3 .. 4] Finally the list is sorted.

PROCEDURE: 1. Create: open Python shell write a program after that save the program with .py extension. 2. Execute: F5

2.5

SOURCE CODE: Program for implementing Bubble Sort def b_sort(a): n = len(a) for i in range(n): for j in range(0, n-i-1): if a[j] > a[j+1] : a[j], a[j+1] = a[j+1], a[j] print("Enter elements into list:") a=[int(x) for x in input().split()] b_sort(a) print("The sorted list is ",a)

18 | P a g e

Output:

Program for implementing Insertion Sort def i_sort(a): for i in range(1,len(a)): temp=a[i] pos=i while pos>0 and a[pos-1]>temp: a[pos]=a[pos-1] pos-=1 a[pos]=temp print("Enter elements into list:") a=[int(x) for x in input().split()] i_sort(a) print("The sorted list is",a)

19 | P a g e

Output:

Program for implementing Selection Sort def s_sort(a): for i in range(len(a)): least=i for k in range(i+1,len(a)): if a[k]= all the elements in a[1 : n]. { if (p