Data Structures and Program Design Using Python E-Book

Mercury Learning and Information

• Herausgeber: Packt Publishing
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 402

Veröffentlichungsjahr: 2024

Beschreibung

This book, part of the Pocket Primer series, introduces the basic concepts of data science using Python 3 and other applications. It offers a fast-paced introduction to data analytics, statistics, data visualization, linear algebra, and regular expressions. The book features numerous code samples using Python, NumPy, R, SQL, NoSQL, and Pandas. Companion files with source code and color figures are available.
Understanding data science is crucial in today's data-driven world. This book provides a comprehensive introduction, covering key areas such as Python 3, data visualization, and statistical concepts. The practical code samples and hands-on approach make it ideal for beginners and those looking to enhance their skills.
The journey begins with working with data, followed by an introduction to probability, statistics, and linear algebra. It then delves into Python, NumPy, Pandas, R, regular expressions, and SQL/NoSQL, concluding with data visualization techniques. This structured approach ensures a solid foundation in data science.

Leseprobe

DATA STRUCTURESANDPROGRAM DESIGNUSING PYTHON

LICENSE, DISCLAIMER OF LIABILITY, AND LIMITED WARRANTY

By purchasing or using this book and disc (the “Work”), you agree that this license grants permission to use the contents contained herein, including the disc, but does not give you the right of ownership to any of the textual content in the book / disc or ownership to any of the information or products contained in it. This license does not permit uploading of the Work onto the Internet or on a network (of any kind) without the written consent of the Publisher. Duplication or dissemination of any text, code, simulations, images, etc. contained herein is limited to and subject to licensing terms for the respective products, and permission must be obtained from the Publisher or the owner of the content, etc., in order to reproduce or network any portion of the textual material (in any media) that is contained in the Work.

MERCURY LEARNING AND INFORMATION (“MLI” or “the Publisher”) and anyone involved in the creation, writing, or production of the companion disc, accompanying algorithms, code, or computer programs (“the software”), and any accompanying Web site or software of the Work, cannot and do not warrant the performance or results that might be obtained by using the contents of the Work. The author, developers, and the Publisher have used their best efforts to insure the accuracy and functionality of the textual material and/or programs contained in this package; we, however, make no warranty of any kind, express or implied, regarding the performance of these contents or programs. The Work is sold “as is” without warranty (except for defective materials used in manufacturing the book or due to faulty workmanship).

The author, developers, and the publisher of any accompanying content, and anyone involved in the composition, production, and manufacturing of this work will not be liable for damages of any kind arising out of the use of (or the inability to use) the algorithms, source code, computer programs, or textual material contained in this publication. This includes, but is not limited to, loss of revenue or profit, or other incidental, physical, or consequential damages arising out of the use of this Work.

The sole remedy in the event of a claim of any kind is expressly limited to replacement of the book and/or disc, and only at the discretion of the Publisher. The use of “implied warranty” and certain “exclusions” vary from state to state and might not apply to the purchaser of this product.

DATA STRUCTURESANDPROGRAM DESIGNUSING PYTHON

A Self-Teaching Introduction

Dheeraj Malhotra, PhDNeha Malhotra, PhD

MERCURY LEARNING AND INFORMATIONDulles, VirginiaBoston, MassachusettsNew Delhi

Copyright © 2021 by MERCURY LEARNING AND INFORMATION LLC. All rights reserved.

This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display or mechanical display, including, but not limited to, photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher.

Publisher: David PallaiMERCURY LEARNING AND INFORMATION22841 Quicksilver DriveDulles, VA [e-mail][phone]

D. Malhotra and N. Malhotra. Data Structures and Program Design Using Python.ISBN: 978-1-68392-639-9

The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others.

Library of Congress Control Number: 2020946121

202122321 Printed on acid-free paper in the United States of America.

Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc. For additional information, please contact the Customer Service Dept. at [phone](toll free). Digital versions of our titles are available at: www.academiccourseware.com and other electronic vendors.

The sole obligation of MERCURY LEARNING AND INFORMATION to the purchaser is to replace the book and/or disc, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product.

Dedicated to ourloving parents and beloved students

CONTENTS

Preface

Acknowledgments

Chapter 1:Introduction to Data Structures

1.1Introduction

1.2Types of Data Structures

1.2.1Linear and Non-Linear Data Structures

1.2.2Static and Dynamic Data Structures

1.2.3Homogeneous and Non-Homogeneous Data Structures

1.2.4Primitive and Non-Primitive Data Structures

1.2.5Arrays/Lists

