Python first year btech Algorithmic thinking with python

Python 1st year 1st module

1. Module 1 PROBLEM SOLVING STRATEGIES

2. Syllabus PROBLEM-SOLVING STRATEGIES :- Problem-solving strategies defined, Importance of understanding multiple problem-solving strategies, Trial and Error, Heuristics, Means-Ends Analysis, and Backtracking (Working backward). THE PROBLEM-SOLVING PROCESS :- Computer as a model of computation, Understanding the problem, Formulating a model, Developing an algorithm, Writing the program, Testing the program, and Evaluating the solution. ESSENTIALS OF PYTHON PROGRAMMING :- Creating and using variables in Python, Numeric and String data types in Python, Using the math module, Using the Python Standard Library for handling basic I/O - print, input, Python operators and their precedence.

3. Problem-Solving Strategies The ter m pr o blem solving has a s l ig h t l y di f fe r ent m e a ning d e p e ndi n g o n t h e discipline. Definition : A problem-solving strategy is a plan used to find a solution or overcome a challenge or achieve a goal . Solutions require sufficient resources and knowledge to attain the goal. Profes s ion a ls such a s l a w y er s , doc t ors, p r o g r a mm er s , and c o nsultants are problem solvers.

4. Problem-Solving Strategies Problems can be classified into two different categories: ill-defined and well-defined problems. Ill- def i ned probl em s : i s sues that do not h a ve clea r goa l s, solut i on paths, or expected solutions. Examples: ?? Well-defined problems : have specific goals, clearly defined solutions, and clear expected solutions. Examples: ??

5. Importance of Multiple Problem-Solving Strategies Different problems typically require you to approach them in different ways to find the best solution. Understanding multiple problem-solving strategies is crucial because it equips individuals with a diverse toolkit to tackle a variety of challenges . By knowing several strategies, one can quickly switch tactics when one method does not work, increasing the chances of finding a successful solution.

6. Importance of Multiple Problem-Solving Strategies Other benefits includes: Adaptability Efficiency Improved Outcomes Skill Development. Common problem solving strategies include: Trial and Error Method Algorithm and Heuristic Mean s - E n d s A n a l ysis Backtracking

7. A fundamental method of Problem solving. It is characterized by repeated , varied attempts which are continued until success . When to avoid the trial and error method: When there is a clear solution When the cost of failure is high When you are working with limited resources Trial and Error Method

8. Problem: Consider the situation where you have forgotten the password to your online account, and there is no password recovery option available. You decide to use trial and error to regain access. Trial and Error Method – Example 1

9. Problem: Printer is not working Solutions: Try checking the ink levels, and if that doesn’t work. Check to make sure the paper tray isn’t jammed. Or may be the printer isn’t connected to a laptop. When using trial and error, one would continue to try different solutions until the problem is solved. Trial and Error Method – Example 2

10. A farmer with a fox, a goose, and a sack of corn needs to cross a river. The farmer has a boat, but there is room for only the farmer and one of his three items. Unfortunately, both the fox and the goose are hungry. The fox cannot be left alone with the goose, or the fox will eat the goose. Likewise, the goose cannot be left alone with the sack of corn, or the goose will eat the corn. How does the farmer get everything across the river? Trial and Error Method – Example 3

11. Solution: HOW TO CROSS THE RIVER?

12. Algorithms and heuristics are different approaches to solving problems. Algorithms are step-by-step procedures for a solution. They are guaranteed to yield the correct solution, but may be time-consuming and require a lot of mental effort. Eg:- Google use algorithms to decide which entries will appear first in your list of results. In contrast, heuristics are shortcut strategies or rules-of-thumb for a solution, but there is no guarantee for the result. They are estimations or shortcuts based on past experience . Eg : - dr i ving i n a cit y with fr e qu e nt tr a f fic conges t io n , tr a veli n g s a l e sper s on problem, etc. Algorithm and Heuristic

