Algorithmic Thinking with Python KTU BTech S1 UCEST 105 2024 scheme - Dr Binu V P

Brute Force Method of Problem Solving The Brute Force method is one of the simplest problem-solving strategies in algorithmic thinking. It means trying all possible solutions systematically until the correct solution is found . In simple words: “Don’t use shortcuts. Try every possible option and check which one works.” It is easy to understand and implement, but it can become very slow when the number of possibilities is large . 1. Basic Idea Suppose you have a problem with several possible solutions. A brute force approach does the following: Generate a possible solution ↓ Check whether it is correct ↙ ↘ Yes No ↓ ↓ Stop Try next possibility ↓ Repeat It continues until: a required solution is found, or all possibilities have been examined. 2. Simple Real-Life Example: Finding a Book Suppose there are 100 books on a shelf and you are looking for a particular book. Using a b...

Introduction to Computational Approaches to Problem Solving Many real-world problems are large, complex, and difficult to solve manually . Examples include finding the shortest route between cities, organizing thousands of records, scheduling college examinations, searching large databases, or selecting the best combination of resources. Computers can solve such problems efficiently by following systematic computational approaches . A computational approach to problem solving is a systematic way of using algorithms, data, and computing power to analyze a problem and find a suitable solution. Instead of trying to solve every problem in the same way, different approaches are chosen depending on the nature of the problem. Some problems can be solved by simply trying every possible solution . This is known as the brute-force approach . Other problems can be made easier by dividing them into smaller problems , as in the divide-and-conquer approach . When the same smaller problems occur...

  Recursion vs Dynamic Programming Aspect Recursion Dynamic Programming (DP) Basic Idea Solves a problem by breaking it down into smaller sub-problems, often leading to repeated calculations of the same sub-problems. Solves a problem by breaking it down into smaller sub-problems, but stores the results of these sub-problems to avoid redundant calculations. Overlapping Sub-Problems Sub-problems are often recalculated multiple times because results are not stored. Sub-problems are solved once and their results are stored (usually in a table) for reuse. Optimal Substructure Can be used if the problem exhibits optimal substructure, but does not explicitly take advantage of it unless combined with memoization. Explicitly takes advantage of optimal substructure by building up the solution from the smallest sub-problems. Time Complexity Can be exponential in many cases (e.g., O(2^n) for Fibonacci) due to repeated calculations. Often reduces time complexity to polynomial (e.g., O(n) for Fi...

Dynamic Programming  Dynamic Programming (DP) is an important problem-solving strategy in algorithmic thinking. It is mainly used when a problem can be divided into smaller sub-problems , and the same sub-problems occur repeatedly. The central idea is: Solve each sub-problem only once, store its result, and reuse it whenever needed. A simple way  to remember DP is: DP = Divide the problem + Solve the subproblem + Remember the answers 1. Why Do We Need Dynamic Programming? Consider the Fibonacci sequence: 0 ,   1 ,   1 ,   2 ,   3 ,   5 ,   8 ,   13 , … The Fibonacci numbers are defined as: 𝐹 ( 𝑛 ) = 𝐹 ( 𝑛 − 1 ) + 𝐹 ( 𝑛 − 2 ) For example: 𝐹 ( 5 ) = 𝐹 ( 4 ) + 𝐹 ( 3 ) A straightforward recursive solution repeatedly calculates the same values. F(5) / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) / \ F(2) F(1) Notice that...