<h5 id="41-introduction">4.1 INTRODUCTION</h5> <ul> <li>The text begins with an introduction to the pervasive use of computers in daily life, highlighting their role in simplifying complex tasks such as railway reservation.</li> <li>The concept of “computerisation” is explained as the use of computers to develop software for efficient automation of routine human tasks.</li> <li>Problems solving is identified as an essential skill for computer science students, with the clarification that computers themselves do not solve problems, but require precise instructions in the form of algorithms and programs.</li> <li>The problems solving process is defined as identifying a problem, developing an algorithm, and implementing the algorithm to create a computer program.</li> <li>The principle of GIGO (Garbage In Garbage Out) is mentioned, emphasizing the dependence of correct computer output on correct input.</li> <li>A quote from A. Aho and J. Ullman is included, defining Computer Science as the science of abstraction, creating the right model for a problem and devising appropriate mechanizable techniques to solve it.</li> </ul> <p>======</p> <h5 id="42-steps-for-problem-solving">4.2 Steps for Problem Solving</h5> <ul> <li>Problem solving can consist of multiple steps, especially for complex problems.</li> <li>The key steps for solving a problem using a computer are: <ol> <li>Identifying the problem: Clearly define and understand the problem that needs to be solved.</li> <li>Planning the solution: Develop a strategy or plan to solve the problem.</li> <li>Implementing the solution: Write a program or software based on the plan.</li> <li>Testing the solution: Check if the program or software correctly solves the problem.</li> <li>Evaluating the solution: Analyze the performance and efficiency of the solution.</li> <li>Documenting the solution: Record the problem, solution, and process for future reference.</li> </ol> </li> </ul> <p>======</p> <h5 id="421-analysing-the-problem">4.2.1 Analysing the problem</h5> <ul> <li>Carefully reading and analyzing the problem statement is crucial to understanding the problem that needs to be solved.</li> <li>The main components of the problem should be listed, and the core functionalities that the solution should have should be decided.</li> <li>Analyzing the problem helps in determining the inputs that the program should accept and the outputs that it should produce.</li> <li>An algorithm is a set of exact steps that, when followed, solve the problem or accomplish the required task.</li> <li>An algorithm is essential to have a clear and systematic approach to developing a solution.</li> </ul> <p>======</p> <h5 id="422-developing-an-algorithm">4.2.2 Developing an Algorithm</h5> <ul> <li>An algorithm is a solution to a problem, represented in natural language, which is then converted into program code.</li> <li>It is developed through a process of refining a tentative solution plan.</li> <li>Multiple algorithms can be possible for a single problem, and the most suitable one must be selected.</li> <li>The development of an algorithm involves defining clear steps, similar to a well-written recipe.</li> <li>The discussion of the algorithm is presented in the following section 4.3.</li> </ul> <p>======</p> <h5 id="423-coding">4.2.3 Coding</h5> <ul> <li>After finalizing the algorithm, it needs to be converted into a format that can be understood by the computer.</li> <li>This is done through writing a program in a high-level programming language.</li> <li>The coding process and solution should be documented for future reference.</li> <li>This documentation is important when revisiting the programs at a later stage.</li> <li>Details about coding are provided in section 4.8.</li> </ul> <p>======</p> <h5 id="424-testing-and-debugging">4.2.4 Testing and Debugging</h5> <ul> <li> <p>Testing is a crucial step in programming to ensure that the program meets user requirements, responds within expected time, and generates correct output for all possible inputs.</p> </li> <li> <p>Standardized testing methods like unit, integration, system, and acceptance testing are followed in the software industry to ensure that the software works as expected and meets all business and technical requirements.</p> </li> <li> <p>Errors or defects found in testing phases are debugged or rectified, and the program is retested until all errors are removed.</p> </li> <li> <p>Maintenance of a software application involves fixing problems, answering user queries, and serving requests for addition or modification of features even after delivery to the user.</p> </li> <li> <p>The term “Algorithm” originated from the Latin translation of the name of Persian astronomer and mathematician, Abu Abdullah Muhammad ibn Musa Al-Khwarizmi (c. 850 AD).</p> </li> </ul> <p>======</p> <h5 id="43-algorithm">4.3 ALGORITHM</h5> <ul> <li>An algorithm is a defined sequence of steps that leads to the desired result in a finite amount of time.</li> <li>It has a definite beginning and end, and consists of a finite number of steps.</li> <li>Examples of activities that follow algorithms include getting ready for school, making breakfast, riding a bicycle, and solving a puzzle.</li> <li>In the given example, the algorithm is used to find the Greatest Common Divisor (GCD) of two numbers 45 and 54.</li> <li>The algorithm for finding the GCD involves finding the divisors of both numbers and then determining the largest common number from those lists. The GCD of 45 and 54 is 9.</li> </ul> <p>======</p> <h5 id="431-why-do-we-need-an-algorithm">4.3.1 Why do we need an Algorithm?</h5> <ul> <li>An algorithm is a roadmap or a set of instructions for a computer program.</li> <li>It is essential for increasing the reliability, accuracy, and efficiency of solutions.</li> <li>A good algorithm has the following characteristics: <ul> <li>Precision: The steps are precisely stated or defined.</li> <li>Uniqueness: Results of each step are uniquely defined and depend only on the input and preceding steps.</li> <li>Finiteness: The algorithm stops after a finite number of steps.</li> <li>Input: The algorithm receives some input.</li> <li>Output: The algorithm produces some output.</li> </ul> </li> <li>While writing an algorithm, it is crucial to identify the input, processing, and desired output.</li> </ul> <p>======</p> <h5 id="44-representation-of-algorithms">4.4 REPRESENTATION OF ALGORITHMS</h5> <ul> <li>Algorithms can be represented using two common methods: flowcharts and pseudocode.</li> <li>The representation should highlight the logic of the problem solution without including implementation details.</li> <li>It should clearly show the flow of control during the execution of the program.</li> <li>Both methods should include identifying the required input and desired output.</li> <li>The representation should not include examples and their solutions.</li> </ul> <p>======</p> <h5 id="441-flowchart--visual-representation-of-algorithms">4.4.1 Flowchart — Visual Representation of Algorithms</h5> <ul> <li>A flowchart is a visual representation of an algorithm, made up of boxes, diamonds, and other shapes, connected by arrows.</li> <li>Standardized symbols are used to draw flowcharts, such as oval for start/end, rectangle for process, diamond for decision, and parallelogram for input/output.</li> <li>An algorithm can be represented pictorially using a flowchart, as seen in the example of finding the square of a number.</li> <li>A flowchart can also be used to solve problems, such as a non-functioning light bulb, by breaking down the steps to identify the issue.</li> <li>If an algorithm does not stop after a finite number of steps, it can lead to an infinite loop, causing the process to continue indefinitely.</li> </ul> <p>======</p> <h5 id="442-pseudocode">4.4.2 Pseudocode</h5> <ul> <li>Pseudocode is a non-formal language used to represent algorithms in a human-readable format.</li> <li>Commonly used pseudocode keywords include INPUT, COMPUTE, PRINT, INCREMENT, DECREMENT, IF/ELSE, WHILE, and TRUE/FALSE.</li> <li>Pseudocode cannot be executed directly by a computer and has no specific standard for writing.</li> <li>Example: Sum of two numbers pseudocode: INPUT num1, INPUT num2, COMPUTE Result = num1 + num2, PRINT Result.</li> <li>Activity: Hockey match scoreboard pseudocode: INPUT TeamA, INPUT TeamB, INCREMENT Score[TeamA], DECREMENT Score[TeamB], PRINT Score.</li> <li>Benefit: Pseudocode helps programmers represent the basic functionality of a program and safeguards against leaving out important steps.</li> </ul> <p>======</p> <h5 id="45-flow-of-control">4.5 FLOW OF CONTROL</h5> <ul> <li>The flow of control represents the sequence of events in a program.</li> <li>It can be depicted using a flowchart.</li> <li>The flow of events can be sequential, based on a decision, or repetitive.</li> <li>Sequential flow means events follow in a straight line.</li> <li>Decision-based flow allows events to branch based on conditions.</li> <li>Repetitive flow allows events to repeat for a finite number of times.</li> </ul> <p>======</p> <h5 id="451-sequence">4.5.1 Sequence</h5> <ul> <li>The default execution of statements in an algorithm is in sequence, where each step is executed one after the other.</li> <li>However, there are situations where statements need to be repeated or executed based on specific conditions.</li> <li>This section focuses on creating algorithms that can handle such scenarios.</li> <li>The algorithm may require executing certain tasks repeatedly (referred to as loops) or altering the flow of execution based on specific conditions (referred to as conditional statements).</li> <li>These concepts will be explored in detail in subsequent sections.</li> </ul> <p>======</p> <h5 id="452-selection">4.5.2 Selection</h5> <ul> <li>The process of decision making in real life can be illustrated with the help of maps and routes, as seen in Figure 4.6.</li> <li>Conditionals are used in programming to check possibilities and select one of the alternatives based on the outcome of a condition, as shown in examples (i) and (ii).</li> <li>Conditionals can be written in algorithms using if-then-else blocks, as demonstrated in Example 4.5, where a number is checked for even or odd.</li> <li>Multiple conditions can be checked using nested if-else blocks, as shown in Example 4.6, where a person’s age is used to categorize them as a child, teenager, or adult.</li> <li>In programming, the ’else’ keyword is used to represent the steps to be taken when a condition is not fulfilled, as seen in Example 4.5 and the card game example (Dragons and Wizards).</li> </ul> <p>======</p> <h5 id="453-repetition">4.5.3 Repetition</h5> <ul> <li>Repetition in programming is known as iteration or loop, where a section of code is executed repeatedly until a specified condition is met.</li> <li>In the given text, two types of loops are discussed: count-controlled loops and condition-controlled loops. <ol> <li>Count-controlled loops: These are loops with a predetermined number of iterations. Example 4.8 calculates the average of 5 numbers using a count-controlled loop.</li> <li>Condition-controlled loops: These are loops that repeat until a specific condition is met. Example 4.9 calculates the average of numbers entered by the user until 0 is entered, using a condition-controlled loop.</li> </ol> </li> <li>The pseudocode for count-controlled loops includes a counter that keeps track of the number of iterations. After each iteration, the value of the counter is incremented until it reaches the desired number of repetitions.</li> <li>The pseudocode for condition-controlled loops checks for a specific condition in each iteration. The loop continues to execute as long as the condition is true.</li> <li>Examples of daily activities with repetition include: A. Brushing your teeth twice a day B. Washing your hands multiple times a day C. Taking a certain number of steps while walking or jogging.</li> </ul> <p>======</p> <h5 id="46-verifying-algorithms">4.6 VERIFYING ALGORITHMS</h5> <ul> <li>Verification of algorithms is crucial in problem solving to ensure that the software works correctly in every situation.</li> <li>This is because faulty software can cause significant issues, especially in critical services like banking, medical field, or space shuttles.</li> <li>To verify an algorithm, we can take different input values and run them through the steps of the algorithm to check if the desired output is obtained for each input value.</li> <li>This process helps identify any incorrect steps in the algorithm and figure out missing details or specifics.</li> <li>For example, when verifying an algorithm to calculate the time taken to travel from place A to C via B, we may realize that the algorithm does not handle cases where the sum of minutes is greater than or equal to 60. Modifying the algorithm to account for this scenario ensures that it works correctly.</li> </ul> <p>======</p> <h5 id="47-comparison-of-algorithm">4.7 COMPARISON OF ALGORITHM</h5> <ul> <li>The problem of finding if a number is prime can be solved in multiple ways, with varying efficiency.</li> <li>Algorithm (i) checks for divisibility from 2 up to the number itself, which is time-consuming, especially for larger numbers.</li> <li>Algorithm (ii) improves upon (i) by only checking up to half the number, reducing processing time.</li> <li>Algorithm (iii) further reduces time complexity by checking divisibility only up to the square root of the number.</li> <li>Algorithm (iv) uses a pre-stored list of prime numbers to check for divisibility, reducing calculations but requiring additional memory.</li> <li>The efficiency of an algorithm can be measured in terms of time complexity (processing time) and space complexity (memory usage), with the choice of algorithm depending on the specific requirements of the task.</li> </ul> <p>======</p> <h5 id="48-coding">4.8 CODING</h5> <ul> <li>Coding is the process of writing an algorithm in a high-level programming language.</li> <li>Syntax is the set of rules that govern the formulation of statements in a programming language.</li> <li>High-level languages are easier to read, write, and maintain than low-level languages, but they are not directly understood by the computer hardware.</li> <li>A program written in a high-level language is called source code, which needs to be translated into machine language using a compiler or an interpreter.</li> <li>The choice of programming language depends on various factors such as the platform, the type of application, and the resources available.</li> </ul> <p>======</p> <h5 id="49-decomposition">4.9 DECOMPOSITION</h5> <ul> <li> <p>Decomposition is a problem-solving technique where a complex problem is broken down into smaller, more manageable sub-problems.</p> </li> <li> <p>This method is useful in designing different components of a system, such as the Railway Reservation System, which can then be made to work together effectively.</p> </li> <li> <p>Each sub-problem can be examined in detail, solved independently, and by different persons or teams, allowing for the assignment of specific sub-problems to teams of experts.</p> </li> <li> <p>Real-life applications of decomposition can be found in various fields, including mathematics, science, events management, weather forecasting, and delivery management systems.</p> </li> <li> <p>After solving the individual sub-problems, it is essential to test them for correctness and integrate them to obtain the complete solution.</p> </li> </ul> <p>======</p>