1.2.6Stacks

1.2.7Queues

1.2.8Linked Lists

1.2.9Trees

1.2.10Graphs

1.3Operations on Data Structures

1.4Algorithms

1.4.1Developing an Algorithm

1.5Approaches for Designing an Algorithm

1.6Analyzing an Algorithm

1.6.1Time-Space Trade-Off

1.7Abstract Data Types

1.8Big O Notation

1.9Summary

1.10Exercises

1.11Multiple Choice Questions

Chapter 2:Introduction to Python

2.1Introduction

2.2Python and Its Characteristics

2.3Python Overview

2.4Tools For Python

2.5easy_install and pip

2.6Quotations and Comments in Python

2.7Compiling the Python Program

2.8Object-Oriented Programming

2.9Character Set Used in Python

2.10Python Tokens

2.11Data Types in Python

2.12Structure of a Python Program

2.13Operators in Python

2.14Decision Control Statements

2.15Looping Statements

2.16Loop Control Statements

2.17Methods

2.18Summary

2.19Exercises

2.19.1Theory Questions

2.19.2Programming Projects

2.19.3Multiple Choice Questions

Chapter 3:Arrays/Lists

3.1Introduction

3.2Definition of an Array

3.3Array/List Declaration

3.4Array/List Initialization

3.5Calculating the Address of Array Elements

3.6Operations on Arrays/Lists

3.72-D Arrays/Two-Dimensional Arrays

3.8Declaration of Two-Dimensional Arrays/Lists

3.9Operations on 2-D Arrays/Lists

3.10Multidimensional Arrays/N-Dimensional Arrays

3.11Calculating the Address of 3-D Arrays

3.12Arrays and Their Applications

3.13Sparse Matrices

3.14Types of Sparse Matrices

3.15Representation of Sparse Matrices

3.16Summary

3.17Exercises

3.17.1Theory Questions

3.17.2Programming Questions

3.17.3Multiple Choice Questions

Chapter 4:Linked Lists

4.1Introduction

4.2Definition of a Linked List

4.3Memory Allocation in a Linked List

4.4Types of Linked Lists

4.4.1Singly Linked List

4.4.2Operations on a Singly Linked List

4.4.3Circular Linked Lists

4.4.4Operations on a Circular Linked List

4.4.5Doubly Linked List

4.4.6Operations on a Doubly Linked List

4.5Header Linked Lists

4.6Applications of Linked Lists

4.7Polynomial Representation

4.8Summary

4.9Exercises

4.9.1Theory Questions

4.9.2Programming Questions

4.9.3Multiple Choice Questions

Chapter 5:Queues

5.1Introduction

5.2Definition of a Queue

5.3Implementation of a Queue

5.3.1Implementation of Queues Using Arrays

5.3.2Implementation of Queues Using Linked Lists

5.4Operations on Queues

5.4.1Insertion

5.4.2Deletion

5.5Types of Queues

5.5.1Circular Queue

5.5.2Priority Queue

5.5.3De-queues (Double-Ended Queues)

5.6Applications of Queues

5.7Summary

5.8Exercises

5.8.1Theory Questions

5.8.2Programming Questions

5.8.3Multiple Choice Questions

Chapter 6:Searching and Sorting

6.1Introduction to Searching

6.2Linear Search or Sequential Search

6.2.1Drawbacks of a Linear Search

6.3Binary Search

6.3.1Binary Search Algorithm

6.3.2Complexity of a Binary Search Algorithm

6.3.3Drawbacks of a Binary Search

6.4Interpolation Search

6.4.1The Interpolation Search Algorithm

6.4.2Complexity of the Interpolation Search Algorithm

6.5Introduction to Sorting

6.5.1Types of Sorting Methods

6.6External Sorting

6.7Summary

6.8Exercises

6.8.1Theory Questions

6.8.2Programming Questions

6.8.3Multiple Choice Questions

Chapter 7:Stacks

7.1Introduction

7.2Definition of a Stack

7.3Overflow and Underflow in Stacks

7.4Operations on Stacks

7.5Implementation of a Stack

7.5.1Implementation of Stacks Using Arrays

7.5.2Implementation of Stacks Using Linked Lists

7.6Applications of Stacks

7.6.1Polish and Reverse Polish Notations

7.6.2Conversion from the Infix Expression to the Postfix Expression

7.6.3Conversion from an Infix Expression to a Prefix Expression

7.6.4Evaluation of a Postfix Expression

7.6.5Evaluation of a Prefix Expression

7.6.6Parenthesis Balancing

