FYCDS_Unit_5_ICPS_Notes

Introduction to problem solving

5.1 Concept: problem solving

Definition of problem

• It is an issue or obstacle which makes it difficult to achieve a desired goal ,objective or purpose.
• It refer to a situation, condition or issue that is yet unresolved.
• It is question or situation that motivates us to search for solution.

Definition of problem Solving

• The process of working through details of a problem to reach a solution.
• It is mental process that involving discovering, analyzing & solving problems
• It include:
• Understand the problem
• Plan a solution
• Carry out the plan
• Examine the result for accuracy

5.2 Steps in problem solving

Defining (identifying) the problem

• Most difficult & the most important of all the steps.
• Help to diagnosing the situation so that focusing on the real problem.

Gather Facts(Data):

• Define key terms
• Articulate Assumptions
• Discuss the problem with someone else
• Get the viewpoint of others

Generate alternate options:

• Representing problem we will select information(options) that is relevant including goal, initial state, operators & restrictions.
• Operators are actions that change the initial state of the problem into another
• Discuss the problem with someone else
• Categorize type of problem, develop similar situations, identify the criteria for evaluating.

Implement & Evaluate:

• Make a list of the different options that we generated, select one or more solutions options from near top of your list to try.
• Evaluations based on whether or not your goals are met.

Monitor the solution:

• Re-apply measurements to confirm that change has taken place.
• Ensure that the change do not negatively impact another area.
• Provide sufficient information & training so that change can be sustained.

5.3 Problem solving techniques

Trial & error technique



• Trial and error is a problem solving method in which multiple attempts are made to reach a solution.
• It is a basic method of learning that essentially all organisms (things) use to learn new behaviors. Trial and error is trying a method, observing if it works, and if it doesn't trying a new method.
• This process is repeated until success or a solution is reached.
• Easy to implement
• Time consuming because of need to run each & every test.



Brainstorming technique



• Brainstorming is a group creativity technique by which efforts are made to find a conclusion for a specific problem by gathering a list of ideas contributed by its members.
• Easy to understand, inexpensive, generate idea & solutions.
• Participants have to listen idea & have to spend more time to sharing their ideas till they are noticed by others.



Divide & conquer technique



• The approach divides the bigger problem into smaller subproblems, and the solution to the original large problem is achieved by combining the solutions to the smaller subproblems.
• General Strategy for Divide and Conquer:
• Divide: Divide the problem into smaller sub-problems.
• Solve: Sub-problems are solved independently.
• Combine: Combine sub problem solutions in order to deduce the answer to the original large problem.
• Solving difficult problems, algorithm efficiency.
• Complicated for simple problems

5.4 Algorithms and Flowcharts (Definitions, Symbols)

Algorithms:

• A set of instructions for solving a problem.
• Step-by-step procedure for solving a particular problem is an algorithm
• Step-by-step solution to a problem.

5.5 Characteristics of an Algorithm:

• Input: Must have zero or more input.
• Output: Must produce one output at least.
• Definiteness: Each instruction must be clear & distinct.
• Finiteness: Must terminate after a finite number of steps.
• Effectiveness: Each operation must be definite (fixed) also it should be feasible.

Advantages:

• It give language independent layout of the program.
• It simple & easy to understand.
• It is to debug as every step is got its own logical sequence.
• It is easy to first develop algorithm & then convert into a flowchart & then into a computer program.

Disdvantages:

• Time Consuming
• Cumbersome

Flowchart:

• It is symbolic representation of a solution to give task problem.
• Graphical representation of a process is called as flowchart
• Pictorial representation of algorithm.

Advantages:

• Proper documentation
• Efficient coding
• Proper Debugging
• Effective Analysis

Disdvantages:

• Loss of technical detail
• Time Consuming
• Alteration & modification
• Complex Logic

Flowchart Symbols

5.6 Conditionals in pseudo-code

Pseudo-code is a way to express algorithms in a language-independent, human-readable format. It's used to outline the logic of a program without getting into the specifics of a particular programming language syntax.

Here's how you might write conditional statements in pseudo-code:

1. If Statement:


The basic structure of an if statement in pseudo-code is as follows:
if condition then
           // Code to execute if the condition is true
end if

Here's an example using pseudo-code to express an if statement:
if temperature > 30 then
           display "It's a hot day!"