13. Used in Artificial Intelligence. It involves breaking down a problem into smaller, more manageable sub-problems to reduce the difference between the current state and the desired goal state. Example: Imagine you want to plan a road trip from our college to Kashmir. Define the Goal (End) Analyze the Current State Identify the Differences Set Sub-Goals (Means) Implement the Plan Adjust as Needed (In this case based on traffic) Mean s -Ends Analysis

14. Mean s -Ends Analysis

15. When the problem to be solved is too complex to manage, break it into manageable parts known as sub-problems . This process is known as problem decomposition. Steps: Understand the problem. Identify the sub-problems. Solving the sub-problems. Combine the solution. Test the combined solution. Problem Decomposition

16. The actual Tower of Hanoi problem consists of three rods sitting vertically on a base with a number of disks of different sizes that can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top making a conical shape. The objective of the puzzle is to move the entire stack to another rod obeying the following rules: Only one disk can be moved at a time. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod. No larger disc may be placed on top of a smaller disk. Tower of Hanoi paradigm

17. Tower of Hanoi paradigm

18. With 3 disks, the puzzle can be solved in 7 moves. The minimal moves required to solve a Tower of Hanoi puzzle is 2 n – 1, where n is the number of disks. For example, if there were 14 disks in the tower, the minimum amount of moves that could be made to solve the puzzle would be 2 14 – 1 = 16,383 moves. There are various ways of approaching the Tower of Hanoi or its related problems in addition to the approaches listed above including an iterative solution, recursive solution, non-recursive solution, a binary and Gray-code solutions, and graphical representations. We will see Means-Ends Analysis Solution. Tower of Hanoi paradigm

19. Tower of Hanoi paradigm

20. 3AC Divided as Subgoals

21. 2AB Divided as Subgoals

22. 2BC Divided as Subgoals

23. Graphically

24. Backtracking is like trying different paths, and when you hit a dead end, you backtrack to the last choice and try a different route. Since a problem would have constraints , the solutions that fail to satisfy them will be removed. It is commonly used in situations where you need to explore multiple possibilities to solve a problem, like searching for a path in a maze or solving puzzles like Sudoku. Backtracking

25. Choose an initial solution. Explore all possible extensions of the current solution. If an extension leads to a solution, return that solution. If an extension does not lead to a solution, backtrack to the previous solution and try a different extension. Repeat steps 2-4 until all possible solutions have been explored. Backtracking – How it works?

26. Finding the shortest path through a maze Inpu t : A m aze repres e nted as a 2 D ar r a y , where 0 rep r esen t s an o p e n space and 1 represents a wall. Start at the starting point. F o r eac h o f the four p o s sible directio n s (up, down, left, ri g ht), try m o v ing in that direction. If moving in that direction leads to the ending point, return the path taken. If moving in that direction does not lead to the ending point, backtrack to the previous position and try a different direction. Repeat ste p s 2 -4 u n til the e nd i n g p o i nt is rea c hed o r all p o ssible p at h s h a ve been explored. Backtracking – Example

27. Past Experience : Take the time to consider if you have encountered a similar situation to your current problem in the past. Bring in a Facilitator : Consider inviting a facilitator to your group meeting to help generate better solutions. Develop a decision matrix for evaluation : Rank your potential solutions based on factors like timeliness, risk, manageability, expense, practicality, and effectiveness. Ask your peers for help : Friends, families or colleagues may have different experiences, ideas and skills that may contribute to finding the best solution to a problem. Step away from the problem : If the problem being worked on does not need an immediate solution, consider stepping away from it for a short period of time. Other Problem-solving Strategies

28. The Problem-Solving Process

29. Computer as a Model of Computation

30. The above model works based on input-process-output concept. Computer as a model of computation Von Neumann’s Computer Architecture Model

31. Definition: Problem Solving is the sequential process of analyzing information related to a given situation and generating appropriate response options. Example: Calculate the average grade for all students in a class. Input : get all the grades … possibly by typing them in via the keyboard or by reading them from a USB flash drive or hard disk. Process : add them all up and compute the average grade. Output : output the answer to either the monitor, to the printer, to the USB flash drive or hard disk … or a combination of any of these devices. Computer as a model of computation

