Data Structure Lecture 1 PDF

Data Structure and Algorithms Lecture 1  Introduction to Data Structure Big O Recursion Stacks Queues Course Lists and linked lists Outline Trees Sorting Searching Graphs...

Data Structure and Algorithms Lecture 1  Introduction to Data Structure Big O Recursion Stacks Queues Course Lists and linked lists Outline Trees Sorting Searching Graphs Hashing Introduction to Data Structure and Abstract Data Types  What is Data Structure? 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 are the method of representing of logical relationships between individual data elements related to the solution of a given problem.  Basic Data Structure Basic Data Structures Linear Data Structures Non-Linear Data Structures Arrays Linked Lists Stacks Queues Trees Graphs Hash Tables  array Linked list queue tree stack  The choice of particular data model depends on two consideration: It must be rich enough in structure to represent the Selection of relationship between data Data elements Structure The structure should be simple enough that one can effectively process the data when necessary Types of Data Structure Linear: In Linear data structure, values are arrange in linear fashion. Non-Linear: The data values in this structure are not arranged in order. Type of Data Structures Homogenous: In this type of data structures, values of the same types of data are stored. Array Non-Homogenous: In this type of data structures, data values of different types are grouped and stored. Structures Classes Abstract Data Type and Data Structure Definition:- Abstract Data Types (ADTs) stores data and allow various operations on the data to access and change it. A mathematical model, together with various operations defined on the model An ADT is a collection of data and associated operations for manipulating that data Data Structures Physical implementation of an ADT data structures used in implementations are provided in a language (primitive or built-in) or are built from the language constructs (user-defined)  The Core Operations of ADT Every Collection ADT should provide a way to: add an item remove an item find, retrieve, or access an item more possibilities is the collection empty make the collection empty give me a sub set of the collection  Software life cycle Without software a computer is of no use. A program goes through many phases called the life cycle of the program. The three fundamental stages through which a program goes are  development, Use(Once users start using the program, they most certainly discover problems or have suggestions to improve it. ) maintenance. (the program is modified to fix the (identified) problems and/or to enhance it.)  Analysis Software Design Development Phase Implementation Testing and debugging  Analyzing the problem is the first and most important step. This step requires you to do the following: Thoroughly understand the problem. Analysis Understand the problem requirements. If the problem is complex, divide the problem into subproblems, analyze each subproblem, and understand each subproblem’s requirements. Design Algorithm: A step-by-step problem-solving process in which a solution is arrived at in a finite amount of time. Dividing a problem into smaller subproblems is called structured design. This process of implementing a structured design is called structured programming. In object-oriented design (OOD), the first step in the problem-solving process is to identify the components called objects, which form the basis of the solution, and determine how these objects interact with one another.  OOD has the Encapsulation—The ability to following combine data and operations three Inheritance—The ability to create new (data) types from existing (data) basic types principles: Polymorphism—The ability to use the same expression to denote different operations  you write and compile Implementation programming code to implement the classes and functions that were discovered in the design phase. Testing and Debugging The term testing refers to testing the correctness of the program; that is, making sure that the program does what it is supposed to do. The term debugging refers to finding and fixing the errors, if they exist. two types of testing—black-box testing and white- box testing.  Black-box testing you do not know the internal working of the algorithm or function. You know only what the function does. black-box testing and Black-box testing is based on white-box inputs and outputs. testing White-box testing relies on the internal structure and implementation of a function or algorithm. Lecture 1 finished