Data Structures with Algorithm PDF

DATA STRUCTURES with ALGORITHM MODULE 1 College of Computer Studies – Calapan City Campus At the end of this lesson, the students must have: 1. explained important terms in data structures and its classification in class. 2. performed all activi...

DATA STRUCTURES with ALGORITHM MODULE 1 College of Computer Studies – Calapan City Campus At the end of this lesson, the students must have: 1. explained important terms in data structures and its classification in class. 2. performed all activities to measure their understanding of the lesson. Terminologies in DATA STRUCTURE “Before we start discussing the main concept of this subject, let us have some important terminologies that we might encounter all throughout the discussion. So, let’s begin! ” Terminologies in DATA STRUCTURE ALGORITHM  A set of instruction for solving a problem(s).  It has steps that requires decisions such as logic or comparison.  It is very important to computers to process information, since computer programs are basically algorithms which commands the computer to what specific task to do (Patel, 2018). Terminologies in DATA STRUCTURE you create a simple algorithm for a specific problem scenario. you were asked also do a program for that. you are already preparing yourself to find different possibilities and the easiest possible way to solve a problem. Terminologies in DATA STRUCTURE DATA STRUCTURE  a representation of the logical relationship existing between individual elements of data.  In other words, it is a way of organizing all data items that considers not only the elements stored but also their relationship to each other (CseWorldOnline, 2020). E.g. programs and their data Terminologies in DATA STRUCTURE According to Patel (2018), “a computer system is known for Data Management where the term “data” is very essential. The data must be represented, stored, organized, processed and managed since it acts a very important role in the user environment. ” Terminologies in DATA STRUCTURE Representation of data.  Data can be in forms of raw data (raw facts e.g. values), data item (single unit of value) and data structure.  It is a fact collected together for reference or analysis. It consists of characters, symbols, quantities performed by computer, stored and transmitted in the form of electrical signals and recorded on different medias. Terminologies in DATA STRUCTURE DATA TYPE Data has different types. Same data could be grouped into one. Data type is an attribute of data which tells the compiler and interpreter on what to do or how to use the data. Data type refers to a named group of data which shares properties or characteristics (Patel, 2018). Below are some data types. Terminologies in DATA STRUCTURE Integer  represents whole numbers (signed or unsigned).  The range of its values depends on the size of the memory used.  Its types are sbyte, byte, short, ushort, int, uint, long and ulong. Examples for this type are the values for days, years, age, whole number, etc. which accept whole numbers Terminologies in DATA STRUCTURE Real represents values with decimal point. It could be signed or unsigned. Its types are float and double. The double type (64 bits) can store a lot more precision than the float type (32 bits). Terminologies in DATA STRUCTURE Character represents symbolic information which gives a corresponding integer code. It takes 16 bits of memory. It is a single value either alphabet letters, numbers from 0-9 or accepted special characters.  “One way to combine different data is by means of Data Structures. It is a named group of different data which could be used or processed as a single unit. According to Ahlawat (2020) data structure is about rendering data elements in terms of some relationship, for better organization and storage. ” E.g. We have some data which has, player's name “Jawo" and age 36. Here, “Jawo" is of String data type and 36 is of integer data type. Organize this into: Player’s Record with Name and Age. Name and Age are of different type of data. E.g. Class in OOP It collects all different type of data under one single entity But the only difference is that, Data Structures provides for techniques to access and manipulate data efficiently. Terminologies in DATA STRUCTURE Classification of Data Structures The two classifications of Data Structures are: Primitive Data Structure Non-Primitive Data Structure  The picture above presents the classification of data structures into primitive and non-primitive. Primitive Data Structure is composed of integer, float, character and pointer type of data while Non-Primitive Data Structure has Array, List and File. Primitive Data Structure  These are basic structures and directly operated upon by the machine instructions.  In general, there are different representation on different computers  Integer, Floating-point number, Character constants, string constants, pointers etc, fall in this category.  This data type is basically not composed of another data type. Non-Primitive Data Structure  more sophisticated data structures.  derived from the primitive data structures.  emphasize on structuring of a group of homogeneous (same type) or heterogeneous (different type) data items.  This data type is basically defined by the user and sometimes known as User-Defined data types. E.g. array, class, structure, etc.  List, Array and File are example of non-primitive data structures. “ ” Differences  A primitive data structure is generally a basic structure that is usually built into the language, such as an integer, a float.  A non-primitive data structure is built out of primitive data structures linked together in meaningful ways, such as a or a linked-list, binary search tree, AVL Tree, graph etc.   Create The design of an efficient data  Selection structure must take operations to be  Updating performed on the data structure. The  Searching most commonly used operation on data structure are broadly categorized  Sorting into the following types:  Merging  Destroy or Delete  TYPES OF DATA STRUCTURE The four types of data structures are the following: 1. Linear: In Linear data structure, values are arranged in linear fashion. Array: Fixed-size Linked-list: Variable-size Stack: Add to top and remove from top Queue: Add to back and remove from front Priority queue: Add anywhere, remove the highest priority 2. Non-Linear:  The data values in this structure are not arranged in order.  Hash tables: Unordered lists which use a ‘hash function’ to insert and search  Tree: Data is organized in branches.  Graph: A more general branching structure, with less strict connection conditions than for a tree 3. Homogenous: In this type of data structures, values of the same types of data are stored. An example is an Array. 4.Non-Homogenous: In this type of data structures, data values of different types are grouped and stored. Examples of this are Structures and Classes. Interface.  Each data structure has an interface.  It represents the set of operations that a data structure supports.  It only provides the list of supported operations, type of parameters they can accept and return type of these operations. Terminologies in DATA STRUCTURE TYPES OF DATA STRUCTURE Interface. Each data structure has an interface. Interface represents the set of operations that a data structure supports. An interface only provides the list of supported operations, type of parameters they can Figure accept2 presents andanreturn example type of two graphical of these interfaces. This an interface where the user operations. interacts with the buttons or designs of the environment (front-end). There is another interface which is considered as a text-based type. Below is an example of an interface in the back-end of a program.  interface Cashier { void talk(); // interface method (does not have a body) void check(); // interface method (does not have a body) } This is an example of an interface in C# language. This creates a cashier interface with two methods: talk() and check() which has both no body. In order to implement this interface, the programmer should use this symbol ( : ) just like inheritance. interface Cashier { void talk(); void check(); } class Cashier1: Cashier { //body of class } Implementation.  This provides the internal representation of a data structure.  It also provides the definition of the algorithms used in the operations of the data structure.  The implementation of data structures must have a set of procedures that will manipulate the instances of that structure.  CHARACTERISTICS OF DATA STRUCTURE Correctness  A data structure implementation is said to be correct if it respects the specification of the structure.  What is Partial and Total Correctness?  For instance, it could be seen in a simple input-output behaviour. If your algorithm throws a correct answer, it is known as partial correctness and total correctness if it terminates successfully with the used algorithm.  CHARACTERISTICS OF DATA STRUCTURE Time Complexity  This refers not only the quantity of time an algorithm takes, but also for the smallest possible time it will have. Space Complexity  Same with time complexity, space complexity of an algorithm is the amount of space in the memory an algorithm may occupy.  Why is there a NEED FOR DATA STRUCTURE ????  Data Search − Consider an inventory of 1million items of a store. If the application is to search an item, it has to search an item in 1 million 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.  EXECUTION TIME CASES  Worst Case – A scenario where a data structure has taken the maximum time to do its operation.  Average Case − A scenario showing the average execution time of an operation of a data structure.  Best Case – A scenario where a data structure has taken the smallest time to do its task.  Data. Data are values or set of values.  Data Item. Data item refers to single unit of values.  Group Items. These are data items grouped into sub-item e.g. customer record.  Elementary Items. Data items that could never be divided into another group of item e.g marks, age, number of students, etc.  Attribute and Entity. An entity is that which contains certain attributes or properties, which may be assigned values. An entity in table 1 is the tbl_student. Entity Set. Entities of similar attributes from an entity set. Field. Field is a single elementary unit of information representing an attribute of an entity. For an instance, the table below has three fields namely: Id_no, F_name and L_name. Record. Record is a collection of field values of a given entity. The records for tbl_student shows each row of the table. File. File is a collection of records of the entities in a given entity set. This presents all the records (all rows) of the entities. Table 1. tbl_student Id_no F_name L_name C16-1110 Rita Viray C16-1111 Rolly Cruz  SELECTION OF DATA STRUCTURES The choice of particular data model depends on two considerations. First, it must be rich enough in structure to represent the relationship between data elements. Second, the structure should be simple enough that one can effectively process the data when necessary.  Stacks. It is a collection with access only to the last element inserted  Last in first out (LIFO)  insert/push  remove/pop  top  make empty  List. It is a Flexible structure, because it can grow and shrink on demand. Elements can be:  Inserted  Accessed First Last  Deleted at any position Tree. A Tree is a collection of elements called nodes. One of the node is distinguished as a root, along with a relation (“parenthood”) that places a Root hierarchical structure on the nodes. Other Representations  LESSON 2: ALGORITHM: Pseudocode Next lesson… and Flowchart