Introduction-to-Data-Structure-and-Algorithm.pptx

study hard and study fuck

1. Introduction to Data Structure and Algorithm Republic of the Philippines UNIVERSITY OF EASTERN PHILIPPINES Department of Information Technology Catarman , Northern Samar, Philippines Mar Riel C. Abuke I.T Instructor

2. What are Data Structure? Data structure is a storage that is used to store and organize data . It is a way of arranging data on a computer so that it can be accessed and updated efficiently. Depending on your requirement and project, it is important to choose the right data structure for your project. For example, if you want to store data sequentially in the memory, then you can go for the Array data structure . Note: Data structure and data types are slightly different. Data structure is the collection of data types arranged in a specific order. 2

3. Types of Data Structure 3

4. Two Main Types of Data Structure Primitive Data Structure and Non-Primitive Data Structure Primitive Data Structure – These are predefined data, which are supported by the programming language , Primitive data structure is the data structure that allows you to store only single data type values. Built-in Data Structure String = “this is string” Integer = 10 Float = 34.1 4

5. Two Main Types of Data Structure Non-Primitive Data Structure - is a data structure that allows you to store multiple data type values. These are data structures that are not defined by the programming language. These are created by the programmer User defined data structure Two Types Linear List Non-Linear List 5

6. Two Main Types of Non-Primitive Data Structure Linear List – the elements are arranged in sequence one after the other. Since elements are arranged in particular order, they are easy to implement . However, when the complexity of the program increases , the linear data structures might not be the best choice because of operational complexities . Non-Linear List - Unlike linear data structures, elements in non-linear data structures are not in any sequence . Instead they are arranged in a hierarchical manner where one element will be connected to one or more elements. 6

7. Two Main Types of Non-Primitive Data Structure Linear List – The data items are arranged in a linear sequence either Vertically or Horizontally . Kinds of Linear List Array Stack Queue Linked List 7

8. Popular Linear Data Structures 1. Array Data Structure In an array, elements in memory are arranged in continuous memory . All the elements of an array are of the same type. And, the type of elements that can be stored in the form of arrays is determined by the programming language. An array with each element represented by an index 8

9. C# Array 1. Array Data Structure In C#, here is how we can declare an array. datatype[] arrayName ; Here, dataType - data type like int , string, char, etc arrayName - it is an identifier Let's see an example, int [] age ; Here, we have created an array named age. It can store elements of int type . 9

10. C# Array But how many elements can it store? To define the number of elements that an array can hold, we have to allocate memory for the array in C#. For example, Here, new int [5] represents that the array can store 5 elements. We can also say the size/length of the array is 5. Note: We can also declare and allocate the memory of an array in a single line. For example, int [] age = new int [5]; 10

11. C# Array In an array, we use an index number to determine the position of each array element. We can use the index number to initialize an array in C#. For example, Note: An array index always starts at 0. That is, the first element of an array is at index 0. If the size of an array is 5, the index of the last element will be at 4 (5 - 1). 11

12. Access Array Elements We can access the elements in the array using the index of the array. For example, Output: 12

13. Popular Linear Data Structures 2. Stack Data Structure In stack data structure, elements are stored in the LIFO principle. That is, the last element stored in a stack will be removed first. It works just like a pile of plates where the last plate kept on the pile will be removed first. In a stack, operations can be perform only from one end (top here). 13

14. Popular Linear Data Structures 3. Queue Data Structure Unlike stack, the queue data structure works in the FIFO principle where first element stored in the queue will be removed first. It works just like a queue of people in the ticket counter where first person on the queue will get the ticket first. In a queue, addition and removal are performed from separate ends. 14

15. Popular Linear Data Structures 4. Linked List Data Structure In linked list data structure, data elements are connected through a series of nodes. And, each node contains the data items and address to the next node. 15

16. Two Main Types of Non-Primitive Data Structure Non-Linear List – The data items are not in sequence. Kinds of Non-Linear List Tree Graph 16

17. Non Linear Data Structures 1. Graph Data Structure In graph data structure, each node is called vertex and each vertex is connected to other vertices through edges. Popular Graph Based Data Structures: Spanning Tree and Minimum Spanning Tree Strongly Connected Components Adjacency Matrix Adjacency List 17

18. Non Linear Data Structures 2. Trees Data Structure Similar to a graph, a tree is also a collection of vertices and edges. However, in tree data structure, there can only be one edge between two vertices. Popular Tree based Data Structure Binary Tree Binary Search Tree AVL Tree B-Tree B+ Tree Red-Black Tree 18

19. Data Structure Hierarchy 19

20. Linear Vs Non-linear Data Structures Now that we know about linear and non-linear data structures, let's see the major differences between them. 20 Linear Data Structures The data items are arranged in sequential order, one after the other. All the items are present on the single layer. It can be traversed on a single run. That is, if we start from the first element, we can traverse all the elements sequentially in a single pass. Non Linear Data Structures The data items are arranged in non-sequential order (hierarchical manner). The data items are present at different layers. It requires multiple runs. That is, if we start from the first element it might not be possible to traverse all the elements in a single pass.

