CC103-ModuleContents-NC.pdf

1 UNIT 1. Introduction to Data Structures and Algorithms Data structures and algorithms are fundamental components in computer science education, crucial for developing efficient software solutio...

1 UNIT 1. Introduction to Data Structures and Algorithms Data structures and algorithms are fundamental components in computer science education, crucial for developing efficient software solutions and optimizing code performance. These concepts provide the necessary tools and techniques to solve complex problems. Understanding algorithms is essential, as they are applied in various fields, including computer science and information technology programs. Sorting, a key concept in data structures, plays a vital role in computer systems, file management, memory management, and real-life applications. Learning the structure of models from data reduces human effort in identifying the right structures. At the end of this lesson, the learners should be able to: ✓ articulate the definitions and significance of data structures and algorithms. ✓ describe how data structures and algorithms are fundamental to computer science and software development. ✓ discuss the role of data structures and algorithms in optimizing performance and solving complex problems. Data structures are fundamental in computer science and information technology, enabling the efficient organization and manipulation of data. Common structures like arrays, linked lists, stacks, queues, trees, and graphs are crucial for managing data effectively. Data structures are fundamental in programming as they determine how data is organized and stored in memory during program execution. Algorithms are then utilized to efficiently manipulate the data within these structures. Understanding data structures and algorithms is essential for programmers to effectively store and manage data, optimize memory usage, and improve data retrieval processes. In programming, basic data structures like arrays and structures utilize offsets to identify fields and strides to determine record sizes. These foundational structures are the cornerstone of software development, empowering programmers to build systems that are both effective and efficient. In computer science, data structure (DS) refers to a sophisticated scheme for organizing and managing data. Simply put, a data structure is an arrangement of data in a computer's memory that is meticulously designed to optimize the speed and efficiency with which data can be accessed and manipulated by the processor. This strategic organization ensures that the data is readily available for the processor to perform necessary calculations, thereby enhancing overall computational performance. By employing various data structures, such as arrays, linked lists, stacks, queues, trees, and graphs, we can significantly improve the efficiency of algorithms and the software systems that rely on them. Through this unit, we will explore the intricacies of different data structures, their implementations, and their vital role in the efficient processing of data. A data structure should be viewed as a logical concept that addresses two fundamental concerns. First and foremost, it must determine how the data will be stored, ensuring that the arrangement of data in memory is both efficient and effective for the intended application. Secondly, it must Bauat R, and Bauat M. (2024). Data Structures and Algorithms: A Comprehensive Learning Module for C++ Programming. Nueva Ecija University of Science and Technology. 2 define the operations that will be performed on the data, specifying how data can be accessed, modified, and managed. This dual focus on storage and operations is essential for optimizing the performance and usability of the data structure within various computational contexts. Index 0 Index 1 Index 2 Index 3 Index 4 Index 5 1 SUM2024-0001 Dela Cruz Juanito Batungbakal [email protected] students.push_back({1, " SUM2024-0001", "Dela Cruz", " Juanito ", " Batungbakal", "[email protected]"}); As a student, it is crucial to understand how data structures work to enhance your programming capabilities. For example, if you are tasked with developing an information system that collects and processes student data, you need a comprehensive understanding of how the system will store those data and how it can be efficiently accessed and manipulated. Mastering data structures allows you to design systems that are not only efficient but also scalable and maintainable. This knowledge ensures that you can implement solutions that handle data storage and retrieval seamlessly, making your applications robust and effective. 1.1 Different types of data structures Data structures in computer science can be broadly divided into two categories: primitive and non- primitive data structures. Primitive data structures are the simplest forms of data representation. They include basic types like integers, floats, characters, string, boolean, and pointers. These structures are directly operated upon by machine instructions and serve as the building blocks for more complex data arrangements. They are fundamental to all programming languages and provide the essential operations needed to manipulate data at a basic level. 1.1.1 Primitive Data Structures Integers. You can use an integer represent numeric data, and more specifically, whole numbers from negative infinity to infinity, like 4, 5, or -1. NEUST - College of Information and Communications Technology  3 Float. "Float" stands for 'floating point number'. You can use it for rational numbers, usually ending with a decimal figure, such as 1.11, 2.75, or 3.14 String. Sequence of characters that is used to represent text. It can be alphabet, numeric, and special characters. Strings are a fundamental data type in many programming languages and are often implemented as an array of characters. Example “#141 Rizal Street” Boolean. Often referred to as a bool, is a data type that can hold one of two possible values: true or false. Example: bool isAdult = true; 1.1.2 Non-Primitive Data Structures In contrast, non-primitive data structures are more advanced and are constructed using primitive data structures. These include arrays, linked lists, stacks, queues, trees, and graphs. Non-primitive data structures are designed to handle more complex tasks and offer efficient ways to manage, organize, and manipulate data. They encapsulate multiple primitive data elements, combining them into more sophisticated forms to meet specific needs and purposes. For example, an array can store a list of elements of the same type, whereas a linked list can dynamically manage data elements with pointers connecting each element. Stacks and queues manage data in specific orders, trees provide hierarchical organization, and graphs represent networks of interconnected nodes. These advanced structures are crucial for developing efficient algorithms and software systems, as they allow for optimized data processing and retrieval. 1.2 Linear Data Structures Linear data structures are those in which data elements are arranged sequentially or linearly, where each element is connected to its previous and next adjacent elements. These structures are easy to implement as they maintain a straightforward arrangement of data. The following are the characteristics of linear data structures: Sequential Access: Data elements can be accessed in a sequence, one after another. Single Level: Linear data structures are single-level, meaning each element has only one successor and one predecessor, except for the first and last elements. Memory Utilization: Linear data structures utilize memory in a contiguous manner, which can sometimes lead to inefficient memory use if not managed properly. The common linear data structures are array, stack, queue, linked-list, tuple, and dictionary. An array is a data structure that stores a fixed- size sequential collection of elements of the same type. It is one of the simplest and most widely used data structures in computer programming. The elements in an array are stored in contiguous memory locations and can be accessed randomly using indices. Bauat R, and Bauat M. (2024). Data Structures and Algorithms: A Comprehensive Learning Module for C++ Programming. Nueva Ecija University of Science and Technology. 4 A stack is a linear data structure that follows a particular order in which operations are performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out). In a stack, the most recently added element is the first one to be removed. An example of this is the pile of coins, chair, or plates. Imagine a stack of plates in a cafeteria. When plates are washed, they are placed on top of the stack. The next person who needs a plate will take the one from the top, which is the most recently added plate. This system is efficient for scenarios where the most recent additions need to be accessed first. Another common example is the "undo" function in software applications. Each action you perform is placed on top of the stack, and hitting "undo" removes the most recent action, allowing you to revert to the previous state. This ensures that actions can be reversed in the correct order, maintaining the integrity of the workflow. A queue is a collection of elements that follows the First In, First Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. You can think of a queue like a line of people waiting for a service: the first person in line is the first one to be served. Enqueue Operation: This is the process of adding an element to the end of the queue. Dequeue Operation: This is the process of removing an element from the front of the queue. In a practical setting, such as a queue of people waiting their turn to be serviced, the queue operates based on a first-come, first-served principle. Individuals join the queue by lining up in the order they arrive. The person at the front of the line is the first to be attended to, followed by the next person, and so on. This method ensures an orderly and fair system where everyone gets served in the sequence they arrived. Queues can be found in various contexts, such as at a bank, a grocery store, or a ticket booth, and they help manage the flow of people efficiently, preventing chaos and ensuring that service is provided in a systematic manner. A linked-list is a fundamental data structure in computer science, consisting of a sequence of elements called nodes. Each node contains two main components: data and a reference (or link) to the next node in the sequence. NEUST - College of Information and Communications Technology  5 A list data structure (DS) can be applied in numerous practical settings due to its ability to store an ordered collection of items. One common application is in managing a to-do list. Each task is an item in the list, and tasks can be added, removed, or accessed based on their position. Lists allow for flexible management of the tasks, enabling users to prioritize or reorganize them as needed. Another example is in handling customer orders in a restaurant. Orders can be stored in a list, where each entry represents a customer's order. The restaurant staff can then process these orders sequentially, ensuring that each order is handled efficiently. If needed, the list can be updated to reflect new orders, completed orders, or canceled orders. In software development, lists are also used to manage a collection of elements such as user inputs, search results, or inventory items in an e-commerce platform. Lists provide a straightforward way to store, retrieve, and manipulate a collection of related data, making them indispensable in various real-world applications. A tuple is a fixed-size collection of heterogeneous values, meaning it can store multiple values of different types. Unlike array that can only handle data of the same type, tuple can handle and store data with different data type. Arrays and tuples have a fixed size, this means that once an array or tuple is created, its size cannot be changed. In geographic information systems (GIS), the coordinates of a location can be stored as a tuple. For instance, the coordinates of the Nueva Ecija University of Science and Technology – Gen. Street Campus can be represented as tuple. tuple landmark_coordinates(15.5782871,121.1113286); This tuple is immutable by nature, ensuring that the coordinates remain constant once defined. However, C++ has the capability to modify these data which will be discussed later. On the other hand, a dictionary is an unordered collection of key-value pairs. Each key is unique, and it maps to a value, which can be accessed, modified, or deleted. employee_records = {"Juan Dela Cruz", "Software Engineer", 75000}; Bauat R, and Bauat M. (2024). Data Structures and Algorithms: A Comprehensive Learning Module for C++ Programming. Nueva Ecija University of Science and Technology. 6 In this example, values such as “Juan Dela Cruz”, “Software Engineer”, 75000, has been mapped to employee_records on index 101. These data represent employee name, position, and salary respectively. These data structures will be explained further separately in the next units of this learning module. 1.3 Non-Linear Data Structures Non-linear data structures are those where data elements are not arranged in a sequential manner. Instead, they are arranged in a hierarchical or interconnected fashion, allowing for more complex relationships between the elements. The most common non-linear data structures are trees and graphs. A tree is a hierarchical data structure consisting of nodes connected by edges. It starts with a root node and branches out into subtrees of children, with each child having zero or more children of its own. There are different types of trees including binary tree and hierarchical tree which will be explained further in this learning module in the succeeding units. The directory structure of a computer's file system is a tree. The root directory is the root node, and every directory or file is a child node branching out from its parent directory. Graph Data Structure is a non-linear data structure consisting of vertices and edges. It is useful in fields such as social network analysis, recommendation systems, and computer networks. In the field of sports data science, graph data structure can be used to analyze and understand the dynamics of team performance and player interactions on the field. Social networks like Facebook use graphs to represent users and their connections. Each user is a node, and each connection (friendship, follow, etc.) is an edge. In the illustrative image, it shows a social network as a graph. The nodes represent users (Alice, Bob, Charlie, Dave, and Eve), and the edges represent their friendships, highlighting the interconnected relationships within the network. NEUST - College of Information and Communications Technology  7 1.4 Characteristics of Data Structures Each data structure has unique characteristics that make it suitable for specific types of applications and operations. Understanding the advantages and disadvantages of different data structures is crucial for selecting the appropriate one for a given task. This guide provides a detailed comparison of several common data structures, including arrays, ordered arrays, stacks, queues, linked lists, binary trees, and graphs, highlighting their benefits and limitations in various practical settings. By examining these characteristics, we can better appreciate the trade-offs involved in data structure selection and application. Table 1. Characteristics of Data Structures Data Structure Advantages Disadvantages Array Quick inserts Slow search Fast access if index known Slow deletes Fixed size Ordered Array Faster search than unsorted array Slow inserts Slow deletes Fixed size Stack Last-in, first-out access Slow access to other items Queue First-in, first-out access Slow access to other items Linked List Quick inserts Slow search Quick deletes Tuple heterogeneous values Fixed size Dictionary Fast search Unordered Tree Quick search Deletion algorithm is complex Quick inserts Quick deletes (If the tree remains balanced) Graph Best models real-world situations Some algorithms are slow and very complex Arrays are advantageous for their quick inserts and fast access if the index is known, as accessing elements in an array has a time complexity of O(1). However, they suffer from slow searches and deletes, with O(n) time complexity for each, due to the need to check or shift elements. Additionally, arrays have a fixed size, necessitating the creation of a new array and copying elements when resizing is required, which is inefficient. Bauat R, and Bauat M. (2024). Data Structures and Algorithms: A Comprehensive Learning Module for C++ Programming. Nueva Ecija University of Science and Technology. 8 Ordered arrays improve search efficiency compared to unsorted arrays by allowing binary search, reducing search time to O(log n). Despite this advantage, ordered arrays still have slow inserts and deletes, both requiring O(n) time due to the need for shifting elements to maintain order. They also share the fixed size limitation of regular arrays. Stacks operate on a last-in, first-out (LIFO) principle, offering efficient access to the most recently added element. Operations like push and pop are very fast, with O(1) time complexity. However, accessing elements other than the top one is slow and inefficient, as it requires removing elements from the stack. Queues, following a first-in, first-out (FIFO) principle, provide efficient access to the oldest added element, making enqueue and dequeue operations very fast with O(1) time complexity. Similar to stacks, accessing elements other than the front is slow and inefficient. Linked lists excel in quick inserts and deletes, especially at the beginning or end of the list, with both operations having O(1) time complexity if the node to be modified is known. However, searching for an element in a linked list is slow, requiring traversal from the head to the desired node, resulting in O(n) time complexity. Binary trees, particularly balanced ones, offer efficient search, insert, and delete operations, each with O(log n) time complexity. However, the algorithm for deleting a node, especially one with two children, is complex and requires maintaining the tree's structure and balance. Graphs are versatile data structures that best model real-world situations, such as social networks and transportation networks, due to their ability to represent complex relationships and structures. Despite this versatility, some graph algorithms, such as finding the shortest path or traversing the graph, can be slow and computationally intensive, particularly for large graphs. These characteristics illustrate the trade-offs in choosing a data structure based on the specific requirements of a task, such as the need for fast access, efficient insertions, or modeling complex relationships. 1.5 Algorithms and their Practical Applications An algorithm is a step-by-step procedure or formula for solving a problem or completing a task. It consists of a finite set of instructions that, when followed, achieve a particular goal or solve a specific problem. Algorithms are fundamental building blocks in the field of computer science and information technology. They are defined as a sequence of well-defined instructions or steps to solve a specific problem or to perform a particular task. These procedures are designed to be unambiguous and to produce a desired outcome or a solution to a problem. In computer science, an algorithm is a well-defined computational procedure that takes some input and produces some output. It is a sequence of computational steps that transform the input into the output. An algorithm is like a recipe or a set of directions for carrying out a task. Just as a recipe outlines the steps to make a dish, an algorithm outlines the steps to achieve a result. NEUST - College of Information and Communications Technology  9 Technically, an algorithm is a finite set of operations that, when executed, yield a solution to a problem. Each operation is precise and unambiguous, ensuring that the algorithm can be implemented effectively in a programming language. Here is a list outlining the importance of algorithms: 1. Efficiency: Algorithms are essential for optimizing the performance of software and hardware systems. By implementing efficient algorithms, we can ensure that tasks are performed quickly and resource usage is minimized. This is crucial in environments where computational resources are limited or where tasks need to be completed in real-time. 2. Problem Solving: Algorithms provide a structured approach to problem-solving. They help in breaking down complex problems into manageable steps, making it easier to devise solutions. This step-by-step approach ensures that each aspect of the problem is addressed systematically. 3. Automation: Algorithms are the backbone of automation in computing. They enable computers to perform tasks automatically without human intervention. This is particularly important in fields such as robotics, artificial intelligence, and machine learning, where algorithms are used to make decisions, learn from data, and perform complex tasks. 4. Data Processing: In the era of big data, algorithms are indispensable for processing vast amounts of information efficiently. They are used in data mining, data analysis, and data visualization to extract meaningful insights from large datasets. Algorithms help in sorting, filtering, and summarizing data, making it easier to understand and utilize. 1.5.1 Characteristics of Algorithms 1. Definiteness: Each step of an algorithm must be clear and unambiguous. This ensures that the algorithm can be implemented precisely without any confusion or misinterpretation. 2. Finiteness: An algorithm must have a finite number of steps. It should eventually terminate after performing the desired task. This ensures that the algorithm will not run indefinitely and will produce a result within a reasonable amount of time. 3. Input: Algorithms may require zero or more inputs to produce an output. Inputs are the data that the algorithm processes to generate the desired outcome. 4. Output: An algorithm produces one or more outputs, which are the results of the processing steps. The output is the final product of the algorithm's execution. 5. Effectiveness: Each step of an algorithm must be simple enough to be carried out in a finite amount of time. This means that the operations performed in each step should be basic and feasible. 1.5.2 Types of Algorithms 1. Search Algorithms: Search algorithms are used to find specific data within a structure. Examples include Binary Search and Linear Search that are applicable for linear data structures. Bauat R, and Bauat M. (2024). Data Structures and Algorithms: A Comprehensive Learning Module for C++ Programming. Nueva Ecija University of Science and Technology. 10 2. Sorting Algorithms: Sorting algorithms are used to arrange data in a particular order (ascending or descending). Examples include Quick Sort, Merge Sort, and Bubble Sort. 3. Graph Algorithms: Graph algorithms are used to solve problems related to graph theory, such as finding the shortest path or detecting cycles. Examples include Depth-First Search (DFS), Breadth-First Search (BFS), and Dijkstra’s Algorithm. These algorithms will be discussed further in the succeeding units of this learning module. There are other Algorithms such as Dynamic Programming Algorithms, Greedy Algorithms, and Backtracking Algorithms. These algorithms are not included in this learning module for they are incorporated in another curriculum which contains topics for advanced algorithm. 1.5.3 Algorithms Real-World Applications 1. E-commerce: Algorithms power the recommendation systems in online shopping platforms, suggesting products based on user behavior and preferences. 2. Social Media: Algorithms are used to filter and prioritize content in social media feeds, ensuring users see the most relevant posts. 3. Navigation Systems: Pathfinding algorithms, like Dijkstra’s, are used in GPS navigation systems to find the shortest and most efficient routes. 4. Finance: Algorithms are employed in stock trading to analyze market trends and make trading decisions in milliseconds. 5. Healthcare: In medical diagnostics, algorithms analyze patient data to identify patterns and make predictions about potential health issues. 6. Robotics: Robots use algorithms for tasks such as object recognition, path planning, and autonomous decision-making. Understanding algorithms and their applications is crucial for developing efficient, reliable, and scalable solutions in computer science. They not only enhance the performance of systems but also enable automation and intelligent decision-making across various industries. As technology continues to evolve, the importance of algorithms in driving innovation and solving complex problems will only continue to grow. NEUST - College of Information and Communications Technology  11 UNIT 2. Selection Control Structures and Iterations This section provides a review of essential C++ programming concepts, focusing on control structures, iterations, recursion, and functions. Mastering these fundamental constructs is crucial for implementing various data structures and algorithms effectively. You need to revisit these concepts, emphasizing their application in more complex coding scenarios. Control structures, including if-else statements and switch cases, enable decision-making processes within programs. Iteration constructs such as for, while, and do-while loops facilitate repetitive tasks, ensuring code efficiency and simplicity. At the end of this lesson, the learners should be able to: ✓ identify the purpose and usage of different selection control in decision- making processes within programs. ✓ explain the concepts of iterations and their differences. ✓ evaluate and apply the simple and logical boolean expressions in selection controls and iterations. ✓ construct control flow using selection control and iterations in various programming scenarios. ✓ implement iteration constructs to handle repetitive tasks efficiently. 2.1 Selection Control Structures Control structures in C++ are constructs that dictate the flow of control through a program. They enable decision-making which are essential for creating dynamic and flexible applications. 2.1.1 The if Selection Control, Relational, Equality, and Logical Operators The if selection control structure allows a program to execute a block of code only if a specified condition is true. It is used to make decisions in the program flow, enabling conditional execution based on the evaluation of expressions. The basic syntax of an if statement in C++ is as follows: if (condition) { // Code Block: Code to execute if condition is true } An if statement in C++ is composed of several parts, each serving a specific purpose to enable conditional execution of code. The if keyword introduces the conditional statement. It tells the compiler that a decision is to be made based on a specified condition. Bauat R, and Bauat M. (2024). Data Structures and Algorithms: A Comprehensive Learning Module for C++ Programming. Nueva Ecija University of Science and Technology. 12 The condition is a boolean expression enclosed in parentheses (). This expression is evaluated to determine whether it is true or false. If the condition evaluates to true, the block of code following the if statement is executed. If it evaluates to false, the block of code is skipped. The code block, enclosed in curly braces {}, contains the statements that will be executed if the condition is true. This is also known as the body of the if statement. The code initializes an integer i with the value 5. It then uses an if statement to check if i is less than 10. SCAN FOR SOURCE CODE Since 5 is less than 10, the condition is true, and the program prints “5 is less than 10” to the console. Therefore, the statements inside if will be executed if and only if the boolean expression is true. How can we check if the condition inside if parenthesis is true? You should refer to the table below to assess the Boolean expression of the if condition. Table 2. The Relational, and Equality Operators Standard algebraic C++ equality Example Meaning of equality operator or or relational of C++ C++ condition relational operator operator condition Relational operators > > x > y x is greater than y < < x < y x is less than y  >= x >= y x is greater than or equal to y  = 13). Finally, if none of the conditions for adult or teenager are met, the person is categorized as a child. This structure allows the program to handle multiple conditions in a hierarchical manner. int age; cout > age; An integer variable age is declared to store the user's input. The user is prompted to enter their age, which is then read and stored in the variable age. First if Statement: if (age >= 18) { This statement checks if age is greater than or equal to 18. If this condition is true, the program enters the block of code following this if. Nested if Statement Inside the First if Block: if (age >= 60) { cout = 13) { cout