DSA Ch1(Introduction) [Recovered].pptx

### Introduction to Data Structures and Algorithms (DSA)

**Data Structures and Algorithms (DSA)** form the backbone of computer science and software engineering, providing essential tools and techniques for organizing, processing, and storing data efficiently and effectively. Understanding DSA is crucial for solving complex computational problems and optimizing software performance.

#### **1. Data Structures**

A **data structure** is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. Different data structures are designed to handle different kinds of data manipulation tasks, making them suitable for various applications. Some of the most common data structures include:

- **Arrays**: A collection of elements identified by index or key. Arrays are used when the number of elements is known and remains constant over time.
- **Linked Lists**: A linear collection of elements, called nodes, where each node points to the next one. They are useful for dynamic data where the number of elements can change.
- **Stacks**: A Last In, First Out (LIFO) data structure where the most recently added element is the first to be removed. Used in recursive algorithms and backtracking.
- **Queues**: A First In, First Out (FIFO) data structure where the oldest added element is the first to be removed. Commonly used in scheduling and buffering.
- **Trees**: Hierarchical data structures with nodes connected by edges. Trees are used to represent hierarchical relationships and are the basis for many efficient search and sorting algorithms.
- **Graphs**: Collections of nodes (or vertices) and edges connecting some or all of them. Graphs are used to model relationships between pairs of objects.
- **Hash Tables**: A structure that maps keys to values for highly efficient lookup operations. Widely used in database indexing and caching.

#### **2. Algorithms**

An **algorithm** is a finite set of well-defined instructions to solve a particular problem or perform a specific task. Algorithms are evaluated based on their correctness, efficiency (time and space complexity), and simplicity. Key categories of algorithms include:

- **Sorting Algorithms**: Arrange data in a specific order, such as Quick Sort, Merge Sort, and Bubble Sort.
- **Searching Algorithms**: Locate specific data within a structure, such as Binary Search and Depth-First Search.
- **Dynamic Programming**: Solve complex problems by breaking them down into simpler subproblems, storing results to avoid redundant work (e.g., Fibonacci sequence, Knapsack problem).
- **Greedy Algorithms**: Make the locally optimal choice at each step with the hope of finding a global optimum (e.g., Dijkstra’s algorithm for shortest path).
- **Divide and Conquer**: Divide a problem into subproblems, solve them independently, and combine their results (e.g., Merge Sort, Quick Sort).
- **Backtracking**: Explore all possible solutions to a problem by building solutions incre

1. Data Structure & Algorithms Chapter 1 Introduction & Overview

2. 2 Course Outline: Introduction to Data Structures and Algorithms; Complexity Analysis; Arrays; Sorting Algorithms: Insertion Sort, Selection Sort, Bubble Sort, Shell Sort, Heap Sort, Quick Sort, Merge Sort, Radix Sort, Bucket Sort; Linked Lists: Singly Linked Lists, Doubly Linked Lists, Circular List; Stacks, Queues, and Priority Queue; Recursion: Function call and Recursion Implementation, Tail Recursion, Non-tail Recursion, Indirect Recursion, Nested Recursion, Backtracking. Trees: Binary Trees, Binary Heap, Binary Search Tree Traversal, Insertion, Deletion, and Balancing a Tree; Heap; B-Tree; Spanning Tree, Splay Trees; Graphs: Representation, Traversal, Shortest Path, and cycle Detection; Isomorphic Graphs; Graph Traversal Algorithms; Hashing; Memory Management and Garbage Collection.

3. References Data Structures by Seymour , SCHAUM’S Series. Data Structures with C++, SCHAUM’S Series. 3

4. Contents 1.1 Basic Terminology 1.2 Data Structures 1.3 Data Structure Operations 4

5. Introduction Contents of this course will repeat again & again in every semester like C/C++. Foundation course. You have already seen basic data structures in C/C++ but focus was on programming. Int Char Float etc… Data have importance in Computer Science that’s why Organization & Arrangement of data have great importance. 5

6. Why DS? DS organize data. More powerful computers. Complex problem can be solved. Saving of resources. Space Time 6

7. Organizing Data Any organization for a collection of records that can be searched, processed or modified. The choice of data structure and algorithm can make the difference between a program running in a few seconds or many days. Ex: Array vs Variable 7

8. 1.1 Basic Terminology Data : Data are simply collection of facts and figures. Data are values or set of values. Data item : A data item refers to a single unit of values. Data items that are divided into sub items are group items ; those that are not are called elementary items . For example, a student’s name may be divided into three sub items – [first name, middle name and last name] but the ID of a student would normally be treated as a single item. 8

9. 1.1 Basic Terminology 9 In the above example ( ID, Age, Gender, First, Middle, Last, Street, Area ) are elementary data items, whereas (Name, Address ) are group data

10. 1.1 Basic Terminology An entity (here entity means table) is something that has certain attributes or properties which may be assigned values. The values themselves may be either numeric or non-numeric. Attributes : Values : 10 Name Age Gender Roll # Std1 20 M 123 Std2 19 F 122

