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

Divide and Conquer Strategy Divide and Conquer is a problem-solving strategy in which a large and complex problem is divided into smaller problems , each smaller problem is solved separately, and then the solutions are combined to obtain the solution to the original problem. Simple idea “Break a big problem into smaller problems, solve them, and combine the answers.” This strategy is especially important in algorithm design because many difficult problems become easier when we work with smaller pieces. The Three Steps Divide and Conquer generally has three stages : 1. Divide Break the original problem into smaller sub-problems . The smaller problems should be easier to handle and usually have the same nature as the original problem . Example: Suppose we have 1,000 books to organize. Instead of organizing all 1,000 books together: 1000 Books ↓ ┌───┼────┐ ↓ ↓ ↓ Fiction Non-fiction Reference We have divided one large problem into smaller problems. 2. Conquer Solve each...

 hese are two core techniques in Dynamic Programming (DP) , both used to optimize recursive or iterative algorithms by avoiding repeated work. 🧠 Memoization Memoization is a top-down technique. You start with the original recursive function When a subproblem is solved, you store its result (usually in a dictionary or list) If the same subproblem is needed again, you reuse the stored result instead of recomputing it ✔ Improves recursive efficiency ✔ Only solves subproblems that are actually needed Simple Example (Fibonacci) def fib ( n, memo={} ): if n in memo: return memo[n] if n <= 1 : return n memo[n] = fib(n- 1 , memo) + fib(n- 2 , memo) return memo[n] Key idea: Cache results of recursive calls. 📊 Tabulation Tabulation is a bottom-up technique. You build a table (often an array) iteratively Solve the smallest subproblems first Use those answers to build up to the final solution ✔ No recursion ...

Greedy Method of Problem Solving The Greedy Method is a problem-solving strategy in which we make the best-looking choice at the current step and continue making similar choices until the problem is solved. The important idea is: “Choose what looks best now, without worrying too much about future choices.” Once a choice is made, it is normally not changed or reconsidered . 1. How Does the Greedy Method Work? The greedy approach generally follows these steps: Identify the choices available. Choose the best option at the current moment. Accept the choice and do not change it later. Reduce the remaining problem. Repeat until the complete solution is obtained. Simple idea Problem ↓ Make the best choice NOW ↓ Reduce the problem ↓ Make the best choice NOW ↓ Reduce the problem ↓ Continue until solution is obtained 2. Real-Life Example – Choosing Coins Suppose you need to pay ₹87 using coins of: ₹25, ₹10, ₹5, ₹1 You want to use the minimum number of coins . ...

Password Guessing Using the Brute Force Method Password guessing using brute force is a simple example of the brute force problem-solving strategy . The basic idea is to systematically try every possible password combination until the correct one is found . 1. Basic Idea Suppose a system uses a 3-digit password , where each position can contain a digit from 0 to 9 . The possible passwords are: 000 001 002 003 ... 998 999 There are: 10 3 = 1000 10^3 = 1000 possible combinations. A brute-force approach checks these possibilities systematically. 000 → ✗ 001 → ✗ 002 → ✗ 003 → ✗ ... 527 → ✓ If the password is 527 , the search stops when 527 is reached. 2. How Does It Work? The process can be explained in four simple steps. Step 1: Identify the Possibilities Determine the possible characters and password length. For our example: Characters = 0–9 Password length = 3 Step 2: Generate Combinations Generate every possible combination: 000 001 002 ... 999 Step 3: Check Each Combinati...