CC104 - Prelim Module 1.pdf

College of Information Technology First Semester, A.Y. 2024-2025 MODULE 1 INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS Introduct...

College of Information Technology First Semester, A.Y. 2024-2025 MODULE 1 INTRODUCTION TO DATA STRUCTURES AND ALGORITHMS Introduction This module entitled Introduction to Data Structures and Algorithms is about the programmatic way of storing data so that data can be used efficiently. Almost every enterprise application uses various types of data structures in one or the other way. This topic will give you a great understanding on Data Structures needed to understand the complexity of enterprise level applications and need of algorithms, and data structures. Date and Time Allotment Week 1 (5 hours) I. Objectives At the end of the end of this module, students should be able to: 1. Understand what Data Structures and Algorithms. 2. Identify key features of Data Structures. 3. Recognize and Evaluate the Qualities of Good Algorithm. 4. Apply basic terminology in Data Structures and Algorithms. II. Lecture WHAT IS DATA STRUCTURE? Data Structure is a way of collecting and organizing data in such a way that we can perform operations on these data in an effective way. Data Structures is about rendering data elements in terms of some relationship, for better organization and storage. Data Structures are structures programmed to store ordered data, so that various operations can be performed on it easily. It represents the knowledge of data to be organized in memory. It should be designed and implemented in such a way that it reduces the complexity and increases the efficiency. CHARACTERISTICS OF A 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. NEED FOR DATA STRUCTURE As applications are getting complex and data rich, there are three common problems that applications face now-a-days.  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. To solve the above-mentioned problems, data structures come to rescue. Data can be organized in a data structure in such a way that all items may not be required to be searched, and the required data can be searched almost instantly. WHAT IS AN ALGORITHM? It is derived from the name of the Arab mathematician, Abu Ja’far Mohammed ibn Musa al Kowarizmi (c.A.D. 825), who wrote a book describing procedures for solving a problem. 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, i.e. an algorithm can be implemented in more than one programming language. In computer programming terms, an algorithm is a set of well-defined instructions to solve a particular problem. It takes a set of input(s) and produces the desired output. Example: An algorithm to add two numbers:  Take two number inputs  Add numbers using the + operator  Display the result An algorithm to prepare an omelet 1. Get the frying pan 2. Get the oil a. Do we have oil? i. If yes, put it in the pan ii. If no, do we want to buy oil? 1. If yes, the go and buy. 2. If no, we can terminate 3. Turn on the stove, etc. QUALITIES OF A GOOD ALGORITHM  Input and output should be defined precisely.  Each step in the algorithm should be clear and unambiguous.  Algorithms should be most effective among many ways to solve a problem.  An algorithm shouldn't include computer code. Instead, the algorithm should be written in such a way that it can be used in different programming languages. From the data structure point of view, 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 − Algorithm to update an existing item in a data structure.  Delete − Algorithm to delete an existing item from a data structure. CHARACTERISTICS OF AN ALGORITHM Not all procedures can be called 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 have step-by-step directions, which should be independent of any programming code. EXECUTION TIME CASES There are three cases which are usually used to compare various data structure's execution time in a relative manner.  Worst Case − This is the scenario where a particular data structure operation takes maximum time it can take. If an operation's worst case time is ƒ(n) then this operation will not take more than ƒ(n) time where ƒ(n) represents function of n.  Average Case − This is the scenario depicting the average execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then m operations will take mƒ(n) time.   Best Case − This is the scenario depicting the least possible execution time of an operation of a data structure. If an operation takes ƒ(n) time in execution, then the actual operation may take time as the random number which would be maximum as ƒ(n). BASIC TERMINOLOGY  Data − Data are values or set of values.  Data Item − Data item refers to single unit of values.  Group Items − Data items that are divided into sub items are called as Group Items.  Elementary Items − Data items that cannot be divided are called as Elementary Items.  Attribute and Entity − An entity is that which contains certain attributes or properties, which may be assigned values.  Entity Set − Entities of similar attributes form an entity set.  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. HOW TO ANALYZE PROGRAMS: Two phases of Algorithm Analysis: 1. Priori Estimates Obtain a function which bounds the algorithm’s complexity time. The amount of time a single execution will take or the number of times a statement executed. However, it is possible to know the exact amount of time to execute any command unless: a. the machine we are executing is known b. machine instruction set c. time required by each machine instruction; d. translation of the compiler from source to machine language. 2. Posteriori Estimates Something to do with memory spaces consumed. Example: Use of arrays vs. linked list ADDRESSING METHODS  Computed Addressing Method - used to access the elements of a structure in pre-allocated space int x; a = x;  Link Addressing Method – used to manipulate dynamic structures where the size and shape are not known beforehand or changes at runtime  Memory pool or avail list - source of the nodes from which linked structures are built MATHEMATICAL FUNCTIOS  Floor of x ( ⎣ x ⎦ ) - greatest integer less than or equal to x, x is any real number e.g.: ⎣ 3.14 ⎦ = 3 ⎣ 1/2 ⎦ = 0 ⎣ -1/2 ⎦ = -1  Ceiling of x ( ⎡ x ⎤ ) - smallest integer greater than or equal to x, where x is any real number e.g.: ⎡ 3.14 ⎤ = 4 ⎡ 1/2 ⎤ = 1  Modulo – remainder operator e.g.: 10 mod 3 = 1 24 mod 8 = 0 -5 mod 7 = -5 COMPLEXITY OF ALGORITHMS  The Big-Oh Notation (or simply O-Notation)  T(n) grows at a rate proportional to n and thus T(n) is said to have “order of magnitude n” denoted by the O-notation: T(n) = O(n)  Formal definition: g(n) = O(f(n)) if there exists two constants c and n0 such that | g(n) | = n0.  Operations on the O-Notation: ▪ Rule for Sums Suppose that T 1 (n) = O( f(n) ) and T 2 (n) = O( g(n) ). Then, t(n) = T 1 (n) + T2 (n) = O( max( f(n), g(n) ) ). Proof: By definition of the O-notation, T1(n) = n1 and T2(n) = n2. Let n0 = max(n1, n2). Then T1(n) + T2(n) = n0. = n0. = n0. Thus, T(n) = T1(n) + T2(n) = O( max( f(n), g(n) ) ). e.g. a. T(n) = 3n3 + 5n2 = O( n3 ) b. T(n) = 2n + n4 + n log n = O( 2n ) ▪ Rule for Products Suppose that T1(n) = O( f(n) ) and T2(n) = O( g(n) ). Then, T(n) = T1(n) * T2(n) = O( f(n) * g(n) ). SUMMARY  A data structure is a special way of organizing and storing data in a computer so that it can be used efficiently.  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, i.e. an algorithm can be implemented in more than one programming language.  In computer programming, there are often many different ways – algorithms – to accomplish any given task. Each algorithm has advantages and disadvantages in different situations. III. Application/Activity Determine the big-O notation for the following: (5 pts each) 1. 5n2+9n+3n4 2. 2n+n3 3. Combine 1 & 2 Create a program to perform addition, subtraction, multiplication, division and modulo. IV. Assessment Explain how an algorithm in an application program differs from an algorithm in an abstract data type? Illustrate your answer with an example. (50 pts) V. Other References  Weiss, Mark A. Data Structures and Algorithm Analysis in C++. 4th Edition  Malik, D S. Data Structures in C++, 2nd Edition, Cengage Learning  Richard F. Gilberg (2001), Data Structure Online Reference: https://www.athabascau.ca https://cps.northeastern.edu https://www.tutorialspoint.com/data_structures_algorithms/index.htm https://www.simplilearn.com/tutorials/data-structure-tutorial/what-is-data-structure https://www.studytonight.com/data-structures/introduction-to-data-structures Prepared by: CLEDMAR N. BADONGEN, CpE Faculty, CIT Checked by: FREDERICK J. SORIANO, MIT Program Head, CIT