end if

2. If-Else Statement:


An if-else statement in pseudo-code allows you to handle both the true and false conditions:
if condition then
           // Code to execute if the condition is true
else
           // Code to execute if the condition is false
end if

Here's an example using pseudo-code to express an if statement:
if temperature > 30 then
           display "It's a hot day!"
else
           display "It's a Cold day!"
end if

5.7 Loops in pseudo code

1. For Loop:

A for loop is used to repeat a block of code for a specific number of iterations. The basic structure of a for loop in pseudo-code is as follows:

Syntax:
for variable = start_value to end_value do
           // Code to be repeated
end for


Example:

for i = 1 to 10 do
           display i
end for


2. While Loop:

A while loop repeats a block of code as long as a certain condition is true. The basic structure of a while loop in pseudo-code is as follows:
Syntax:
while condition do
           // Code to be repeated
end while


Example:

sum = 0
while sum < 100 do
           sum = sum + input_number
end while


3. Do-While Loop:

A do-while loop is similar to a while loop, but the condition is checked after the code block is executed, ensuring that the code block is executed at least once.
Syntax:
do
           // Code to be repeated
while condition


Example:

do
           display "Enter a positive number:"
           input number
while number <= 0

5.8 Algorithm Complexities

Complexity

• It is function of size of input of a given problem instance which determines how much running time /memory space is needed by the algorithm in order to run to completion
• Analysis of the program requires two main considerations one is time complexity and other is space complexity
• The notation we used : big-O i.e. O(n)

Time Complexity

• It measures program or algorithm is take the amount of computer time that it needs to run to completion.
• Example
• Algorithm 1:
  a=a+1
Frequency count algorithm 1 is 1.

• Algorithm 2:
  for x=1 to n
  a=a+1
Frequency count algorithm 2 is n.
• Algorithm 3:
  for x=1 to n
  for y=1 to n
  a=a+1
• Frequency count algorithm 3 is n*n=n2.

Algorithm Analysis

Best Case Time Complexity

• It is measure of the minimum time that algorithm will require for an input of size ‘n’.
Worst Case Time Complexity

• It is measure of the maximum time that algorithm will require for an input of size ‘n’.
Average Case Time Complexity

• Comes under between Best Case Time Complexity & Worst Case Time Complexity

Big-O Notation

Big O notation is a mathematical notation used in computer science and mathematics to describe the performance or complexity of algorithms. It provides a way to analyze how the runtime or resource usage of an algorithm scales with the size of the input data.
In essence, Big O notation describes the upper bound of an algorithm's efficiency. It helps programmers and computer scientists compare different algorithms and make informed decisions about which algorithm to use for a particular problem based on its time and space complexity.
The notation uses the letter "O" followed by a function that represents the upper bound of an algorithm's growth rate. Here are some common Big O notations and their meanings:
O(1) - Constant Time: The algorithm's runtime or resource usage remains constant regardless of the input size. It's the most efficient scenario.
O(log n) - Logarithmic Time: The algorithm's runtime increases logarithmically with the input size. Commonly seen in algorithms that divide the input space in half with each step, like binary search.
O(n) - Linear Time: The algorithm's runtime grows linearly with the input size. As the input grows, the runtime also grows proportionally.
O(n log n) - Linearithmic Time: Commonly seen in more efficient sorting algorithms like mergesort and heapsort.
O(n^2) - Quadratic Time: The algorithm's runtime is proportional to the square of the input size. Often seen in algorithms with nested loops.
O(n^k) - Polynomial Time: The algorithm's runtime is proportional to a polynomial of the input size. Higher powers indicate worse performance.
O(2^n) - Exponential Time: The algorithm's runtime doubles with each increase in input size. Often seen in brute-force algorithms.
O(n!) - Factorial Time: The algorithm's runtime increases by a factorial with the input size. Extremely inefficient for large inputs.

5.9 Simple Examples: Algorithms and flowcharts (Real Life Examples)

Example : Determine number is even or odd




Algorithm

• Step 1: Start
• Step 2: Read a number to N
• Step 3: Divide the number by 2 and store the remainder in R.
• Step 4: If R = O Then go to Step 6
• Step 5: Print “N is odd” go to step 7
• Step 6: Print “N is even”
• Step 7: Stop



Flowchart