7.7Summary

7.8Exercises

7.8.1Theory Questions

7.8.2Programming Questions

7.8.3Multiple Choice Questions

Chapter 8:Trees

8.1Introduction

8.2Definitions

8.3Binary Tree

8.3.1Types of Binary Trees

8.3.2Memory Representation of Binary Trees

8.4Binary Search Tree

8.4.1Operations on Binary Search Trees

8.4.2Binary Tree Traversal Methods

8.4.3 Creating a Binary Tree Using Traversal Methods

8.5AVL Trees

8.5.1Need for Height-Balanced Trees

8.5.2Operations on an AVL Tree

8.6Summary

8.7Exercises

8.7.1Theory Questions

8.7.2Programming Questions

8.7.3Multiple Choice Questions

Chapter 9:Multi-Way Search Trees

9.1Introduction

9.2B-Trees

9.3Operations on a B-Tree

9.3.1Insertion in a B-Tree

9.3.2Deletion in a B-Tree

9.4Application of a B-Tree

9.5B+ Trees

9.6Summary

9.7Exercises

9.7.1Review Questions

9.7.2Multiple Choice Questions

Chapter 10:Hashing

10.1Introduction

10.1.1Difference between Hashing and Direct Addressing

10.1.2Hash Tables

10.1.3Hash Functions

10.1.4Collision

10.1.5Collision Resolution Techniques

10.2Summary

10.3Exercises

10.3.1Review Questions

10.3.2Multiple Choice Questions

Chapter 11:Files

11.1Introduction

11.2Terminology

11.3File Operations

11.4File Classification

11.5C vs. C++ vs. Java vs. Python File Handling

11.6File Organization

11.7Sequence File Organization

11.8Indexed Sequence File Organization

11.9Relative File Organization

11.10Inverted File Organization

11.11Summary

11.12Exercises

11.12.1 Review Questions

11.12.2 Multiple Choice Questions

Chapter 12:Graphs

12.1Introduction

12.2Definitions

12.3Graph Representation

12.3.1Adjacency Matrix Representation

12.3.2Adjacency List Representation

12.4Graph Traversal Techniques

12.4.1Breadth-First Search

12.4.2Depth-First Search

12.5Topological Sort

12.6Minimum Spanning Tree

12.6.1Prim’s Algorithm

12.6.2Kruskal’s Algorithm

12.7Summary

12.8Exercises

12.8.1Theory Questions

12.8.2Programming Questions

12.8.3Multiple Choice Questions

Appendix: Answers to Multiple Choice Questions

Index

PREFACE

Data structures are the building blocks of computer science. The objective of this text is to emphasize the fundamentals of data structures as an introductory subject. It is designed for beginners who would like to learn the basics of data structures and their implementation using the Python programming language. With this focus in mind, we present various fundamentals of the subject, well supported with real-world analogies to enable a quick understanding of the technical concepts and to help the reader in quickly identifying appropriate data structures to solve specific, practical problems. This book will serve the purpose of a text or reference book and will be of immense help especially to undergraduate or graduate students of various courses in information technology, engineering, computer applications, and information sciences.

Key Features:

•Practical Applications: Real-world analogies as practical applications are given throughout the text to quickly understand and connect the fundamentals of data structures with day to day, real-world scenarios. This approach, in turn, will assist the reader in developing the capability to identify the most appropriate and efficient data structure for solving a specific, real-world problem.

•Frequently Asked Questions: Frequently asked theoretical or practical questions are integrated throughout the content of the book, within related topics to assist readers in grasping the subject.

•Algorithms and Programs: To better understand the fundamentals of data structures at a generic level-followed by their implementation in Python, syntax independent algorithms, as well as implemented programs in Python, are discussed throughout the book. This presentation will assist the reader in getting both algorithms and their corresponding implementation within a single book.

•Numerical and Conceptual Exercises: To assist the reader in developing a strong foundation of the subject, various numerical and conceptual problems are included throughout the text.

•Multiple Choice Questions: To assist students for placement-oriented exams in various IT fields, several exercises are suitably chosen and are given in an MCQ format.

Dr. Dheeraj MalhotraDr. Neha MalhotraSeptember 2020

ACKNOWLEDGMENTS

We are indeed grateful to Chairman - Dr. S.C. Vats, Vice Chairman - Mr. Suneet Vats, Chairperson VSIT - Prof. Sidharth Mishra, and Dean VSIT- Prof. Supriya Madan of our employer institute - Vivekananda Institute of Professional Studies (GGS IP University). They are always a source of inspiration for us, and we feel honored because of their faith in us.

