1 The Stages of ADT.pdf

Course Packet 1 The Stages of ADT Maria Lolita G. Masangcap Introduction This course packet allows the students to differentiate abstract data type, data structure, and algorithm. Also, it discusses the stages of abstract data types where data properties are specified, an...

Course Packet 1 The Stages of ADT Maria Lolita G. Masangcap Introduction This course packet allows the students to differentiate abstract data type, data structure, and algorithm. Also, it discusses the stages of abstract data types where data properties are specified, and the algorithm is carried out using a data structure. At the end of the course packet, students will be given a computing problem and are required to write a solution in the form of an algorithm with ADT specification and data structure representation. Introduction At the end of this course packet, you will be able to explain the basic concepts of abstract data types and the implementation of algorithm using data structure. Data Information gathered to express knowledge about a world or an environment Manipulated by operations to discuss, explain, and calculate things about this environment Example: School Environment Group Activity The class will be divided in four (4) groups through breakout sessions. In eight (8) minutes, discuss by group the data that can be gathered in the following environment Library Pharmacy Clinic Supermarket Choose a particular presenter who will discuss the output of the group. The group can create a presentation for the output This is graded, and only those who have participated will receive a score for this activity. Post your output in our Discord Server – Section-Forum Abstract Data Types (ADT) A model or description of Abstract Data Type (ADT) a type of data Data Properties Properties of the data Operations that can be Operations performed on that data Abstract Data Types (ADT) Example: Abstract Data Type (ADT) Temperature in one place Positive Data Properties Negative Get Minimum Operations Get Maximum Convert Temp Stages of ADTs 1. Specification Identification of the data’s components, properties, relationships among its components, and the operations performed on the data in a problem 2. Representation Design on how to store instances of the ADT -> DATA STRUCTURE 3. Implementation Procedural description of how each operation is carried out using the data structure -> ALGORITHM  Sample Problem ADT Specification Data Properties List of n employees with the following details: Name – composed of characters Salary – must be real numbers Bonus – must be real numbers The ABC Manufacturing Company plans to give a year-end bonus to each Operations of its employees. Bonus is computed Get the names of each employee based on the employee’s salary. Get the salary of each employee Determine the bonus of each employee Abstract Data Types (ADT) ADTs model Examples of sets of data. ADTs ADTs can be They are Static (They Stacks, queues, change trees, graphs, implemented naturally infrequently or in many kinds implemented do not change at of languages. as classes. all.) Dynamic (They change frequently.) Data Structures Show relationships among the data items using primitive structures or other data structures available in a programming environment to facilitate operations of the ADTs Dictates how much space is required to store the ADT Directly influences the efficiency of the algorithms that use them Data Structures Data structures are programmed using features of programming languages. Simple Data Structure Complex Data Structure Primitive Data Type Composite or User Integer Defined Data Types Float Arrays Boolean Linked Lists Character Strings Structs Classes Simple Data Structures Primitive Data Types Keyword Description Size/Format Range byte Byte-length integer 8-bit two's complement -128 to127 short Short integer 16-bit two's complement -32,768 to 32,767 -2,147,483,648 to int Integer 32-bit two's complement 2,147,483,647 -9,223,372,036,854,775,808 to long Long integer 64-bit two's complement 9,223,372,036,854,775,807 float Single-precision floating point 32-bit IEEE double Double-precision floating point 64-bit IEEE char A single character 16-bit Unicode character Valid characters boolean A Boolean value (true or false) true or false true and false The programming language imposes policies on how instances of each data type are stored and accessed in memory. Complex Data Structures Composite Data Types Arrays Linked List Strings Structs Classes An ordered collection of data in These allow data These allow data of These are These allow data to which each element and operations to the same type to be sequences of be grouped as a contains the be defined as a stored in cells. characters single data type location of the next single data type element Each element of an array is stored in a contiguous memory The elements in a Instances of structs Instances of classes linked list are called Each has a length space allowing can be created are called objects direct access to each nodes. cell  Sample Problem Data Structure Each data may be stored in a node. Multiple nodes can be stored in an array. 0 1 2 3 4 name[] Sam Shaan Jasmine Jaimie Yman The ABC Manufacturing Company salary[] 6,000 3,000 4,200 8,500 2,100 plans to give a year-end bonus to each bonus[] ? ? ? ? ? of its employees. Bonus is computed based on the employee’s salary. The indices are used to access each node. Algorithms A finite set of instructions that specify sequence of operations to be carried out Input Values in order to solve a specific problem or class of problems Output Values The input, output, and intermediate computations are represented with the Problem use of DATA STRUCTURES. Solved Algorithm Example Imagine you have an unsorted list of random numbers 110 100 125 160 131 120 Our goal is to find the highest number in this list. Upon first thinking about the solution, you will realize that you need to look at each number only once. Algorithm Example 110 100 125 160 131 120 160 is the largest number Largest number 1. When you begin, the first number is the largest number in the list you’ve seen so far. 2. Look at the next number, and compare it with the largest number you’ve seen so far. 3. If this next number is larger, then make that the new largest number you’ve seen so far. 4. Repeat steps 2 and 3 until you have gone through the whole list. Properties of Algorithm 1. Finiteness – all instructions of an algorithm must terminate after finite number of steps. 2. Absence of ambiguity – each instruction must be clear and unambiguous. 3. Sequence Definition – steps or procedures must be grouped in proper sequence 4. Input and Output Definition – data and required results must be defined 5. Scope definition – scope of the problem must be defined first and it is the only part that must be given into considerations in solving it 6. Effectiveness – each step executes as expected in a finite amount of time 7. Efficiency – solves the problem with less resources such as time and space Algorithms It is often written in pseudocode before it is implemented in a specific programming language. Algorithms are then combined to form bigger algorithms. Data structures, together with algorithms, form programs. Some algorithms are functions. They perform computations on their inputs and return values. Some algorithms are subroutines that produce results are side effects; they do not return values. Sample Problem The ABC Manufacturing Company plans to give a year-end bonus to each of its employees. Write the algorithm that will accept name and monthly salary of five (5) employees, then compute the bonus of all the employees. Consider the ff. criteria: If the employee’s monthly salary is less than 5, 000.00, the bonus is 50% of the salary; otherwise, bonus is 5,000.00. Print out the names and corresponding bonus of the employees.  Sample Problem ADT Specification ADT Representation Data Properties Data Structure List of n employees with the following details: Each data may be stored in a node. name – composed of characters Multiple nodes can be stored in an array. salary – must be real numbers bonus – must be real numbers 0 1 2 3 4 name[] Sam Shaan Jasmine Jaimie Yman Operations Get the names of each employee salary[] 6,000 3,000 4,200 8,500 2,100 Get the salary of each employee bonus[] ? ? ? ? ? Determine the bonus of each employee The indices are used to access each node.  Sample Problem Data Structure Each data may be stored in a node. Multiple nodes can be stored in an array. Let us compute now the bonus of each employee… 0 1 2 3 4 The ABC Manufacturing Company plans to give a year- end bonus to each of its employees. Write the name[] Sam Shaan Jasmine Jaimie Yman algorithm that will accept name and monthly salary of five (5) employees, then compute the bonus of all the salary[] 6,000 3,000 4,200 8,500 2,100 employees. Consider the ff. criteria: If the employee’s monthly salary is less than 5, 000.00, the bonus is 50% bonus[] 5,000 1,500 2,100 5,000 1,050 of the salary; otherwise, bonus is 5,000.00. Print out the names and corresponding bonus of the employees.  Sample Problem ADT Implementation ADT Specification Algorithm Data Properties main() List of n employees with the following details: name – composed of characters 1. Initialize all variables: name[] as string, salary – must be real numbers salary[] as real numbers, bonus[] as real bonus – must be real numbers numbers Operations 2. name[] = Call getName() getName() - Get the names of each employee 3. salary[] = Call getSalary() getSalary() - Get the salary of each employee 4. bonus[] = Call computeBonus(salary) computeBonus()- Determine the bonus of 5. Display employees’ name and bonus each employee 6. Stop  Sample Problem Algorithm ADT Specification String getName() Operations 1. Initialize variable pangalan as string Get the names of each employee 2. Read/Input value of pangalan Get the salary of each employee 3. Return pangalan Determine the bonus of each employee Double getSalary() Double computeBonus(Double salary) 1. Initialize variable sahod as real 1. Initialize variable bonus as real numbers numbers 2. If salary is less than 5000 then bonus is 2. Read/Input value of sahod 50% of the salary; else, bonus is 5000. 3. Return sahod 3. Return bonus Q&A Any Questions??? CP1 The Stages of ADT