Unit 1 DS.pptx

Basics Concepts: Data, Data objects, Data types, Data structure, Abstract Data Types (ADT), Primitive and non primitive, linear and nonlinear, static and dynamic, persistent and ephemeral data structures Algorithms: Introduction, Characteristics, Analysis of algorithms Complexity of algorithms- Space complexity, Time complexity, Big O notation Sequential Organization: Concept, Array as an abstract data type, Memory representation and address calculation, Inserting and deleting an element, Sorting: stability in sorting, internal Sorting methods, Quick sort, merge sort, shell sort, radix sort, concept of external sorting SYLLABUS.

INTRODUCTION.

Computer : A programmable device that can store, retrieve, and process data.(Combination of H/w & S/w ) Hardware : things which we can touch. Software : things which we cannt touch.(Can only see) Data : Raw facts, figures or values (like numbers, text, images) fed into a computer Information : Processed data that’s meaningful and useful Introduction.

Data type : The specification of how information is represented in the computer as data and the set of operations that can be applied to it. (type of value a variable can hold) Computer program : A set of instructions that a computer follows to perform a task Programming Language : A language used to write those instructions. Introduction.

DATA STRUCTURE.

DATA STRUCTURE Data Structure is a way to store and organize data so that it can be used efficiently. Data Object : “Data object is a region of storage that contains a value or group of values”.

NEED OF DATA STRUCTURE 1. Stores huge data 2. Stores data in systematic way 3. Retains logical relationship 4. Provides various structure 5. Static and dynamic formats 6. Better algorithms.

NEED OF DATA STRUCTURE 1. Stores huge data- • Data structures must be capable of holding and organizing large amounts of data efficiently. • As data increases, the data structure should handle it efficiently without performance problems.

NEED OF DATA STRUCTURE 2. Stores data in systematic way • A data structure organizes data in a specific manner that allows efficient access, modification, and deletion. • Without an organized approach, searching for or manipulating data would be inefficient. • This systematic organization enables better performance and reliability in managing data..

NEED OF DATA STRUCTURE 3. Retains logical relationship • Data in a data structure should maintain logical relationships between elements. • For example, in a tree structure, parent-child relationships exist between nodes. • This ensures the data is not just a collection of individual elements but rather interconnected in a meaningful way. • This also facilitates operations such as searching, updating, and traversing the data.

NEED OF DATA STRUCTURE 4. Provides various structure • Different types of data require different types of organization. • Data structures offer various ways to store and organize data based on the needs of the application. • For example: Arrays and linked lists are simple linear data structures. Trees and graphs represent hierarchical and network-like relationships. • Hash tables provide fast lookups. • Stacks and queues manage elements in a specific order (LIFO or FIFO)..

NEED OF DATA STRUCTURE 5. Static and dynamic formats Some data structures have a fixed size (static), like arrays, where the size is defined at the time of creation. Others are dynamic, such as linked lists, where the size can grow or shrink during runtime based on the data being inserted or deleted. This flexibility is important to accommodate the changing needs of applications as data size fluctuates..

NEED OF DATA STRUCTURE 6. Better algorithms Data structures often come with algorithms designed for efficient manipulation of the stored data. These algorithms can include search, insert, delete, update, and traversal operations, which need to be optimized for performance..

ABSTRACT DATA TYPE ADT : • An ADT is a mathematical model or concept used to define a type of data and the operations that can be performed on that data, independent of any implementation. • In other words, an ADT specifies what a data structure can do (its behavior), without saying how it is done (the implementation details). • Abstract data types, or ADTs, are typically used in algorithms.”.

ABSTRACT DATA TYPE ADT : For example, consider a Stack: •What it does: You can push elements onto it, pop elements from it, and check the top element. •How it's done: The implementation can vary. It might be implemented using an array or a linked list, but this is not part of the ADT. The ADT only defines the behavior (the operations), not how they are implemented..

ABSTRACT DATA TYPE Another definition of ADT is ADT is set of D, F and A. D – domain = Data object, This represents the set of possible data that the ADT will operate on. F – function = These are the set of operations that can be performed on the data in the ADT. For a stack, the operations could include: push(x) – Add item x to the stack, pop()Remove the top item from the stack. A – axioms = These are the rules or properties that the operations must follow. They define how the operations b h ith t t th d t.