We also take this opportunity to extend our gratitude to our mentors Prof. O.P. Rishi (University of Kota), Dr. Sushil Chandra (DRDO, GOI), Prof. Udyan Ghose (GGS IP University), and Prof. M.N. Hoda (BVICAM) for their motivation to execute this project.

We are profoundly thankful to Mr. Sahil Pathak (VIPS, GGSIPU) and Mr. Deepanshu Gupta (Tech Mahindra Ltd.) for helping us in proofreading and compiling the codes in this manuscript.

It is not possible to complete a book without the support of a publisher. We are thankful to David Pallai and Jennifer Blaney of Mercury Learning and Information for their enthusiastic involvement throughout the tenure of this project.

Our heartfelt regards to our parents, siblings and family members who cheered us in good times and encouraged us in bad times.

Lastly, we have always felt inspired by our readers, especially in the USA, Canada, and India. Their utmost love and positive feedback for our first three titles of Data Structures using C, …C++, and …Java, all published with MLI, helped us to improve the current title further.

Dr. Dheeraj MalhotraDr. Neha MalhotraSeptember 2020

CHAPTER 1

INTRODUCTION TO DATA STRUCTURES

1.1INTRODUCTION

A data structure is an efficient way of storing and organizing the data elements in a computer’s memory. Data means a value or a collection of values. Structure refers to a method of organizing the data. The mathematical or logical representation of data in the memory is referred to as a data structure. The objective of a data structure is to store, retrieve, and update the data efficiently. A data structure can be considered as all the elements grouped under one name. The data elements are called members, and they can be of different types. Data structures are used in almost every program and software system. There are various kinds of data structures that are suited for different types of applications. Data structures are the building blocks of a program. For a program to run efficiently, a programmer must choose the appropriate data structures. A data structure is a crucial part of data management. As the name suggests, data management is a task that includes different activities, like the collection of data and the organization of data into structures. Data structures are used in stacks, queues, arrays, binary trees, linked lists, and hash tables.

A data structure helps us to understand the relationship of one element to another element and organize it within the memory. It is a mathematical or logical representation or organization of data in the memory. Data structures are extensively applied in the following areas:

•Compiler Design

•Database Management Systems (DBMS)

•Artificial Intelligence

•Network and Numerical Analysis

•Statistical Analysis Packages

•Graphics

•Operating Systems (OS)

•Simulations

There are many applications in which different data structures are used for their operations. Some data structures sacrifice speed for the efficient utilization of memory, while others sacrifice memory utilization and result in a faster speed. In today’s world, programmers aim not just to build a program, but to build an effective program. As previously discussed, for a program to be efficient, a programmer must choose the appropriate data structures. Hence, data structures are classified into various types. Now, let us discuss and learn about different types of data structures.

Frequently Asked Questions

1.Define the term “data structure.”

Answer:

A data structure is an organization of data in a computer’s memory or disk storage. In other words, a logical or mathematical model of a particular organization of data is called a data structure. A data structure in computer science is also a way of storing data in a computer so that it can be used efficiently. An appropriate data structure allows a variety of important operations to be performed using both resources, that is, the memory space and execution time, efficiently.

1.2TYPES OF DATA STRUCTURES

Data structures are classified into various types.

1.2.1Linear and Non-Linear Data Structures

A linear data structure is one in which the data elements are stored in a linear, or sequential, order; that is, data is stored in consecutive memory locations. A linear data structure can be represented in two ways; either it is represented by a linear relationship between various elements utilizing consecutive memory locations as in the case of arrays, or it may be represented by a linear relationship between the elements utilizing links from one element to another as in the case of linked lists. Examples of linear data structures include arrays, linked lists, stacks, and queues.

A non-linear data structure is one in which the data is not stored in any sequential order or consecutive memory locations. The data elements in this structure are represented by a hierarchical order. Examples of non-linear data structures include graphs and trees.

1.2.2Static and Dynamic Data Structures

A static data structure is a collection of data in memory that is fixed in size and cannot be changed during runtime. The memory size must be known in advance, as the memory cannot be reallocated later in a program. One example is an array.

A dynamic data structure is a collection of data in which memory can be reallocated during the execution of a program. The programmer can add or remove elements according to his/her need. Examples include linked lists, graphs, and trees.

1.2.3Homogeneous and Non-Homogeneous Data Structures

A homogeneous data structure is one that contains data elements of the same type (for example, arrays).

A non-homogeneous data structure contains data elements of different types (for example, structures).

