DSA # 1 Introduction to DSA.pdf

9/25/2017 Data Structure & Algorithms Muzammil Khan Department of Computer & Software Technology University of Swat 1...

9/25/2017 Data Structure & Algorithms Muzammil Khan Department of Computer & Software Technology University of Swat 1 Evaluation  Evaluation Criteria Total Marks 100% (100)  Final Term Exam 50%  Mid Term Exam 30%  Assignments + Presentations + Quizzes 20%  Recommended Readings Theory and Problems of data Structures, Schaum’s Series  Written by Seymour Lipschutz. Data Structures using C  Written by Tanenbaum Aaron et. al. An introduction to data structures with applications  Written by Tremblay J.P and Sorenson P.G Research Articles and Internet Data Structure & Algorithms 2 1  9/25/2017 Evaluation (Cont...)  Policies Late assignments submission may be accepted with marks reduction.  There will be a 10% reduction for assignments submitted up to 24 hours late Students who have copied assignments or whose assignments have been copied will both be given a zero Plagiarism is not acceptable.  Anyone found to be guilty of plagiarism in an assignment will be given a zero in that assignment Quizzes may be unannounced or announced (depends on your response!) Data Structure & Algorithms 3 Chapter 1 Introduction Data Structure & Algorithms 4 2  9/25/2017 Basic Terminologies  Data Data are simply collection of facts and figures OR Data are values or set of values  Data Item A data item refers to a single unit of values  Group Data Items Those data items that are divided into sub items Those that are not are called elementary data items  For example Student’s ID, Age, Gender are elementary data items, whereas Name (First, Middle, Last), Address (Street, Area) are group data items Data Structure & Algorithms 5 Basic Terminologies (Cont...)  Entity and Attributes An entity is that which contains certain attributes or properties, which may be assigned values Entities with similar attributes form an entity set  For example: all the employees in an organization Each attribute of an entity set has a range of values  The set of all possible values that could be assigned to the particular attribute  Information The term “information” is sometimes used for data with given attributes OR In other words, meaningful or processed data Data Structure & Algorithms 6 3  9/25/2017 Basic Terminologies (Cont...)  Field Field is a single elementary unit of information representing an attribute of an entity  Record Record is a collection of field values of a given entity  File File is a collection of records of the entities in a given entity set  Data Type Data type is a way to classify various types of data such as integer, string, etc. Which determines the values that can be used with the corresponding type of data Data Structure & Algorithms 7 Basic Terminologies (Cont...) Specify the type of operations that can be performed on the corresponding type of data  There are two data types 1. Built-in Data Type  Those data types which has built-in support for a language  For example: int, float, string, character, boolean, etc. 2. Derived Data Type  Those data types which are implementation independent as they can be implemented in one or the other way  These data types are normally built by the combination of primary or built-in data types and associated operations on them  For example: list, array, stack and queue Data Structure & Algorithms 8 4  9/25/2017 Algorithm  Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output Algorithms are generally created independent of underlying languages  That is, a same algorithm can be implemented in more than one programming language  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 - to update an existing item in a data structure Delete - to delete an existing item from a data structure Data Structure & Algorithms 9 Characteristics of an Algorithm  An algorithm should have the following characteristics 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 Input - An algorithm should have 0 or more well-defined inputs Output - An algorithm should have 1 or more well-defined outputs, and should match the desired output Finiteness - Algorithms must terminate after a finite number of steps Feasibility - Should be feasible with the available resources Independent - An algorithm should be independent of any programming code Data Structure & Algorithms 10 5  9/25/2017 Parts of Algorithm  Algorithm can be divided into two parts 1. Algorithm’s Description 2. Algorithm’s Steps/Statements  Algorithm’s Description Describe the main purpose of the algorithm Describe the symbols and abbreviations used Describe inputs/outputs, Etc...  Algorithm’s Statements Presents the steps to be executed and perform the tasks  Which would be implemented using any programming language Data Structure & Algorithms 11 Example “To find largest element in array”  Algorithm’s Description A non-empty array DATA with N numerical values is given. This algorithm finds the location LOC of the largest value MAX of DATA. The variable K is used as counter.  Algorithm’s Statements Step 1. [Initialize] Set K := 1, LOC := 1 and MAX := DATA Step 2. [Increment counter] Set K := K + 1 Step 3. [Test counter] if K > N, then: write: LOC, MAX and Exit Step 4. [Compare & Update] if MAX < DATA[K], then: Set LOC := K and MAX := DATA[K] Step 5. [Repeat loop] Go to Step 2 Data Structure & Algorithms 12 6  9/25/2017 Example “To find largest element in array”  OR steps can be written as  Algorithm’s Statements Step 1. Set K := 1, LOC := 1 and MAX := DATA Step 2. Set K := K + 1 Step 3. if K > N, then: write: LOC, MAX and Exit Step 4. if MAX < DATA[K], then: Set LOC := K and MAX := DATA[K] Step 5. Go to Step 2  Different steps can be used by number and by nature Indentation is best to used Data Structure & Algorithms 13 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 We have many data structures The choice of a particular data model depends on the two considerations 1. It must be rich enough in structure to mirror the actual relationships of the data in the real world 2. The structure should be simple enough that one can effectively process the data whenever necessary Data Structure & Algorithms 14 7  9/25/2017 Categories of Data Structure  The data structure can be classified in to major types: 1. Linear Data Structure 2. Non-linear Data Structure  Linear Data Structure A data structure is said to be linear if its elements form any sequence There are basically two ways of representing such linear structure in memory 1. One way is to have the linear relationships between the elements represented by means of sequential memory location,  For example: Array Data Structure & Algorithms 15 Categories of Data Structure (Cont...) 2. The other way is to have the linear relationship between the elements represented by means of pointers or links  For example: linked lists Examples: Array, Queue, Stacks and Link Lists  Non-linear Data Structure This structure is mainly used to represent data containing a hierarchical relationship between elements Examples: Graphs, Trees and Table of contents Data Structure & Algorithms 16 8  9/25/2017 Operations on DS  The data in the data structures are processed by certain operations  The particular data structure chosen largely depends on the frequency of the operation that needs to be performed on the data structure  DS Operations 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. Data Structure & Algorithms 17 Operations on DS (Cont...) Inserting: Adding a new node/record to the structure Deleting: Removing a node/record from the structure Sorting: Sorting elements in data structure either in ascending order or descending order Merging: Merging elements of two or more data structures after satisfying specified condition Data Structure & Algorithms 18 9  9/25/2017 End of Chapter  Homework Study the following in details  Algorithm Notations and Basic terms  Pages 21-22  Control structures  Pages 23-24  Sub-algorithm, variables and data types  Pages 30-31  Exercise  Pages 33...  You may have quiz next week Data Structure & Algorithms 19 10