11. 1.1 Basic Terminology The term “ information ” is sometimes used for data with given attributes or in other words meaningful or processed data. A field is a single elementary unit of information representing an attribute of an entity. A record is the collection of field values of a given entity. Records may also be classified according to length. Fixed length records (Name, F.Name , Age) Variable length records (Name, Address, Experience ) A file is the collection of records of the entities in a given entity set. 11

12. 1.2 Data Structure The logical or mathematical model of a particular organization of data is called a data structure. In computer science, a data structure is a particular way of storing and organizing data in a computer’s memory so that it can be used efficiently. Data may be organized in many different ways. The choice of a particular data model depends on the two considerations first: It must be rich. Should be simple enough that one can effectively process the data whenever necessary. 12

13. 1.2 Data Structure 13 Primitive Data Structure Data Structure Non-primitive Data Structure Integer Character Boolean Float Linear Data Structure Non-Linear Data Structure Graph Tree Arrays Linked List Queue Stack Classification of Data Structure:

14. 1.2 Data Structure The non-primitive data structure can be classified in two major types: 1. Linear Data Structure 2. Non-linear Data Structure 14

15. 1.2 Data Structure Linear Data Structure: A data structure is said to be linear if its elements form any sequence. The common examples of linear data structure are Arrays Linked lists Queues Stacks 15

16. 1.2 Data Structure Non-linear Data Structure: This structure is mainly used to represent data containing a hierarchical relationship between elements. The common examples of non-linear data structure are: Tree Graph 16

17. 1.2 Data Structure Arrays: The simplest type of data structure is a linear (or one dimensional) array. A list of a finite number n of similar data referenced respectively by a set of n consecutive numbers, usually 1, 2, 3 . . . . . . . n. Example: A linear array A[8] consisting of numbers is pictured in following figure. 17

18. 1.2 Data Structure Linked List: A linked list or one way list is a linear collection of data elements called nodes. Where the linear order is given by means of pointers. Each node is divided into two parts: The first part contains the information of the node The second part contains the address of the next node (link /next pointer field) in the list. 18

19. 1.2 Data Structure Queue: Also called FIFO (first in first out) system Linear list in which deletions can take place only at one end of the list, the Front of the list and insertion can take place only at the other end Rear . 19 Front Rear

20. 1.2 Data Structure Stack: Also called LIFO: Last In, First Out system. Linear list in which insertion and deletion take place only at one end called top . The most recently added items are at the top of the stack. The last element to be added is the first to be removed 20

21. 1.2 Data Structure Tree: Data frequently contain a hierarchical relationship between various elements. The data structure which reflects this relationship is called a rooted tree graph or simply a tree. 21

22. 1.2 Data Structure Graph: Data sometimes contains a relationship between pairs of elements which is not necessarily hierarchical in nature. e.g. an airline flights only between the cities connected by lines. This data structure is called Graph. 22

23. Assignments Real applications of stack, queue, linked list, tree, graph in computer system. 23

24. 1.3 Need of DSA Data Structures and Algorithms (DSA) are used in virtually every software system, from operating systems to web applications: For managing large amounts of data, such as in a social network or a search engine. For scheduling tasks, to decide which task a computer should do first. For planning routes, like in a GPS system to find the shortest path from A to B. For optimizing processes, such as arranging tasks so they can be completed as quickly as possible. For solving complex problems: From finding the best way to pack a truck to making a computer 'learn' from data. 24

25. 1.3 Need of DSA DSA is fundamental in nearly every part of the software world: Operating Systems Database Systems Web Applications Machine Learning Video Games Cryptographic Systems Data Analysis Search Engines 25

26. 1.4 Data Structure Operations The data appearing in our data structures are processed by means of certain operations. In fact, the particular data structure that one chooses for a given situation depends largely in the frequency with which specific operations are performed. 26

27. 1.4 Data Structure Operations The following four operations play a major role: Traversing : Accessing each record/node exactly once so that certain items in the record may be processed. (This accessing and processing is sometimes called “visiting” the record.) Searching : Finding the location of the desired node with a given key value, or finding the locations of all such nodes which satisfy one or more conditions. Inserting : Adding a new node/record to the structure. Deleting : Removing a node/record from the structure. 27

28. 1.4 Data Structure Operations Sometimes, two or more of the operations may be used in a given situation. For e.g , we may want to delete a data element from a data structure, which may mean we first need to search for the location of the record. The following two operations, which are used in special situations, will also be considered : Sorting : Sorting is the process of arranging all data items in a data structure in a particular order say for example, either in ascending order or in descending order. Merging : Combining the records of two different sorted files into a single sorted file. 28

29. 1.4 Data Structure Operations EXAMPLES & REAL LIFE APPLICATIONS A company contains employee file in which each record contain the following data for a given employee : Name, Address, Telephone number, Employee age, gender, employ number. 29

30. 1.4 Data Structure Operations Suppose the company wants to announce a meeting through a mailing. Then one would traverse the file to obtain employee name and address for each member. Suppose one wants to obtain address for the given employee name. Then one would search the file for the record containing employee name. Suppose a new person joins the company. Then one would insert his or her record into the file. Suppose an employee dies. Then one would delete his or her record from the file. Suppose an employee has moved and has a new address and telephone number. Given the name of the member, one would first need to search for the record in the file. Then one would perform the “update”- i ..e., change items in the record with the new data. 30