1 Introduction to Data Structures and Algorithms.pdf

Introduction to Data Structures and Algorithms WMSU Objective: Define data structures and abstract data types Enumerate and define the foundation terms and basic terminologies used in Data Structures. List down the different characteristics of Data Structures Specify...

Introduction to Data Structures and Algorithms WMSU Objective: Define data structures and abstract data types Enumerate and define the foundation terms and basic terminologies used in Data Structures. List down the different characteristics of Data Structures Specify and explain the different problems that application face nowadays Define Data. Facts or information used usually to calculate, analyze, or plan something. OR Data are simply collection of facts and figures. Data are values or set of values. OR The quantities, characters, or symbols on which operations are performed by a computer, being stored and transmitted in the form of electrical signals and recorded on magnetic, optical, or mechanical recording media. Define Data. In computing, data is information that has been translated into a form that is more convenient to move or process. Data is collected and analyzed to create information suitable for making decisions  Data items that are divided into sub items are group items; Those that are not divided are called elementary items. For example, a student’s name may be divided into three sub items – [first name, middle name and last name]  Attribute and Entity – characteristics Entity Set – entities of similar attributes form an entity set Field – single elementary unit of information Record – collection of field values of a given entity File – collection of records Atomic Data Data that we choose to consider as a single, nondecomposable entity. – For example, the integer 4562 may be considered as a single integer value. The decomposed digits – 4, 5, 6, 2 will not have the same characteristics of the original integer Atomic Data Type is a set of atomic data with identical properties. They are degined by a set of values and a set of operations that act on the values. Composite Data Data that can be broken out into subfields that have meaning. – Example: telephone number Good Computer Program A computer program is a series of instructions to carry out a particular task written in a language that a computer can understand. The process of preparing and feeding the instructions into the computer for execution. Features for a good program – Run efficiently and correctly – Have a user friendly interface – Be easy to read and understand – Be easy to debug – Be easy to modify – Be easy to maintain Good Computer Program Programs consists of two things: Algorithms and data structures A Good Program is a combination of both algorithm and a data structure An algorithm is a step by step recipe for solving an instance of a problem A data structure represents the logical relationship that exists between individual elements of data to carry out certain tasks A data structure defines a way of organizing all data items that consider not only the elements stored but also stores the relationship between the elements What is Data Structure? a systematic way to organize data in order to use it efficiently. Foundation Terms Interface – represents the set of operations that a data structure supports. Implementation – provides the internal representation Types of Data Structure Primitive Data Structure: – int, float, char Non-primitive Data Structures: – Arrays, Structures, stacks Linear Data Structures: – Stacks, queues, linked list Non-Linear Data Structures: – Trees, Graphs. Characteristics of Data Structure Correctness − Data structure implementation should implement its interface correctly. Time Complexity − Running time or the execution time of operations of data structure must be as small as possible. Space Complexity − Memory usage of a data structure operation should be as little as possible. Execution Time Cases Worst Case − This is the scenario where a particular data structure operation takes maximum time it can take. Average Case − This is the scenario depicting the average execution time of an operation of a data structure. Best Case − This is the scenario depicting the least possible execution time of an operation of a data structure. Why do we need Data Structures? Data Search – Consider an inventory of 1 million(106) items of a store. If the application is to search an item, it has to search an item in 1 million(106) items every time slowing down the search. As data grows, search will become slower. Processor Speed – Processor speed although being very high, falls limited if the data grows to billion records. Multiple requests − As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data. Why Python?  Python is a general-purpose interpreted, interactive, object- oriented, and high-level programming language. It was created by Guido van Rossum during 1985- 1990. Python is designed to be highly readable. It uses English keywords frequently where as other languages use punctuation, and it has fewer syntactical constructions than other languages.  Python is a MUST for students and working professionals to become a great Software Engineer – Python is Interpreted – Python is Interactive – Python is Object-Oriented – Python is a Beginner's Language Applications of Python Easy-to-learn Portable Easy-to-read Extendable Easy-to-maintain Databases A broad standard library GUI Programming Interactive Mode Scalable