32. Understanding the problem Formulating a model Developing an algorithm Writing the program Testing the program Evaluating the solution. Computer as a model of computation

33. Understands the problem about to be solved. One needs to know: What input data/information is available? In what format is the data/information? What is missing in the data provided? Does the person solving the problem have everything needed? What output information needs to be produced? In what format should the result be: text, picture, graph? What are the other requirements needed for computation? 1. Understanding the problem

34. Formulate a model for the problem. By c ons i d e ring the a b o v e p r obl e m, a m o d e l (or for m ula) i s need e d for computing the average of a bunch of numbers. If there is no such “formula”, one must be developed. Assuming that the input data is a bunch of integers or real numbers 𝑥 1 , 𝑥 2 , ⋯ , 𝑥 𝑛 repr e s e n t ing a gr a de per c ent a ge, the f ollo w i ng co m p u t a t i onal m o d el m ay apply: 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 1 = ( 𝑥 1 + 𝑥 2 + 𝑥 3 + ⋯ + 𝑥 𝑛 )/ 𝑛 2. Formulating a Model

35. However, the above approach will not work if the input data is a set of letter grades like B-, C, A+, F, D-, etc. S o , we m a y dec i de t o a s s i gn a n integer nu m ber t o the in c om i ng letter s as follows: 𝐴 + = 12, 𝐴 = 11, 𝐴 − = 10, 𝐵 + = 9, 𝐵 = 8, etc. As s ume the s e n e wly a s s i g n ed gr a de n u m bers a r e 𝑦 1 , 𝑦 2 , ⋯ , 𝑦 𝑛 , then t he following computational model may be used: 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 2 = ( 𝑦 1 + 𝑦 2 + 𝑦 3 + ⋯ + 𝑦 𝑛 )/n 2. Formulating a Model

36. Come up with a precise plan of what the computer is expected to do . Defini t io n : Al g orit h m i s a p r e c i s e s e q u ence o f i n s t ruct i o n s for solving a problem. The instructions must be understandable to a person who is trying to figure out the steps involved. Two commonly used representations for an algorithm is by using Pseudocode Flowcharts 3. Develop an Algorithm

37. Consider the following example for solving the problem of a broken lamp. 3. Develop an Algorithm Flowchart for a broken Lamp

38. Algorithm for a broken Lamp IF lamp works, go to step 7. Check if lamp is plugged in. IF not plugged in, plug in lamp. Check if bulb is burnt out. IF blub is burnt, replace bulb. IF lamp doesn’t work buy new lamp. Quit ... problem is solved. 3. Develop an Algorithm

39. Algorithm to calculate the average of grades 1. Set the sum of the grade values to 0. 2. Read all grades 𝑥 1 , 𝑥 2 , ⋯ , 𝑥 𝑛 . for i = 1 to n, repeat the following Get grade 𝑥 𝑖 Add 𝑥 𝑖 to the sum Compute average to be sum/ 𝑛 . Print the average. 3. Develop an Algorithm

40. Writing a program is often called " coding " or “ implementing an algorithm ”. So the code (or source code ) is actually the program itself. The source code would vary depending on the programming language that was used. The c ompu t er re q uires prec i se i n s t ruct i o n s i n o rder t o unders t a n d w hat i t is being asked to do. Compiling is the process of converting a program into instructions that can be understood by the computer. Fix all such compile-time errors before continuing on to the next step. 4. Writing the Program

41. Sometime, a program may work correctly for some set of input data but not for all. If the output of a program is incorrect, it is possible that the algorithm was not properly converted into a proper program. Such problems with the program are known as bugs . B u gs are er r ors w i th a prog r am that c ause i t t o s top working or p roduce incorrect or undesirable results. It is the responsibility of the programmer to fix as many bugs in a program as present. To find bugs effectively, a program should be tested with many test cases. Debugging is the process of finding and fixing errors in program code. 5. Testing the program