21. Linear Vs Non-linear Data Structures Now that we know about linear and non-linear data structures, let's see the major differences between them. 21 Linear Data Structures The memory utilization is not efficient. The time complexity increase with the data size. Example: Arrays, Stack, Queue Non Linear Data Structures Different structures utilize memory in different efficient ways depending on the need. Time complexity remains the same. Example: Tree, Graph, Map

22. What is an Algorithm? In computer programming terms, an algorithm is a set of well-defined instructions to solve a particular problem. It takes a set of input(s) and produces the desired output. For example An algorithm to add two numbers: Take two number inputs Add numbers using the + operator Display the result 22

23. Characteristics of an Algorithm? Input – Zero (0) to more Output – At least one (1) Definiteness – Instructions must be clear and realistic Finiteness – Must terminate and must have a stopping point Effectiveness – Instructions must be efficient and useful 23

24. Qualities of a Good Algorithm Input and output should be defined precisely. Each step in the algorithm should be clear and unambiguous. Algorithms should be most effective among many different ways to solve a problem. An algorithm shouldn't include computer code. Instead, the algorithm should be written in such a way that it can be used in different programming languages. 24

25. Algorithm Examples: Algorithm 1: Add two numbers entered by the user 25

26. Algorithm Examples: Algorithm 2: Find the largest number among three numbers 26

27. Algorithm Examples: Algorithm 5: Check whether a number is prime or not 27

28. 28 Algorithm : Systematic logical approach which is a well-defined, step-by-step procedure that allows a computer to solve a problem. Pseudocode : It is a simpler version of a programming code in plain English which uses short phrases to write code for a program before it is implemented in a specific programming language. Program : It is exact code written for problem following all the rules of the programming language . Difference between Algorithm, Pseudocode and Program

29. 29 Algorithm: An algorithm is used to provide a solution to a particular problem in form of well-defined steps. Whenever you use a computer to solve a particular problem, the steps which lead to the solution should be properly communicated to the computer. While executing an algorithm on a computer, several operations such as additions and subtractions are combined to perform more complex mathematical operations. Algorithms can be expressed using natural language, flowcharts, etc . Difference between Algorithm, Pseudocode and Program

30. 30 Algorithm: Let’s take a look at an example for a better understanding. As a programmer, we are all aware of the Linear Search program. (Linear Search) Algorithm of linear search : Here, we can see how the steps of a linear search program are explained in a simple, English language. Difference between Algorithm, Pseudocode and Program

31. 31 Pseudocode: It is one of the methods which can be used to represent an algorithm for a program. It does not have a specific syntax like any of the programming languages and thus cannot be executed on a computer . There are several formats which are used to write pseudo-codes and most of them take down the structures from languages such as C, Lisp, FORTRAN, etc. Many time algorithms are presented using pseudocode since they can be read and understood by programmers who are familiar with different programming languages. Pseudocode allows you to include several control structures such as While, If-then-else, Repeat-until, for and case, which is present in many high-level languages. Note: Pseudocode is not an actual programming language. Difference between Algorithm, Pseudocode and Program

32. 32 Pseudocode: Pseudocode for Linear Search : In here, we haven’t used any specific programming language but wrote the steps of a linear search in a simpler form which can be further modified into a proper program. Difference between Algorithm, Pseudocode and Program

33. 33 Program: A program is a set of instructions for the computer to follow. The machine can’t read a program directly, because it only understands machine code. But you can write stuff in a computer language, and then a compiler or interpreter can make it understandable to the computer. Difference between Algorithm, Pseudocode and Program

34. 34 Program: Program for Linear Search : Difference between Algorithm, Pseudocode and Program

35. 35 Informally, an algorithm is nothing but a mention of steps to solve a problem. They are essentially a solution. For example, an algorithm to solve the problem of factorials might look something like this: Here, the algorithm is written in English. If it was written in a programming language, we would call it to code instead. Here is a code for finding the factorial of a number in PHP. Data Structure & Algorithm in PHP Implementation

36. 36 Programming is all about data structures and algorithms. Data structures are used to hold data while algorithms are used to solve the problem using that data. Data structures and algorithms (DSA) goes through solutions to standard problems in detail and gives you an insight into how efficient it is to use each one of them. It also teaches you the science of evaluating the efficiency of an algorithm. This enables you to choose the best of various choices. Data Structure & Algorithm in PHP Implementation

37. 37 Time is precious. Suppose, Alice and Bob are trying to solve a simple problem of finding the sum of the first 1011 natural numbers. While Bob was writing the algorithm, Alice implemented it proving that it is as simple as criticizing Donald Trump. Code by Bob Code by Alice Use of Data Structures and Algorithms to Make Your Code Scalable

38. 38 Alice and Bob are feeling euphoric of themselves that they could build something of their own in almost no time. Let's sneak into their workspace and listen to their conversation. Alice: Let's run this code and find out the sum. Bob: I ran this code a few minutes back but it's still not showing the output. What's wrong with it? Oops, something went wrong! A computer is the most deterministic machine. Going back and trying to run it again won't help. So let's analyze what's wrong with this simple code. Two of the most valuable resources for a computer program are time and memory. Use of Data Structures and Algorithms to Make Your Code Scalable

39. 39 The time taken by the computer to run code is: The number of instructions depends on the code you used , and the time taken to execute each code depends on your machine and compiler . Use of Data Structures and Algorithms to Make Your Code Scalable

40. End of Lesson