1.2.4Primitive and Non-Primitive Data Structures

Primitive data structures are the fundamental data structures or predefined data structures that are supported by a programming language. Examples of primitive data structure types are integer, float, and char.

Non-primitive data structures are comparatively more complicated data structures that are created using primitive data structures. Examples of non-primitive data structures are arrays, files, linked lists, stacks, and queues.

The classification of different data structures is shown in Figure 1.1.

FIGURE 1.1 Classification of different data structures

Python supports various data structures. We now introduce all these data structures, and they are discussed in detail in the upcoming chapters.

Frequently Asked Questions

2.What is the difference between primitive data structures and non-primitive data structures?

Answer:

The data structures that are typically directly operated upon by machine-level instructions, that is, the fundamental data types such as int, float, and char, are known as primitive data structures. The data structures that are not fundamental are called non-primitive data structures.

Frequently Asked Questions

3.What is the difference between linear and non-linear data structures?

Answer:

The main difference between linear and non-linear data structures lies in the way in which data elements are organized. In the linear data structure, elements are organized sequentially, and therefore they are easy to implement in a computer’s memory. In non-linear data structures, a data element can be attached to several other data elements to represent specific relationships existing among them.

1.2.5Arrays/Lists

1.2.6Stacks

A stack is a collection of objects that are inserted and removed according to the Last-In, First-Out (LIFO) principle. A user may insert objects into a stack at any time, but may only access or remove the most recently inserted object that remains (at the so-called “top” of the stack). The name “stack” is derived from the metaphor of a stack of plates in a spring-loaded, cafeteria plate dispenser. In this case, the fundamental operations involve the “pushing” and “popping” of plates on the stack. When we need a new plate from the dispenser, we “pop” the top plate off the stack, and when we add a plate, we “push” it down on the stack to become the new top plate.

Practical Application:

A real-life example of a stack is a pile of plates arranged on a table.A person will pick up the first plate from the top of the stack.

The Stack ADT can be implemented in several ways. The two most common approaches to implement Stack ADT in Python include the use of a Python list and a linked list. The choice depends on the type of application involved.

1.2.7Queues

Another fundamental data structure is the queue. It is a close cousin of the stack, as a queue is a collection of objects that are inserted and removed according to the First-In, First-Out (FIFO) principle. That is, elements can be inserted at any time, but only the element that has been in the queue the longest can be next removed. We usually say that elements enter a queue at the back and are removed from the front. A metaphor for this terminology is a line of people waiting to get on an amusement park ride. People waiting for such a ride enter at the back of the line and get on the ride from the front of the line.

Practical Application:

For a simple illustration of a queue, imagine there is a line of people standing at the bus stop and waiting for the bus. The first person standing in the line will get into the bus first.

The Queue ADT can be implemented in several ways. The two most common approaches in Python include the use of a Python list and a linked list. The choice depends on the type of application involved.

1.2.8Linked Lists

The major drawback of the array is that the size or the number of elements must be known in advance. Thus, this drawback gave rise to the new concept of a linked list. A linked list is a linear collection of data elements. These data elements are called nodes, which store the address of the next node. A linked list is a sequence of nodes in which each node contains one or more than one data field and an address field that stores the address of the next node. Linked lists are dynamic; that is, memory is allocated when required.

FIGURE 1.2 Memory representation of a linked list

Figure 1.2 shows a linked list in which each node is divided into two slots:

1.The first slot contains information/data.

2.The second slot contains the address of the next node.

Practical Application:

A simple real-life example is a train; here, each train car is connected to the previous one and next one (except the first car (the engine) and the last car (the coach)).

The address part of the last node stores a special value called NULL, which denotes the end of the linked list. The advantage of a linked list over arrays is that now it is easier to insert and delete data elements, as we don’t have to do shifting each time. Yet searching for an element is difficult. More time is required to search for an element, and it requires a large amount of memory space. Hence, linked lists are used where a collection of data elements is required but the number of data elements in the collection is not known to us in advance.

Frequently Asked Questions

4.Define the term “linked list.”

Answer:

A linked list or one-way list is a linear collection of data elements called nodes, which give a linear order. It is a popular dynamic data structure. The nodes in the linked list are not stored in consecutive memory locations. For every data item in a node of the linked list, there is an associated address field that gives the address location of the next node in the linked list.

1.2.9Trees

1.2.10Graphs

1.3OPERATIONS ON DATA STRUCTURES

Here, we discuss various operations that are performed on data structures.

•Creation – This is the process of creating a data structure. The declaration and initialization of the data structure are done here. It is the first operation.

