V.M.Prabhakaran, Department of CSE, KIT- Coimbatore Problem Solving and Python Programming 1
Definition • Algorithms are procedural solutions to problems. • These solutions are not answers but specific instructions for getting answers. Problem Solving and Python Programming 2
Techniques are, • Understanding the problem • Ascertain the capabilities of the computational device • Exact/approximate solution • Decide on the appropriate data structure • Algorithm design technique • Methods of specifying an algorithm • Proving an algorithm correctness • Analyzing an algorithm • Coding an algorithm Problem Solving and Python Programming 3
Algorithm design and Analysis process Problem Solving and Python Programming 4
1.Understanding the problem • The Problem given should be understood properly. • Creating an algorithm is an art which may never be fully automated. • An input to an algorithm specifies an instance of the problem the algorithm solves. • Correct algorithm should work for all possible inputs. Problem Solving and Python Programming 5
2. Ascertain the capabilities of the computational device • The second step is to ascertain the capabilities of a machine. • This can be done by knowing the type of the architecture, speed and memory availability. • Computational device of the algorithm is intended for sequential algorithms and parallel algorithms. Problem Solving and Python Programming 6
3. Exact/approximate solution • Once algorithm is devised, it is necessary to show that it compute answer for all the possible inputs. • The solution is stated in two forms: • Solving the problem exactly is called an Exact solution • Solving it approximately is called approximate solution. • Examples: Finding a square root of number Problem Solving and Python Programming 7
4. Decide on the appropriate data structure • Data structures remain important for both design and analysis of algorithms. • Data structures can be defined as a particular scheme of organizing related data items. • Some of the elementary data structures are arrays, lists, set. • Algorithm + Data Structure= Programs Problem Solving and Python Programming 8
5. Algorithm design technique • General approach to solving problem algorithmically that is applicable to a variety of problems from different areas of computing. • Some important design techniques are, – Brute force – Greedy method – Divide and conquer – Dynamic programming – Backtracking – Linear programming Problem Solving and Python Programming 9
6. Methods of specifying an algorithm • There are mainly two options for specifying an algorithm, – Use of natural language – Pseudo code and Flowcharts Problem Solving and Python Programming 10
7. Proving an algorithm correctness • Correctness has to be proved for every algorithm. • To prove that the algorithm yields a required result for every legitimate input in a finite amount of time. • A proof of correctness requires that the solution to be stated in two forms : Assertions that deals about input and output variables of the program and Specifications that is expressed in predicate calculus. Problem Solving and Python Programming 11
8. Analyzing an algorithm • There are two kinds of algorithm efficiency: time and space efficiency. • Time Efficiency : Indicates how fast the algorithm runs. • Space Efficiency : Indicates how much extra memory the algorithm needs. • Simpler algorithms are easier to understand and program, the resulting programs will be easier to debug. Problem Solving and Python Programming 12
9. Coding an algorithm • Program the algorithm by using programming language. • Formally verification is done through small programs. • Validity is done through testing and debugging. • A good algorithm is a result of repeated effort and work. Problem Solving and Python Programming 13

Algorithmic problem solving

  • 1.
    V.M.Prabhakaran, Department of CSE, KIT-Coimbatore Problem Solving and Python Programming 1
  • 2.
    Definition • Algorithms areprocedural solutions to problems. • These solutions are not answers but specific instructions for getting answers. Problem Solving and Python Programming 2
  • 3.
    Techniques are, • Understandingthe problem • Ascertain the capabilities of the computational device • Exact/approximate solution • Decide on the appropriate data structure • Algorithm design technique • Methods of specifying an algorithm • Proving an algorithm correctness • Analyzing an algorithm • Coding an algorithm Problem Solving and Python Programming 3
  • 4.
    Algorithm design andAnalysis process Problem Solving and Python Programming 4
  • 5.
    1.Understanding the problem •The Problem given should be understood properly. • Creating an algorithm is an art which may never be fully automated. • An input to an algorithm specifies an instance of the problem the algorithm solves. • Correct algorithm should work for all possible inputs. Problem Solving and Python Programming 5
  • 6.
    2. Ascertain thecapabilities of the computational device • The second step is to ascertain the capabilities of a machine. • This can be done by knowing the type of the architecture, speed and memory availability. • Computational device of the algorithm is intended for sequential algorithms and parallel algorithms. Problem Solving and Python Programming 6
  • 7.
    3. Exact/approximate solution •Once algorithm is devised, it is necessary to show that it compute answer for all the possible inputs. • The solution is stated in two forms: • Solving the problem exactly is called an Exact solution • Solving it approximately is called approximate solution. • Examples: Finding a square root of number Problem Solving and Python Programming 7
  • 8.
    4. Decide onthe appropriate data structure • Data structures remain important for both design and analysis of algorithms. • Data structures can be defined as a particular scheme of organizing related data items. • Some of the elementary data structures are arrays, lists, set. • Algorithm + Data Structure= Programs Problem Solving and Python Programming 8
  • 9.
    5. Algorithm designtechnique • General approach to solving problem algorithmically that is applicable to a variety of problems from different areas of computing. • Some important design techniques are, – Brute force – Greedy method – Divide and conquer – Dynamic programming – Backtracking – Linear programming Problem Solving and Python Programming 9
  • 10.
    6. Methods ofspecifying an algorithm • There are mainly two options for specifying an algorithm, – Use of natural language – Pseudo code and Flowcharts Problem Solving and Python Programming 10
  • 11.
    7. Proving analgorithm correctness • Correctness has to be proved for every algorithm. • To prove that the algorithm yields a required result for every legitimate input in a finite amount of time. • A proof of correctness requires that the solution to be stated in two forms : Assertions that deals about input and output variables of the program and Specifications that is expressed in predicate calculus. Problem Solving and Python Programming 11
  • 12.
    8. Analyzing analgorithm • There are two kinds of algorithm efficiency: time and space efficiency. • Time Efficiency : Indicates how fast the algorithm runs. • Space Efficiency : Indicates how much extra memory the algorithm needs. • Simpler algorithms are easier to understand and program, the resulting programs will be easier to debug. Problem Solving and Python Programming 12
  • 13.
    9. Coding analgorithm • Program the algorithm by using programming language. • Formally verification is done through small programs. • Validity is done through testing and debugging. • A good algorithm is a result of repeated effort and work. Problem Solving and Python Programming 13