TYPES OF DATA STRUCTURE There are two types : 1. Primitive data structure: predefined way of storing data by the system 2. Non-primitive data structure: derived from primary data types.

TYPES OF DATA STRUCTURE 1. Primitives data structure : “Primitive data structures are thosewhich are predefined way of storing data by the system. ” e.g. int, char, float etc 2. Non-primitive data structure : “The data types that are derived from primary data types are known as non-Primitive data types. These datatype are used to store group of values.” e.g. struct, array, linklist, stack, tree , graph etc..

Linear and Non-Linear Data Structure 1. Linear Data Structure : “Linear data structure traverses the data elements sequentially, in which only one data element can directly be reached”. Linear Data Structures are like a line where you access elements in order (one after another). Ex: Arrays, Linked Lists, stack, queue. 2. Non-Linear Data Structure: “Every data item is attached to several other data items in a way that is specific for reflecting relationships.” Non-Linear Data Structures are like a tree or a web, where elements have more complex connections, and you might access them in various orders. Ex: Graph , Tree.

Linear vs Non-Linear Data Structure.

Static and Dynamic Data Structure 1. Static data strucure : “A static datastructureis anorganizationor collection of data in memory that is fixed in size.” Ex: Arrays 2. Dynamic Data Strucute : “ In Dynamic data structure the size of the structure in not fixed and can be modified during the operations performed on it” Ex: Linked list.

Persistent and Ephemeral Data Structure 1. Persistent data strucure : “A persistent data structure is a data structure that always preserves the previous version of itself when it is modified..” Ex: Linked list, tree 2. Ephemeral Data Strucute : “ An ephemeral data structure is one of which only one version is available at a time(it does not preserve previous version).” Ex: RAM , Cache memory.

Persistent and Ephemeral Data Structure 1. Persistent data strucure : “A persistent data structure is a data structure that always preserves the previous version of itself when it is modified..” Ex: Linked list, tree.

Relationship among Data,Data Structure and Algorithms Data is considered as set of facts and figures or data is value of group of value which is in particular format. Data structure is method of gathering as well as organizing data in such manner that several operation can be performed Problem is definedas a situation or condition which needto solve to achieve the goals Algorithm is set of ordered instruction which are written in simple english language..

SORTING.

❖ “Sorting is the process ordering a list of element in either ascending or descending order.” ❖ Sorting is the operation of arranging the records of a table according to the key value of each record, or it can be defined as the process of converting an unordered set of elements to an ordered set of elements ❖ Sorting is a process of organizing data in a certain order to help retrieve it more efficiently 35 SORTING.

❖ Any sort algorithm that uses main memory exclusively during the sorting is called as internal sort algorithm ❖ Internal sorting is faster than externalsorting 36 INTERNAL SORTING(types) Internal Sorting •Definition: Sorting is performed entirely within the main memory (RAM) of a computer. •Data Size: Typically used when the dataset is small enough to fit into the main memory. •Speed: Faster since accessing data in RAM is quicker than accessing external storage. •Examples of Algorithms: Quick Sort, Merge Sort, Bubble Sort, Heap Sort. •Applications: Useful for small-to-medium-sized datasets or when sufficient RAM is available..

❖ Any sort algorithm that uses main memory exclusively during the sorting is called as internal sort algorithm ❖ Internal sorting is faster than externalsorting Internal Sorting techniques : 1. Bubble sort 2. Selection sort 3. Insertion sort 4. Quick sort 5. Shell sort 6. Heap sort 7. Radix sort 8. Bucket sort 36 INTERNAL SORTING(types).

❖ Any sort algorithm that uses external memory, such as tape or disk, during the sorting is called as external sort algorithm ❖ Merge sort is used in external sorting EXTERNAL SORTING 29 Definition: Sorting involves the use of external storage (e.g., hard drives) because the dataset is too large to fit into the main memory. Data Size: Designed for very large datasets that exceed the capacity of the main memory. Speed: Slower due to the overhead of reading from and writing to external storage. Applications: Used for tasks like database sorting, processing logs, or handling massive datasets..

❖ A sorting method is said to be stable if at the end of the method, identical elements occur in the same relative order as in the original unsorted set 1. EXAMPLE : STABILITY OF SORTING 30.

relativ e ❖ Sort efficiencyis a measure of the efficiency of a sort ❖ It is usually an estimate of the number of comparisons and data movement required to sort the data SORT EFFICIENCY 31 Why is Stability Important? Stability is especially useful when the data has additional attributes besides the value being sorted. For example: •If you are sorting a list of employees by their salary (and two employees have the same salary), their order based on their names or IDs will remain unchanged in a stable sort..