•Insertion – This is the process of adding new data elements in the data structure, for example, to add the details of an employee who has recently joined an organization.

•Deletion – This is the process of removing a particular data element from the given collection of data elements, for example, to remove the name of an employee who has left the company.

•Updating – This is the process of modifying the data elements of a data structure. For example, if the address of a student is changed, it should be updated.

•Searching – This is used to find the location of a particular data element or all the data elements with the help of a given key, for example, to find the names of people who live in New York.

•Sorting – This is the process of arranging the data elements in some order, that is, either ascending or descending order. An example is arranging the names of students of a class in alphabetical order.

•Merging – This is the process of combining the data elements of two different lists to form a single list of data elements.

•Traversal – This is the process of accessing each data element exactly once so that it can be processed. An example is to print the names of all the students of a class.

•Destruction – This is the process of deleting the entire data structure. It is the last operation in the data structure.

1.4ALGORITHMS

An algorithm is a systematic set of instructions combined to solve a complex problem. It is a step-by-finite-step sequence of instructions, each of which has a clear meaning and can be executed in a minimum amount of effort in finite time. In general, an algorithm is a blueprint for writing a program to solve the problem. Once we have a blueprint of the solution, we can easily implement it in any high-level language like C, C++, or Python. It divides the problem into a finite number of steps. An algorithm written in a programming language is known as a program. A computer is a machine with no brain or intelligence. Therefore, the computer must be instructed to perform a given task in unambiguous steps. Hence, a programmer must define his problem in the form of an algorithm written in English. Thus, such an algorithm should have the following features:

1.An algorithm should be simple and concise.

2.It should be efficient and effective.

3.It should be free of ambiguity; that is, the logic must be clear.

Similarly, an algorithm must have the following characteristics:

•Input – It reads the data of the given problem.

•Output – The desired result must be produced.

•Process/Definiteness – Each step or instruction must be unambiguous.

•Effectiveness – Each step should be accurate and concise. The desired result should be produced within a finite time.

•Finiteness – The number of steps should be finite.

1.4.1Developing an Algorithm

To develop an algorithm, some steps are necessary:

1.Defining or understanding the problem.

2.Identifying the result or output of the problem.

3.Identifying the inputs required by the problem and choosing the best input.

4.Designing the logic from the given inputs to get the desired output.

5.Testing the algorithm for different inputs.

6.Repeating the previous steps until it produces the desired result for all the inputs.

1.5APPROACHES FOR DESIGNING AN ALGORITHM

A complicated algorithm is divided into smaller units called modules. These modules are further divided into sub-modules. Thus, in this way, a complex algorithm can easily be solved. The process of dividing an algorithm into modules is called modularization. There are two popular approaches for designing an algorithm:

•Top-Down Approach

•Bottom-Up Approach

Now let us understand both approaches.

1.Top-Down Approach–A top-down approach states that the complex/complicated problem/algorithm should be divided into a smaller number of one or more modules. These smaller modules are further divided into one or more sub-modules. This process of decomposition is repeated until we achieve the desired output of module complexity. A top-down approach starts from the topmost module, and the modules are incremented accordingly until a level is reached where we don’t require any more sub-modules, that is, the desired level of complexity is achieved.

FIGURE 1.5 Top-down approach

Bottom-Up Approach–A bottom-up algorithm design approach is the opposite of a top-down approach. In this kind of approach, we first start with designing the basic modules and proceed further toward designing the high-level modules. The sub-modules are grouped to form a module of a higher level. Similarly, all high-level modules are grouped to form more high-level modules. Thus, this process of combining the sub-modules is repeated until we obtain the desired output of the algorithm.

FIGURE 1.6 Bottom-up approach

1.6ANALYZING AN ALGORITHM

An algorithm can be analyzed by two factors: space and time. We should develop an algorithm that makes the best use of both these resources. Analyzing an algorithm measures the efficiency of the algorithm. The efficiency of the algorithm is measured in terms of the speed and time complexity. The complexity of an algorithm is a function that measures the space and time used by an algorithm in terms of input size.

Time Complexity–The time complexity of an algorithm is the amount of time taken by an algorithm to run the program completely. It is the runtime of the program. The time complexity of an algorithm depends upon the input size. The time complexity is commonly represented by using big O notation. For example, the time complexity of a linear search is O (n).

Space Complexity–The space complexity of an algorithm is the amount of memory space required to run the program completely. The space complexity of an algorithm depends upon the input size.

Time Complexity is categorized into three types:

1.Best Case Running Time–The performance of the algorithm is best under optimal conditions. For example, the best case for a binary search occurs when the desired element is the middle element of the list. Another example is that of sorting; that is, if the elements are already sorted in a list, then the algorithm will execute in the best time.

2.Average Case Running Time–This denotes the behavior of an algorithm when the input is randomly drawn from a given collection or distribution. It is an estimate of the running time for “average” input. It is usually assumed that all inputs of a given size are likely to occur with equal probability.

3.Worst Case Running Time–The behavior of the algorithm during the worst possible case of the input instance. The worst case running time of an algorithm is an upper bound on the running time for any input. For example, the worst case for a linear search occurs when the desired element is the last element in the list or the element does not exist in the list.

Frequently Asked Questions

6.Define time complexity.

Answer:

Time complexity is a measure that evaluates the count of the operations performed by a given algorithm as a function of the size of the input. It is the approximation of the number of steps necessary to execute an algorithm. It is commonly represented with asymptotic notation, that is, the O(g) notation, also known as big O notation, where g is the function of the size of the input data.

1.6.1Time-Space Trade-Off

In computer science, the time-space trade-off is a way of solving a particular problem either in less time and more memory space or in more time and less memory space. But if we talk in practical terms, designing such an algorithm in which we can save both space and time is a challenging task. So, we can use more than one algorithm to solve a problem. One may require less time, and the other may require less memory space to execute. Therefore, we sacrifice one thing for the other. Hence, there exists a time-space or time-memory trade-off between algorithms. The time-space trade-off gives the programmer a rational choice from an informed point of view. If time is a big concern for a programmer, then she might choose a program that takes less or the minimum time to execute. If space is a prime concern for a programmer, then, she might choose a program that takes less memory space to execute at the cost of more time.

1.7ABSTRACT DATA TYPES

An Abstract Data Type (ADT) is a popular mathematical model of data objects that defines a data type along with various functions that operate on these objects. To understand the meaning of an abstract data type, we can break the term into two parts, that is, “data type” and “abstract.” The data type of a variable is a collection of values that a variable can take. There are various data types in Python (such as integer, float, character, long, and double). When we talk about the term “abstract” in the context of data structures, it means “apart from detailed specifications.” It can be considered as a description of the data in a structure with a list of operations to be executed on the data within the structure. Thus, an abstract data type is the specification of a data type that specifies the mathematical and logical model of the data type. For example, when we use stacks and queues, our prime concern is only with the data type and the operations to be performed on those structures. We are not worried about how the data will be stored in the memory. Also, we don’t bother about how the push () and pop () operations work. We just know that we have two functions available to us, so we have to use them for insertion and deletion operations.

1.8BIG O NOTATION

1.9SUMMARY

•A data structure determines a way of storing and organizing the data elements in a computer’s memory. Data means a value or a collection of values. Structure refers to a way of organizing the data. The mathematical or logical representation of data in the memory is referred to as a data structure.

•Data structures are classified into various types, which include linear and non-linear data structures, primitive and non-primitive data structures, static and dynamic data structures, and homogeneous and non-homogeneous data structures.

•A linear data structure is one in which the data elements are stored in a linear or sequential order; that is, data is stored in consecutive memory locations. A non-linear data structure is one in which the data is not stored in any sequential order or consecutive memory locations.

•A static data structure is a collection of data in memory that is fixed in size and cannot be changed during runtime. A dynamic data structure is a collection of data in which memory can be reallocated during the execution of a program.

•Primitive data structures are fundamental data structures or predefined data structures that are supported by a programming language. Non-primitive data structures are comparatively more complicated data structures that are created using primitive data structures.

•A homogeneous data structure is one that contains all data elements of the same type. A non-homogeneous data structure contains data elements of different types.

•Python’s list structure is a mutable sequence container that can change size as items are added or removed. It is an abstract data type that is implemented using an array structure to store the items contained in the list.

•A queue is a linear collection of data elements in which the element inserted first will be the element taken out first, that is, it is a FIFO data structure. A queue is a linear data structure in which the first element is inserted from one end, called the REAR end, and the deletion of the element takes place from the other end, called the FRONT end.

•A linked list is a sequence of nodes in which each node contains one or more than one data field and an address field that stores the address of the next node.

•A stack is a linear collection of data elements in which insertion and deletion take place only at one end, called the TOP of the stack. A stack is a Last-In-First-Out (LIFO) data structure because the last element added to the top of the stack will be the first element to be deleted from the top of the stack.

