Data_structures_and_algorithm_Lec_1.pptx

Object oriented programming in C

1. Data structures and algorithm 1 01 1 1 0 .0 10 Q 1 0 01 0 3 01 0 0. Qq. qQq 1 A1z Dr. Muhammad Idrees

2. Books to Follow D.S.Malik , “Data Structures using C++” D.Samanta , “Classic Data Structures”, Prentice Hall Tenenbaum , M.Augenstein , and Y. Langman , “Data Structures using C and C++”, Prentice Hall. 2

3. Some General Comments 3 Encouragement to ask questions during class Without your feedback, it is impossible for me to know what you don’t know?  There is no reason not to ask questions during class Of course, you could also send email.  Encouragement to read course material prior to class Kindly switch off your Mobile Phones during class

4. Introduction to Data Structure 4 A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently

5. Need for Data Structures Data structures organize data  more efficient programs. More powerful computers  more complex applications. More complex applications demand more calculations.

6. Organizing Data Any organization for a collection of records that can be searched, processed in any order, or modified. The choice of data structure and algorithm can make the difference between a program running in a few seconds or many days.

7. What is Data Structure? 7 Data structure is a representation of data and the operations allowed on that data. A data structure is a way to store and organize data in order to facilitate the access and modifications. Data Structure is the method of representing of logical relationships between individual data elements related to the solution of a given problem.

8. Fundamental Data Structures 8 Hash Tables Basic Data Structures Linear Data Structures Non-Linear Data Structures Linked Lists Stacks Queues Trees Graphs Arrays

9. array Linked list tree queue stack

10. Linear Data Structures 10 A data structure is said to be linear if its elements form a sequence or a linear list. Examples: Arrays Linked Lists Stacks Queues

11. Non-Linear Data Structures 11 A data structure is said to be non-linear if its elements does not form a sequence or a linear list. Examples: Trees Graphs Hash Tables Each element may be connected with two or more other nodes or items in a non-linear arrangement.

12. Operations on Data Structures 12 Traversal: Travel through the data structure Search: Traversal through the data structure for a given element Insertion: Adding new elements to the data structure Deletion: Removing an element from the data structure Sorting: Arranging the elements in some type of order Merging: Combining two similar data structures into one

13. Arrays Linked List Stacks Queues Linear Data Structures 13

14. Arrays 14 A sequence of n items of the same data type that are stored contiguously in computer memory and made accessible by specifying a value of the array’s index. Properties: fixed length (need preliminary reservation of memory) contiguous memory locations direct access Insert/delete a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] 1 2 3 4 5 6 7 8 9 10 Array a with 10 integer elements

15. Linked List 15 A sequence of zero or more nodes each containing two kinds of information: some data and one or more links called pointers to other nodes of the linked list. Properties dynamic length arbitrary memory locations access by following links Insert/delete Types of Linked List Singly linked list (next pointer) Doubly linked list (next + previous pointers)

16. Stacks 16 A stack is a data structure that uses last-in, first-out (LIFO) ordering and allows reading and writing on the top element only. Properties insertion/deletion can be done only at the top LIFO Two operations Push (insertion) Pop (removal)

17. Queues 17 Collection with access only to the item that has been present the longest Properties Insertion/ enqueue from the rear (back) and deletion/ dequeue from the front. FIFO Two operations Enqueue Dequeue 20 30 10 60 57 29 Front Back

18. Graphs Trees Hash Tables Non-Linear Data Structures 18

19. Graphs 19 Formal definition: A graph G = <V, E> is defined by a pair of two sets: a finite set V of items called vertices and a set E of vertex pairs called edges . Undirected and directed graphs ( digraphs ). Complete, dense, and sparse graphs Undirected Graph Directed Graph

20. Trees 20 A Tree is a way of representing the hierarchical nature of a structure in a graphical form. Properties of trees Root Node Child Node Parent Node Leaf Node Types Unordered Tree Binary Tree is an ordered tree data structure in which each node has at most two children. Ordered Tree Binary Tree

21. Hash Tables 21 A hash table is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values.

22. Summary 22 A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. Linear Data Structures Arrays Linked List Stacks Queues Non Linear Data Structures Graphs Trees Hash Tables

23. Selecting a Data Structure Select a data structure as follows: Analyze the problem to determine the resource constraints a solution must meet. Determine the basic operations that must be supported. Quantify the resource constraints for each operation. Select the data structure that best meets these requirements.

24. Data Structure Philosophy Each data structure has costs and benefits. Rarely is one data structure better than another in all situations. A data structure requires: space for each data item it stores, time to perform each basic operation, programming effort.

25. A precise rule (or set of rules) specifying how to solve some problem. Introduction to Algorithms 25

26. What is an Algorithm? 26 An algorithm is a sequence of unambiguous instructions for solving a problem, i.e., for obtaining a required output for any legitimate input in a finite amount of time. Properties Can be represented various forms Unambiguity /clearness Effectiveness Finiteness/termination Correctness

27. What is an Algorithm? 27 Recipe, process, method, technique, procedure, routine,… with the following requirements: Finiteness terminates after a finite number of steps Definiteness rigorously and unambiguously specified Clearly specified input valid inputs are clearly specified Clearly specified/expected output can be proved to produce the correct output given a valid input Effectiveness steps are sufficiently simple and basic

28. Why Study Algorithms? 28 Algorithms solve problems Good choice: more efficient programs Bad choice: poor programs performance Example: Problem: Find the largest element ‘k’ out of ‘N’ integers Easy algorithms: sort all integers, then list the first or last element Better algorithm: take first element then read through the list Different algorithms perform better on different inputs Input size also affect the performance.

29. Notion of Algorithm and Problem 29 “Computer ” Problem Algorithm Input Output

30. Representation of an Algorithms 30 An algorithm may be represented in different forms: A description using English/other languages A real computer program, e.g. C++ or java A pseudo-code, C-like program, program-language-like program. Program = algorithms + data structures

31. Basic Issues Related to Algorithms 31 How to design algorithms How to express algorithms Proving correctness Efficiency (or complexity) analysis Theoretical analysis Empirical analysis Optimality

32. Analysis of Algorithms 32 How good is the algorithm? Correctness Time efficiency Space efficiency

33. Algorithm Efficiency 33 There are often many algorithms for a given problem. How do we choose the best? Goals of program design: Algorithm is to be easy to understand, code, debug Algorithm makes efficient use of computer’s resources How to measure the efficiency? Empirical comparison (run the program) Asymptotic algorithm analysis (without running the program) Factors affecting running time (size of the input)

34. Best, Worst and Average Cases 34 Not all inputs of a given size take the same time. Each algorithm has three cases: Best case: Worst Case: Average Case:

35. Example: Best, Worst and Average Cases 35 Sequential search for ‘k’ in an array of ‘n’ integers: Best case: ‘k’ is the first element of the array. Worst case: the search must visit every element once. This happens when the value being searched for is either the last element in the list, or is not in the list Average case: on average, assuming the value searched for is in the list and each list element is equally likely to be the value searched for, the search visits only n /2 elements.