42. Re-do some of the steps again, perhaps going as far back as step 1 again if the expected result is not getting from the last step. Here the original problem needs to be reconsidered to make sure that the answer is formatted into a proper solution to the problem. For example, if the result of a program is a long list of numbers, but the intent was to identify some feature from the data, then simply producing a list of numbers may not suffice. There may be a need to display the information in a way that helps visualize or interpret the results with respect to the problem; perhaps a chart or graph is needed. 6. Evaluating the Solution

43. Problem: Determining the discriminant of a quadratic equation . Understand the problem : Here formally define the problem by specifying the inputs and output. Input: The three coefficients a , b and c of the quadratic equation Output: The discriminant value D for the quadratic equation. Formulate a model for the solution : Develop a mathematical model for the solution. D = b 2 − 4ac A Case Study - The Discriminant Calculator

44. D e velop a n algori t h m : A po s sible discriminant problem is given below Start Read(a, b, c) 3. d = b ∗ b − 4 ∗ a ∗ c Print(d) Stop a l g o r i t hm (or Pseudo c ode) for our A Case Study - The Discriminant Calculator

45. Code the algorithm : The Python program to calculate the discriminant is as follows a = int(input("Enter the value of first coefficient")) b = int(input("Enter the value of second coefficient")) c = int(input("Enter the value of third coefficient")) d = (b**2) - (4*a*c) print(d) A Case Study - The Discriminant Calculator

46. T e s t the p r ogr a m : E a ch r ow d e not e s a set o f in p uts (a, b , and c ) and t h e expected output (d) with which the actual output is to be compared. A Case Study - The Discriminant Calculator

47. Essentials of Python Programming

48. The Python Programming Language Python is an example of a high-level language. It is an interpreted language Python programs are executed by an interpreter. There are two ways to use the interpreter: Command line mode Script mode.

49. The Python Programming Language In com m a n d -line mo d e, w e t y pe P y th o n p r o g r am s and the inte r pret e r prints the result $ python Python 3.12.4 (Sep 20 2024, 09:28:56) Type "help", "copyright", "credits" or "license" for more information. >>> print (1 + 1) 2

50. The Python Programming Language In script mode, we can write a program in a file and use the interpreter to execute the contents of the file. Such a file is called a script. For example, we use a text editor to create a file named test.py with the following contents: print (1 + 1) To execute the program: $ python test.py 2

51. Values and Data Types in Python A value is one of the fundamental things, like a letter or a number. Eg: 2, 2.5, ‘a’, “Hello” These values belong to different data types Integer, float, character, string >>> type("Hello, World!") <type 'str'> >>> type(17) <type 'int'>

52. Python Identifiers A P y t h on identif i er i s a na m e used t o i d enti f y a v a ri a ble, func t io n , c l a s s, module or other object. An identifier starts with a letter A to Z or a to z or an underscore ‘ _ ’ followed by zero or more letters, underscores and digits (0 to 9). Examples: sum, name, age, _age, Age, name_1, name0

53. V ariables A variable is a name that refers to a value Variables are created when they are assigned The variable name is case sensitive: ‘val’ is not the same as ‘Val’ The type of the variable is determined by Python A variable can be reassigned to whatever, whenever >>> message = “Welcome to Python Programming" >>> n = 17 >>> pi = 3.14159

54. Variable Names Variable names can be arbitrarily long. They can contain both letters and numbers, but they have to begin with a letter. The underscore character ( _ ) can appear in a name. used i n na m es with m ul t ip l e words, such as my_nam e or birth_dat e .

55. Variable Names – invalid syntax >>> 76trombones = "big parade" SyntaxError: invalid syntax >>> more$ = 1000 SyntaxError: invalid syntax >>> class = "Computer Science 101" SyntaxError: invalid syntax

56. Keywor d s Keywords define the language's rules and structure, and they cannot be used as variable names. Python has 29 keywords:

57. St a teme n ts A statement is an instruction that the Python interpreter can execute. Egs:- print statement and assignment statement. prin t (“ W e ar e S 1 CS E St udent s …… ”) age = 19 h = “Hello…” price = 25.5

