Algorithmic Thinking with Python Module 3 PDF

ALGORITHMIC THINKING WITH PYTHON Module 3 CO3: Utilize effective algorithms to solve the formulated models and translate algorithms into executable programs. Syllabus SELECTION AND ITERATION USING PYTHON:- if-else, elif, for loop, range, while loop. Sequence data types...

ALGORITHMIC THINKING WITH PYTHON Module 3 CO3: Utilize effective algorithms to solve the formulated models and translate algorithms into executable programs. Syllabus SELECTION AND ITERATION USING PYTHON:- if-else, elif, for loop, range, while loop. Sequence data types in Python - list, tuple, set, strings, dictionary, Creating and using Arrays in Python (using Numpy library). DECOMPOSITION AND MODULARIZATION* :- Problem decomposition as a strategy for solving complex problems, Modularization, Motivation for modularization, Defining and using functions in Python, Functions with multiple return values RECURSION:- Recursion Defined, Reasons for using Recursion, The Call Stack, Recursion and the Stack, Avoiding Circularity in Recursion Range() Range is a built in function that generates a sequence of numbers Its is used in for loops and to create list of numbers Syntax range(start,stop,step) Start : optional - an integer specifies at which position to start, Default is 0 Stop : Mandatory - an integer specifies at which position to end Step : optional - an integer specifies the increment, Default is 1 Range example range(0,n) takes value from 0 to n-1 Example Result range(5) 0,1,2,3,4 range(2,8) 2,3,4,5,6,7 range(2,10,2) 2,4,6,8 range(5,0,-1) 5,4,3,2,1 For loop Loop that repeats an action a fixed number of times (definite iteration) We use for in association with the range() function that dictates the number of iterations. Syntax for variable_name in range(start,stop,step): Code block range(k) starts counting from 0, incrementing after each iteration, and stops on reaching k − 1. Example You are reminded that range(5) counts from 0 to 4, not 5. Example To get the numbers on the same line you need to write print(i, end=" "). By using end =" ", the Python interpreter will append whitespace following the i value, instead of the default newline character ('\n') Example Example Example Example To determine the sum of the first n even numbers. To find the sum of all multiples of 3 in a list of n numbers entered by the user. To determine the largest and smallest in a list of n numbers entered by the user. To check if the input number is a prime. Print the pattern Home work To determine the average of n numbers entered by the user. To find the sum of all odd numbers in a list of n numbers entered by the user. To print the factorial of a number. To check if a number is a perfect number or not. A perfect number is one whose value is equal to the sum of its factors. For example, 6 is a perfect number as 6 = 1 + 2 + 3 Sequence Data Types Sequence Data Types in Python refer to ordered collections of elements that can be accessed by their position or index. It allow you to store multiple items in a single variable and provide various operations for working with ordered data. Key characteristics of sequence data types are: Ordered: Elements maintain a specific order. Indexed: elements can be accessed using integer indices. Slicing: portions of the sequence can be extracted using slice notations. Sequence Data Types 1. Lists 2. Tuple 3. Sets 4. String 5. Dictionary Lists Ordered (elements maintain their position and can be accessed with their index. Mutable (which can be changed or altered after creating) Created using square brackets Allows duplicate elements. Can contain items of different data types. Support methods like append(), remove(), etc. Tuple Ordered (elements maintain their position and can be accessed with their index numbers starting from 0). Immutability: (Once created, the contents of a tuple cannot be modified) Usually defined using parenthesis. eg: coordinates = (10,20) or coordinates = 10,20 Can contain items of different data types. Tuples support methods like append(), remove(), etc. Sets Unordered: Elements have no defined position Mutable: The set itself can be modified. Sets are created using curly brackets. No duplicate elements: Each element is unique. Sets do not support indexing. String Strings are immutable sequences of characters. A group of one or more characters enclosed in a single, double or triple quote. A character in python is a string of length one; there is no character data type in Python. Built in string manipulation methods (no need to import special library): Concatenation, Slicing, Formatting, etc. Strings contain letters, numbers, symbols and whitespace characters. Ordered Immutable Represent text data Dictionary Unordered: Key value pairs have no defined position Mutable: can be modified after creation. Keys must be unique and immutable. Values can be of any data type. Curly braces with colon separated key value pairs.  Data Ordered Mutable Key value Use cases Structure pairs List Yes Yes No Storing a collection of items, accessing items by index Tuple Yes No No Immutable collection, returning multiple values from functions Set No Yes No Storing unique items, performing set operations(union, intersection) Dictionary No Yes Yes Storing data with key value pairs, efficient lookups String Yes No No Textual data, string manipulation Decomposition and Modularisation  Decomposition is the initial process of breaking down a complex problem or system into smaller, more manageable parts. Modularisation is the practical implementation of this breakdown in code, organizing these smaller parts into separate, self-contained units or modules. Decomposition provides the conceptual framework that guides modularisation. The function that calls itself repeatedly to produce solution to the original task is called Recursion. Problem decomposition as a strategy for solving complex problems Decomposition is when we break a problem down into smaller parts to make it easier to tackle. Decomposition is a useful problem-solving strategy. Decomposition saves a lot of time Example: It can help you write a complex computer program, plan a holiday or make a model plane. Problem Decomposition A problem should be decomposed into modules such that each module should have only a single responsibility. Each module should have a clear and focused purpose. It should depend minimally on other modules. The independence of a module can be measured using coupling and cohesion Coupling is the measure of the degree of interdependence between the modules. A good software will have low coupling Cohesion is a measure of the degree to which the elements of the module are functionally related. Basically, cohesion is the internal glue that keeps the module together. A good software design will have high cohesion. Key aspects of Decomposition 1. Simplification 2. Parallel Processing 3. Reusability 4. Scalability 5. Easy debugging Building a car: Instead of building the entire car at once, decompose it into sub problems: designing the engine, creating the chasis, developing the electrical system, etc. further decomposition is also possible into pistons, crankshafts, valves, etc. Modularization Modularisation is the process of separating the functionality of a program into independent, interchangeable modules, such that each contains everything necessary to execute only one aspect of the desired functionality. It allows to group some lines of code into a unit that can be included in our program. Also called sub-program, macro, sub-routine, provedure, module and function. Example: Application 1 is a payroll program for an academic institution, then Module 1 may take care of teaching staff while Module 2 is for non- teaching staff. Further, Func 1 and Func 2 may compute taxable and non- taxable incomes respectively for each of the indicated categories. Characteristics of good modularisation Cohesion: each module should focus on a single, well-defined task or functionality. It reflects the functional relationship between a module’s components, showing how well they work together for a single purpose. Strong cohesion is the hallmark of good software design. Loose coupling: It measures module interdependence. Modules should have minimal dependencies on each other, communicating through well defined interface. Encapsulation: The internal workings of a module should be hidden from other modules, with interaction occurring only through specified interfaces. Abstraction: Modules should present a simplified view of their functionality to other parts of the system. Advantages of Modularization Code reusability: Modules can be used in different parts of the program or even in other projects. Improved code organization: Related code is grouped together, making it easier to understand and manage. Enhanced code maintainability: Changes to one module are less likely to affect other parts of the program. Better team collaboration: Different teams can work on different modules independently. Motivation for modularization Promotes re-use Hides complexity Readability Reliability Supports division of labour Improves debugging and testing Contributes to scalability Reduces development costs Functions in Python In the world of Python, modules are known as functions. A Python program can be seen as a collection of functions, each of which serves a unique purpose. The portion of the function code that implements its functionality is known as function definition. For built-in functions, the definitions are provided by the interpreter itself. But, with user-defined functions, it is the duty of the programmer to define them. When we want to use the functionality provided by a function, we access it (technically known as a function call) by its name. Defining python A function should be “defined” before its first use. To define a function, you specify its name and then write the logic for implementing its functionality. The header has to end with a colon, and the body has to be indented. Syntax def function-name(parameter-list): statement-1 statement-2.. statement-n return-statement Function definition begins with the keyword def followed by the function name. Then you have the parameter list – a comma-separated list of arguments enclosed in a pair of parentheses. This line of the function definition is called header. The block of statements that constitute the function logic (statement-1to return- statement) is called function body. The final statement return exits a function. The parameters and the return statement are optional, i.e., you could write a function without these. To use its functionality, you need to call it. call a function by its name, passing the value for each parameter separated by commas and the entire list enclosed in parentheses How function works When a function call is encountered, instead of going to the next statement, the flow jumps to the body of the function, executes all the statements there, and then comes back to pick up where it left off. A function call changes the flow of execution. When the end of the program is reached, the execution terminates. Arguments and return value Arguments are the way you supply data to a function for processing. The function performs the operations on the received data and produces the result which is given back through the return statement. The value that is given back is known as the return value. Technically, you say that a function “receives” one or more arguments and “returns” a result. The parameters in the function definitions are called formal parameters, and those in the function call are called actual parameters. The arguments and the return value are both optional. Function with no arguments and no return value Function with arguments but no return value Function with return value but no arguments Function with arguments and return value Pseudocode and flowchart for function Variable scope and parameter passing The region of the program where a variable’s value can be accessed is called its scope. The variables defined inside a function are said to have local scope. This means if you try to access the value of a variable outside the function where it is defined, you are bound to get an error Actual and formal parameter Function calls obey scope rules. When a function is called, the values of the actual parameters are copied to the formal parameters. The changes made, if any, to the formal parameters, are not reflected in the calling function. The changes are made only to the local copy of the formal parameters. To implement a menu-driven calculator. Use separate func- tions for the different operations To check whether a number is even or not. To print n lines of the following pattern. To find the sum of a range of numbers. To print the nth prime number Recursion Function that call itself is called recursion function Its a problem solving technique that involves in breaking down the issue into progressively smaller subproblems until the issue is small enough to be solved easily. A recursive function typically has two key components: Base Case: The simplest version of the problem that can be solved directly without further recursion. Recursive Case: The part of the problem that involves calling the function itself to handle a smaller or simpler instance. Once we determine the two essential components, implementing a recursive function involves calling the function again based on the recursive relation until the base case is reached. Example: Calculating Factorials The factorial function is a classic example of recursion. The factorial of a non- negative integer n, denoted n!, is defined as: n! = n × (n − 1) × (n − 2) × · · · × 1 Base Case: 0! = 1 Recursive Case: n! = n × (n − 1)! for n > 0 Factorial of a Positive Integer Explanation 1. factorial(4) executes 4 * factorial(3) 2. factorial(3) executes 3 * factorial(2) 3. factorial(2) executes 2 * factorial(1) 4. factorial(1) executes 1 * factorial(0) 5. factorial(0) returns 1 to its calling function factorial(1) 6. factorial(1) returns 1 * 1 = 1 to its calling function factorial(2) 7. factorial(2) returns 2 * 1 = 2 to its calling function factorial(3) 8. factorial(3) returns 3 * 2 = 6 to its calling function factorial(4) 9. factorial(4) returns 4 * 6 = 24 Reasons for using Recursion Recursion is a powerful and often elegant approach to problem-solving. It offers several advantages over iterative methods, particularly for certain types of problems. Simplification Recursion can simplify the solution to complex problems by breaking them down into smaller, more manageable subproblems. This reduction can make the problem easier to understand and solve. Example: Finding the Greatest Common Divisor (GCD) Using Euclidean Algorithm  Natural Fit for Certain Problems Recursion is particularly well-suited for problems with a recursive structure, where the solution involves solving smaller instances of the same problem. Example: Fibonacci Sequence Greatest Common Divisor (GCD) of Two Positive Integers Finding the nth Fibonacci Number The Call Stack It operates on a last-in, first-out (LIFO) principle, Meaning that the most recent function call is processed first when returning control to previous calls. Each time a function is invoked, a stack frame is created, storing information such as the function’s parameters, local variables, and the return address. As functions call other functions, new frames are pushed onto the stack, and as functions return, their frames are popped off. This mechanism ensures that each function executes in the correct context and allows for the orderly execution and return of function calls, especially important in recursive programming where functions call themselves. How the Call Stack Works 1. Function Call: When a function is called, an activation record (also known as a stack frame) is created and pushed onto the top of the call stack. This frame contains information such as: The return address (where to return control after the function execution completes), parameters, Local variables of the function and saved registers 2. Function Execution: The CPU executes the function. If the function calls another function, a new frame is pushed onto the stack. 3. Function Return: When a function finishes executing, its frame is popped from the stack. Control is then transferred back to the return address stored in the popped frame, and execution resumes from there.  In the call stack, the frames are put on top of each other in the stack. Adhering to the LIFO principle, the last function to be called (the most recent one) is at the top of the stack while the first function that was called resides at the bottom of the stack. When a new function is called(meaning that the function at the top of the stack calls another function), that new function's frame is pushed onto the stack and becomes the active frame. When a function finishes, its frame is destroyed and removed from the stack, returning control to the frame just below it on the stack (the new top frame). Recursion and the Stack When using recursive techniques, functions "call themselves". If the function johnny() were recursive, it might make a call to itself during the course of its execution. However, as mentioned before, it is important to realise that every function called gets its own frame, with its own local variables, its own address, etc. As far as the computer is concerned, a recursive call is just like any other call. Circularity in Recursion A crucial problem to avoid when writing recursive functions is circularity. Circularity occurs when a point is reached in recursion where the arguments to the function are the same as with a previous function call in the stack. If this happens, the base case will never be reached and the recursion will continue forever, or until the computer runs out of memory and crashes. If this function is called with the value 1, then it calls itself with the value 2, which in turn calls itself with the value 1. Avoiding Circularity in Recursion Well defined base case Progression towards base case that is to reduce size of the problem in each recursive call Careful function design Advantage of recursion Simplicity Problem decomposition Readability Natural fit for certain problem Divide and conquer Backtracking Disadvantage of recursion Recursion might not be the most efficient way to implement an algorithm. Each time a function is called, there is a certain amount of "overhead" that takes up memory and system resources. When a function is called from another function, all the information about the first function must be stored so that the computer can return to it after executing the new function. adding two positive integers Sum of Digits of a Positive Number  Code- While Q: Write the python code to find sum of first 10 numbers.  Psuedocode- While Q: Write the python code to find sum of first 10 numbers. Flowchart- While  Code- For Q: Python program for loop that prints out the numbers of a list. For Psudocode Flowchart- For Flowchart Difference