❖ During the sorted process, the data is traversed many times ❖ Each traversal of the data is referred to as a sort pass ❖ In addition,the characteristicofa sort passis the placement of one or more elements in a sorted list PASSES IN SORTING 32.

Quick Sort Algorithm � Quicksort is based on divide-and-conquer strategy � Quick sort is thus in-place, divide-and-conquer based massively recursive sort technique � This technique reduces unnecessary swaps and moves the element at great distance in one move.

Quick Sort Algorithm ❖ The recursive algorithm consists of four steps: ❖ If there is one or less element in the array to be sorted, return immediately ❖ Pick an element inthe array toserve asa ‘pivot’ (usually the left-most element in the list) ❖ Partition the array into two parts—one with elements smaller thanthe pivot and the other with elements larger than the pivot by traversing from both the ends and performing swaps if needed ❖ Recursively repeat the algorithm for bothpartitions.

Quick Sort Algorithm.

Quick Sort Algorithm partition(A, lb, ub) swap(A[lb], A[q]); return q; } Quicksort(A, lb, ub) }.

Quick Sort Algorithm.

Quick Sort Algorithm.

Quick Sort Algorithm.

Quick Sort Algorithm.

ALGORITHM Introduction, Characteristics, Analysis of algorithms Complexity of algorithms- Space complexity, Time complexity, Big O notation.

ALGORITHM –PROBLEM SOLVING COMPUTER : “Computer is multi purpose Electronic Machine which is used for storing , organizing and processing data by set of program Problem : “Problem is defined as situation or condition which needs to solve to achive goal” Steps in Problem Solving : 1. Define the problem 2. Data gathering 3. Decide effective solution 4. Implement and evaluate the solution 5. Review the result..

PROBLEM SOLVING TECHNIQUES There are two types : 1. Algorithmic 2. Flowchart Algorithms is set of instructions which are writeen in simple english language. Flowchart is graphical representation of the algorithms..

Some other Problem Solving Techniques 1. Trial and error techniques 2. Divide and conquer techniques 3. Merging solution 4. The building block approach 5. Brain storming techniques.

INTRODUCTION OF ALGORITHMS DEFINITION : “An algorithm is defined as a step-by-step procedure or method for solving a problem by a computer in a finite number of steps.” From the data structure point of view, following are some important categories of algorithms − Search − Algorithm to search an item in a data structure. Sort − Algorithm to sort items in a certain order. Insert − Algorithm to insert item in a data structure. Update − Algorithm to update an existing item in a data structure. Delete − Algorithm to delete an existing item from a data structure..

CHARACTRISTICS OF ALGORITHM 1. Unambiguous − Algorithm should be clear and unambiguous. Each of its steps (or phases), and their inputs/outputs should be clear and must lead to only one meaning. 2. Input − An algorithm should have 0 or more well-defined inputs. 3. Output − An algorithm should have 1 or more well-defined outputs, and should match the desired output. 4. Finiteness − Algorithms must terminate after a finite number of steps. 5. Feasibility − Should be feasible with the available resources. 6. Independent − An algorithm should have step-by-step directions, which should be independent of any programming code..

EXAMPLE OF ALGORITHM Example Let's try to learn algorithm-writing by using an example. Problem − Design an algorithm to add two numbers and display the result. Step 1 − START Step 2 − declare three integers a, b & c Step 3 − define values of a & b Step 4 − add values of a & b Step 5 − store output of step 4 to c Step 6 − print c.

ALGORITHM DESIGN TOOL • There can be two tools : 1. Flowchart 2. Pseudo Code Flowchart : “ Flowchart is graphical representation of the algorithms” Pseudo Code : “It is simply an implementation of an algorithm in the form of annotations and informative text written in plain English. Prof. Anand Gharu.

FLOWCHAR T Symbol used inFlowchart :.

Name Start or Stop Process Decision Input or Output Connector Direction of flow Symbol Start/ Stop Process Decision Input/Output Usage The beginning and end points in the sequence. An instruction or a command. A decision, either yes or no. An input is data received by a computer. An output is a signal or data sent from a computer. A jump from one point in the sequence to another. Connects the symbols. The arrow shows the direction of flow of instructions-.