58. Evaluating Expressions An expression is a combination of values, variables, and operators. >>> 1 + 1 2 >>> Sum = a + b

59. The math Module A module is a file consisting of Python code. I t ca n d e fine f u n c t i o ns, classes , and vari a bles w h i c h ca n b e u s ed i n ot h e r programs. Ma t h m odule c o nsi s ts of al l t h e b u i l t-i n fun c t i o n s t o per f o r m m a t he m atic a l operations. To use a mathematical function in a program, first import the math module using the import keyword. Example: import math print(math.pi) print(math.sqrt(16))

60. math.sqrt(x) math.exp(x) math.pi math.log(x) #log(x) is base e For example: >>> math.sqrt(2) / 2.0 0.707106781187 The math Module

61. Co m po s ition Python functions can be composed. We can use one expression as part of another. Example: >>> x = math.cos(angle + math.pi/2) >>> x = math.exp(math.log(10.0))

62. Input/Output Functions To print a message or value to screen, use: print( ) – I t prints so m e t hi n g o n the s c re e n To read values from the keyboard, use: input() – It reads the input and returns a string. int(input() ) – Reads the in p ut and re t ur n s a n intege r . Example: name = input(“Enter Name”); age = int(input(“Enter Age”)); print(“Hello ”, name)

63. name = input(“Enter Name”); print("Enter name") name = input() Print(name)

64. Example Programs Si m ple desktop c a l c ulator usi n g P y t h on. O n ly the five basic ar i th m e t i c operators. Write a program to find the value of (a + b) 2 Write a program to evaluate the expression n(n - 1)/2

65. Operators in Python Operators are special symbols that represent computations like addition and multiplication. The values the operator uses are called operands . Examples: 20+32 , hou r- 1 , h ou r * 60+m in ute , m inute/ 60 , 5* * 2 , (5+9)*(15-7) When a variable name appears in the place of an operand, it is replaced with its value before the operation is performed.

66. Python language supports the following types of operators. Arithmetic Operators Comparison (Relational) Operators Assignment Operators Logical Operators Bitwise Operators Membership Operators Identity Operators. Operators in Python

67. 1. Arit h metic Operat o rs Floor division is also called integer division Example: >>> 7.0//2 3.0 >>> 7//2 3

68. 2. A s sign m ent Operator ‘ = ’ is the assignment operator. The assignment statement creates new variables and gives them values. Examples: >>> a = 10 >>> a = b = 5 >>> a, b, c = 1, 2.5, "ram" Python supports the following six additional assignment operators

69. 3. Comparison Operator The result of a comparison is either True or False. Examples: >>> i , j, k = 3, 4, 7 >>> i > j False >>> (j + k) True > (i + 5) Comparison operators support chaining. For example, x < y <= z is equivalent to x < y and y <= z.

70. 4. Logical Operators Python includes three Boolean (logical) operators: and , or , and not . The and operator and or operator expect two operands, which are hence called binary operators . The and operator returns True if and only if both of its operands are True , and returns False otherwise. The or operator returns False if and only if both of its operands are False , and returns True otherwise. The not operator expects a single operand and is hence called a unary operator. I t re t ur n s t he l o gical n e gation o f the ope r a n d, that i s , T ru e , i f t h e oper a nd is False , and False if the operand is True .

71. 4. Logical Operators – Truth Table T ruth t a b l e s for l o gical o r a nd lo g i c al and operators. T ruth t a bl e s for l o gic a l not operator. Python interprets all non-zero values as True and zero as False

72. 4. Logical Operators - Example >>> 7 and 1 1 >>> -2 or -2 >>> -100 and >>> True and False False >>> False or True True >>> False or False False >>> not True False

73. 5. Bitwise Operators Bitwise operators take the binary representation of the operands and work on their bits, one bit at a time. The bits of the operand(s) are compared starting with the rightmost bit (least significant bit), then moving towards the left and ending with the leftmost (most significant) bit. The result of the comparison will depend on the compared bits and the operation being performed. Bitwise operators can be divided into three general categories: One’s complement, Logical bitwise, and Bitwise shift

