Problem Solving Techniques with C - Algorithm & Flowchart PDF

UNIT I Problems and Problem Instances:  Problem: A problem is a broad or general task that defines what needs to be solved. It does not include specific inputs or instances but focuses on the overall goal. Example: "Sort a list of numbers" is a problem where the goal is to a...

UNIT I Problems and Problem Instances:  Problem: A problem is a broad or general task that defines what needs to be solved. It does not include specific inputs or instances but focuses on the overall goal. Example: "Sort a list of numbers" is a problem where the goal is to arrange numbers in ascending or descending order.  Problem Instance: It provides actual data or input for the problem, which makes it possible to apply a solution or algorithm. Example: For the sorting problem, an instance could be a list like [5, 2, 9, 1]. Solving this instance involves arranging these numbers into [1, 2, 5, 9]. In summary, the problem sets the overall goal, while the problem instance gives specific data to apply a solution and achieve that goal. 1 -Runali Mali Generalization and Special Cases 1. Generalization: o Making a problem or solution applicable to a wider range of inputs or scenarios. Example: A sorting algorithm that works on numbers, strings, or dates, not just integers. 2. Special Cases: o Focusing on a specific version or condition of the problem. Example: Sorting only positive integers or sorting an already sorted list. Difference: In summary, Generalization Broadens the scope to cover more situations. And Special Cases Narrows the focus to specific situations. 2 -Runali Mali Computational Problems: A computational problem is a problem that can be solved step-by-step with a computer. A computational problem refers to a task that can be described using computational steps to produce an answer. These problems require algorithms to process data and derive a solution based on the input provided. The key objective is to develop an efficient solution using a programming language like C. In problem-solving techniques using C, the computational problem is broken down into manageable steps, and the solution is implemented through logical programming constructs like loops, conditions, and functions. Here are some types of computational problems: 1. Decision Problems Problems that require a Yes/No answer. Example: Is a number prime? 2. Search Problems Problems that involve finding specific data or information from a collection. Example: Searching for a specific key in a search tree. 3. Sorting Problems Problems that involve arranging data in a specific order, such as ascending or descending. Example: Sorting student grades in ascending order. 4. Numerical Problems Problems involving mathematical computations or numeric data. Example: Calculating the square root of a number. 3 -Runali Mali Classification and Analysis of Problems: In problem-solving using C programming, understanding how problems are classified and analyzed is crucial for selecting the appropriate algorithm and structuring the solution efficiently. This process helps to break down complex problems into manageable sub-problems and ensures that the problem is addressed systematically. Classification of Problems: Problem classification refers to categorizing problems based on their characteristics, which helps in selecting suitable approaches and techniques. Below are common classifications used in problem-solving: 1. Based on Problem Nature Well-defined Problems: These are problems that have a clear set of rules and goals. The input, output, and the relationship between them are explicitly specified. Examples include mathematical problems (e.g., calculating the factorial of a number), sorting, searching, etc. 2. Based on the Type of Output 1. Decision Problems: These problems yield a binary outcome (Yes/No). They test if a particular condition is met based on the given input. Example: Checking if a number is prime or not. 2. Search Problems: These problems involve searching for a specific element or solution from a collection of items or data. Example: Searching for a number in an unsorted array. 3. Based on Problem Size Small Scale Problems: These problems are simple and can be solved directly with basic algorithms. Example: small arrays or simple mathematical operations. Large Scale Problems: These problems require more advanced algorithms due to the complexity and size of the data. They often involve optimization techniques, dynamic programming, or divide-and-conquer methods. 4 -Runali Mali Analysis of Problems: Problem analysis is the process of understanding a problem thoroughly to design an efficient and effective solution. In C programming, this involves identifying the problem's requirements, constraints, and possible solutions. The process ensures the code meets the problem's objectives efficiently. Steps in Problem Analysis 1. Understand the Problem Grasp the problem statement clearly. Break the problem into input, process, and output. Example: Problem: Calculate the factorial of a number. Input: An integer n. Output: A single integer, n!. 2.Identify Inputs and Outputs Input: Define the types and structure of data. Output: Specify the desired result and format. Example: For factorial: Input: Integer n (e.g., n = 5). And Output: Integer result (e.g., 5! = 120). 3. Break the Problem into Sub-Problems Decompose the problem into manageable steps or sub-problems. Example: Sub-problems for calculating factorial: 1. Check if the input is valid (non-negative integer). 2. Compute the product of all numbers from 1 to n. 3. Return the result. 4. Analyze Constraints and Edge Cases Identify the constraints: o Input size and Data types (e.g., int, float, double). 5. Choose an Algorithm Select the algorithm that balances efficiency and simplicity. 5 -Runali Mali 6.Design the Solution Create a step-by-step plan or pseudocode. Divide the solution into modular functions for clarity and reusability. 7. Implement the Solution in C Convert the design into C code, ensuring: o Correct syntax. o Proper use of loops, conditionals, and functions. Steps for problem solving: When problems are straightforward and easy, we can easily find the solution. But a complex problem requires a methodical approach to find the right solution. In other words, we have to apply problem solving techniques. Problem solving begins with the precise identification of the problem and ends with a complete working solution in terms of a program or software In order to solve a problem by the computer, one has to pass though certain stages or steps. They are 1. Understanding the problem 2. Analyzing the problem 3. Developing the solution 4. Coding and implementation. 1. Understanding the problem: Here we try to understand the problem to be solved in totally. Before with the next stage or step, we should be sure about the objectives of the given problem. 2. Analyzing the problem: After understanding thoroughly the problem to be solved, we look different ways of solving the problem and evaluate each problem under consideration. The result of this stage is a broad overview of the sequence of operations that are to be carries out to solve the given problem. 3. Developing the solution: Here the overview of the sequence of operations that was the result of analysis stage is expanded to form a detailed step by step solution to the problem under consideration. 6 -Runali Mali 4. Coding and implementation: The last stage of the problem solving is the conversion of the detailed sequence of operations into a language that the computer can understand. Here each step is converted to its equivalent instruction or instructions in the computer language that has been chosen for the implantation. Input/Output Specification  Ensures clarity about what the program requires and what it delivers.  Helps in avoiding ambiguous or incorrect inputs/outputs. ensures clarity about: Data types. Formats. Ranges for inputs and outputs. Input Validation Input validation ensures that the program processes only valid and acceptable inputs. It prevents errors, crashes, and incorrect results. It Prevents unexpected behavior or crashes caused by invalid inputs. Ensures robustness by handling edge cases or invalid data gracefully. 1. Check Data Type: Ensure input matches the expected data type. Example: If expecting an integer, ensure the user doesn't input a character. 2. Check Value Range: Verify that the input falls within acceptable limits. Example: For factorial, ensure n >= 0. 3. Graceful Error Handling: Provide clear error messages and prevent further processing on invalid inputs. Pre and Post Conditions Pre and post-conditions define the requirements before and after executing a program or function to ensure correctness. Pre-Conditions 7 -Runali Mali  Requirements or assumptions that must be true before the execution of a function or program. Purpose: o To validate input data. o Ensure the program starts in a valid state. Examples: o Input to a factorial function must be n >= 0. Post-Conditions Requirements or guarantees about the state of the program after execution. Purpose: o Ensure the program produces the correct result. Examples: o Factorial function should return the correct factorial for valid input. 8 -Runali Mali  Algorithm: An algorithm is a sequence of steps to solve a particular problem or algorithm is an ordered set of unambiguous steps that produces a result and terminates in a finite time. An algorithm is a step-by-step problem solving procedure that can be carried out by a computer. Properties of Algorithm: It should terminate after a finite time. It should produce at least one output. It should take zero or more input. It should be deterministic means giving the same output for the same input case. Every step in the algorithm must be effective i.e. every step should do some work. Characteristics/ Features Input: An algorithm may or may not require input Output: Each algorithm is expected to produce at least one result Definiteness: Each instruction must be clear and unambiguous. Finiteness: If the instructions of an algorithm are executed, the algorithm should terminate after finite number of steps Effectiveness: All the operations used in the algorithm are basic (division, multiplication, comparison., etc.) and can be performed exactly in fixed duration of time. 9 -Runali Mali The algorithm and flowchart include following three types of control structures 1. Sequence: In the sequence structure, statements are placed one after the other and the execution takes place starting from up to down. 2. Branching (Selection): In branch control, there is a condition and according to a condition, a decision of either TRUE or FALSE is achieved. In the case of TRUE, one of the two branches is explored; but in the case of FALSE condition, the other alternative is taken. Generally, the ‘IF- THEN’ is used to represent branch control 3. Loop (Repetition): The Loop or Repetition allows a statement(s) to be executed repeatedly based on certain loop condition e.g. WHILE, FOR loops. HOW TO WRITE ALGORITHMS Step 1 Define your algorithms input: Many algorithms take in data to be processed, e.g. to calculate the area of rectangle input may be the rectangle height and rectangle width. Step 2 Define the variables: Algorithm's variables allow you to use it for more than one place. We can define two variables for rectangle height and rectangle width as HEIGHT and WIDTH (or H & W). We should use meaningful variable name e.g. instead of using H & W use HEIGHT and WIDTH as variable name. Step 3 Outline the algorithm's operations: Use input variable for computation purpose, e.g. to find area of rectangle multiply the HEIGHT and WIDTH variable and store the value in new variable (say) AREA. An algorithm's operations can take the form of multiple steps and even branch, depending on the value of the input variables. Step 4 Output the results of your algorithm's operations: In case of area of rectangle output will be the value stored in variable AREA. if the input variables described a rectangle with a HEIGHT of 2 and a WIDTH of 3, the algorithm would output the value of 6. 10 -Runali Mali  Flowchart: Flowchart is diagrammatic /Graphical representation of sequence of steps to solve a problem. Once the flowchart is complete, it becomes very easy for programmers to write the program from the starting point to the ending point. Since the flowchart is a detailed representation of the program logic no step is missed during the actual program writing resulting in error free programs. Such programs can also be developed faster. -A flowchart being a pictorial representation of a program, makes it easier forthe programmer to explain the logic of the program to others rather than a program Advantages of flowchart: Flowchart is an excellent way of communicating the logic of a program. Easy and efficient to analyze problem using flowchart. During program development cycle, the flowchart plays the role of a blueprint, which makes program development process easier. After successful development of a program, it needs continuous timely maintenance during the course of its operation. The flowchart makes program or system maintenance easier. It is easy to convert the flowchart into any programming language code. 11 -Runali Mali  Symbol Name Symbol function Used to represent start and end Oval of flowchart Used for input and output Parallelogram operation Processing: Used for Rectangle arithmetic operations and data-manipulations Decision making. Used to represent the operation in Diamond which there are two/three alternatives, true and false etc Flow line Used to indicate Arrows the flow of logic by connecting symbols Circle Page Connector 12 -Runali Mali  1. Sequence Algorithm & Flowchart to find Simple Interest P : Principle Amount N : Time in Years R : % Annual Rate of Interest SI : Simple Interest Algorithm Step 1:Start Step 2: Read the three input quantities’ P, N and R. Step 3 : Calculate simple interest as Simple interest = P* N* R/100 Step 4: Print simple interest. Step 5: Stop 13 -Runali Mali  14 -Runali Mali  2. Flowcharts for decision making/Branching : Algorihm: 1. Start 2. Declare variables m1, m2, m3. 3. Read marks of three subjects into m1, m2 and m3. 4. If m1 >= 35 and m2 >= 35 and m3 >= 35 print Pass. Otherwise goto step 5. 5. Print Fail. 6. Stop 15 -Runali Mali  16 -Runali Mali  3. Flowcharts for loops 17 -Runali Mali Draw a flowchart for sum of first n natural numbers. Step 1: Start 3Step 2: Read number n Step 3: Declare sum to 0 and i to 1 Step 4: Repeat steps 5 to 7 until i