•A tree is a non-linear data structure in which the data elements or the nodes are represented in a hierarchical order. Here, an initial node is designated as the root node of the tree, and the remaining nodes are partitioned into two disjointed sets such that each set is a part of a sub-tree.

•A binary tree is the simplest form of a tree. A binary tree consists of a root node and two sub-trees known as the left sub-tree and right sub-tree, where both the sub-trees are also binary trees.

•A graph is a general tree with no parent-child relationship. It is a non-linear data structure that consists of vertices or nodes and the edges that connect those vertices.

•An algorithm is a systematic set of instructions combined to solve a complex problem. It is a step-by-finite-step sequence of instructions, each of which has a clear meaning and can be executed with a minimum amount of effort in a finite amount of time.

•The process of dividing an algorithm into modules is called modularization.

•The time complexity of an algorithm is described as the amount of time taken by an algorithm to run the program completely. It is the runtime of the program.

•The space complexity of an algorithm is the amount of memory space required to run the program completely.

•An ADT (Abstract Data Type) is a mathematical model of the data objects that defines a data type as well as the functions to operate on these objects.

•Big O notation is a popular analysis characterization scheme that provides an upper bound on the complexity of an algorithm.

1.10EXERCISES

Q1.What is a “good” program?

Q2.Explain the classification of data structures.

Q3.What is an algorithm? Discuss the characteristics of an algorithm.

Q4.What are the various operations that can be performed on the data structures? Explain each of them with an example.

Q5.Differentiate a list from a linked list.

Q6.Explain the terms time complexity and space complexity.

Q7.Write a short note on graphs.

Q8.What is the process of modularization?

Q9.Differentiate between stacks and queues with examples.

Q10.What is meant by Abstract Data Type (ADT)? Explain in detail.

Q11.Discuss the worst-case, best-case, and average-case time complexity of an algorithm.

Q12.Write a brief note on trees.

Q13.Explain how you can develop an algorithm to solve a complex problem.

Q14.Explain the time-memory trade-off in detail.

1.11MULTIPLE CHOICE QUESTIONS

Q1.Which of the following data structures is a FIFO data structure?

a.List

b.Stacks

c.Queues

d.Linked List

Q2.How many maximum children can a binary tree have?

a.0

b.2

c.1

d.3

Q3.Which of the following data structures uses dynamic memory allocation?

a.Graphs

b.Linked Lists

c.Trees

d.All of these

Q4.In a queue, deletion is always done from the _____________

a.Front end

b.Rear end

c.Middle

d.None of these

Q5.Which data structure is used to represent complex relationships between the nodes?

a.Linked Lists

b.Trees

c.Stacks

d.Graphs

Q6.Which of the following is an example of a heterogeneous data structure?

a.List

b.Structure

c.Linked list

d.None of these

Q7.In a stack, insertion and deletion takes place from the _____________

a.Bottom

b.Middle

c.Top

d.All of these

Q8.Which of the following is not part of the Abstract Data Type (ADT) description?

a.Operations

b.Data

c.Both (a) and (b)

d.None of the above

Q9.Which of the following data structures allows deletion at both ends of the list but insertion at one end only?

a.Stack

b.Input Restricted Dequeue

c.Output Restricted Dequeue

d.Priority Queue

Q10.Which of the following data structures is a linear type?

a.Trees

b.Graphs

c.Queues

d.None of the above

Q11.Which one of the following is beneficial when the data is stored and has to be retrieved in reverse order?

a.Stack

b.Linked List

c.Queue

d.All of the above

Q12.A binary search tree whose left and right sub-tree differ in height by 1 at most is a _____________

a.Red Black Tree

b.M way search tree

c.AVL Tree

d.None of the above

Q13.The operation of processing each element in the list is called __________

a.Traversal

b.Merging

c.Inserting

d.Sorting

Q14.Which of the following are the two primary measures of the efficiency of an algorithm?

a.Data & Time

b.Data & Space

c.Time & Space

d.Time & Complexity

Q15.Which one of the following cases does not exist/occur in complexity theory?

a.Average Case

b.Worst Case

c.Best Case

d.Minimal Case

CHAPTER 2

INTRODUCTION TO PYTHON

2.1INTRODUCTION

What is Python?

Python is a popular programming language. It was created by Guido van Rossum and released in 1991.

It is used for:

•web development (server-side)

•software development

•mathematics

•system scripting

What can Python do?

•Python can be used on a server to create web applications.

•Python can be used alongside software to create workflows.

•Python can connect to database systems. It can also read and modify files.

•Python can be used to handle big data and perform complex mathematics.

•