74. 5.1 One’s complement Operation -7 >>> ~8 -9 One’s complement is denoted by the symbol ∼ . I t o p er a t e s b y c h a n g i ng al l z e r o es t o o n es a n d ones t o z e r oes i n the bi n a r y representation of the operand. >>> ~6 8 = 1000 ∼ 8 = 1 1 1 ( Wh i c h i s t h e 2 ’s complement of -9 ) = -9

75. 5.2 Logical Bitwise There are three logical bitwise operators: bitwise and ( & ), bitwise exclusive or ( 𝖠 ), and bitwise or ( | ). A bitwise and expression will return 1 if both the operand bits are 1.Otherwise, it will return 0. A bitwise or expression will return 1 if at least one of the operand bits is 1. Otherwise, it will return 0. A bitwise exclusive or expression will return 1 if the bits are not alike (one bit is and the other is 1). Otherwise, it will return 0.

76. 5.2 Logical Bitwise >>> a = 5 >>> b = 6 >>> a & b 4 >>> a | b 7 >>> a ^ b 3

77. 5.3 Bitwise Shift Operators The two bitwise shift operators are shift left ( << ) and shift right ( >> ). The expression x << n shifts each bit of the binary representation of x to the left, n times. Each time we shift the bits left, the vacant bit position at the right end is filled with a zero. The expression x >> n shifts each bit of the binary representation of x to the right, n times. Each time we shift the bits right, the vacant bit position at the left end is filled with a zero.

78. 5.3 Bitwise Shift Operators >>> 120 >> 2 30 >>> 10 << 3 80 120 = 0111 1000 Right shifting once − 0011 1100 Right shifting twice − 0001 1110 120 >> 2 = 30 10 = 0000 1010 Left shifting once − 0001 0100 Left shifting twice − 0010 1000 Left shifting thrice − 0101 0000 10 << 3 = 80

79. 6. Membership Operators These operators test for the membership of a data item in a sequence, such as a string. Two membership operators are used in Python. in – Evaluates to True if it finds the item in the specified sequence and False otherwise. not in – Evaluates to True if it does not find the item in the specified sequence and False otherwise.

80. 6. Membership Operators - Example >>> ‘E' in ‘HELLO' True >>> ‘e' in ‘HELLO' False >>> 'a' not in ‘Welcome' True

81. 6. Identity Operators is and is not are the identity operators in Python. They are used to check if two values (or variables) are located in the same part of the memory. x is y evaluates to True if and only if x and y are the same object. x is not y yields the inverse truth value.

82. When more than one operator appears in an expression, the order of evaluation depends on the rules of precedence. The acronym PEMDAS is a useful way to remember the order of operations. 2 * (3-1) is 4 (1+1)**(5-2) is 8 2**1+1 is 3, and not 4 3*1**3 is 3, and not 27 2*3-1 is 5, not 4 2/3-1 is -1, not 1 Note : Multiplication and Division have the same precedence. In this case it will Left to Right associativity. Precedence of Operators

83. String Operations branch = “ CSE” semester = “S1” s = “ Students...” greeting = “Hello ” + semester + branch + s print (greeting) O/P: Hello S1 CSE Students... Or we can use greeting = “Hello ” , semester , branch , s

84. String Operations “Hello” * 3 is “HelloHelloHello". One of the operands has to be a string; the other has to be an integer.

85. Co m men t s To add notes to your programs to explain in natural language what the program is doing. C o mm ents are m arked with the # sy m b o l . Eg: # compute the percentage of marks obtained percentage = (m1 + m2 + m3) * 100 / 300 – Everything from the # to the end of the line is ignored

86. I n den t ation Python uses indentation to highlight the blocks of code. Whitespace is used for indentation in Python. All statements with the same distance to the right belong to the same block of code. If a block has to be more deeply nested, it is simply indented further to the right.

87. Indentation - Example # Python program showing indentation site = 'gfg' if site == 'gfg': print(‘Welcome S1 Students...') else: print(‘Hai……’) print('All set !')