Chapter 1. Algorithmic Fundamentals PDF

## CHAPTER 1. ALGORITHMIC FUNDAMENTALS ### 1.2. FUNDAMENTAL CONCEPTS **Definition 1.4** Programming Language: is a computer language that enables a human (programmer) to write source code that will be analysed and executed by a computer. Programming is considered the culmination of a series of steps...

## CHAPTER 1. ALGORITHMIC FUNDAMENTALS ### 1.2. FUNDAMENTAL CONCEPTS **Definition 1.4** Programming Language: is a computer language that enables a human (programmer) to write source code that will be analysed and executed by a computer. Programming is considered the culmination of a series of steps. * **Compilation:** Compilation involves translating the entire source code at once. The compiler reads the entire program and produces a new set of code known as object code, which can now be executed by the computer. Languages like C, C++, Pascal are examples of compiled languages. * **Interpretation:** Interpretation involves translating the program line by line into a few machine language instructions, which are then executed directly. Lisp, Prolog are examples of interpreted languages. * **Semi-compilation:** Semi-compilation is the combination of both techniques to leverage the strengths of each. This is the case with languages like Python, Java for example. **Definition 1.5** Algorithm: It is an ordered and finite sequence of instructions that outlines the steps to follow in solving a problem. According to this definition, it is clear that an algorithm does not solve the problem itself; rather, it provides a series of steps. If these steps are followed correctly, they will ultimately lead to a solution for the problem. **Definition 1.6** Algorithmics: It is the set of methods used to define and/or study algorithms. ### 1.3. MY FIRST ALGORITHM #### 1.3.1 Objects **Definition 1.7** A data object is a fundamental structure in a programming language that holds information or values. It can represent numbers, text, lists, or other types of information used in a program. * **Inputs:** Read or input the data; provide values for X and Y. * **Processing:** Perform operations on the data; calculate the average M using the values of X and Y. * **Outputs:** Display and write the results, display the value of M. All data manipulated by an algorithm are considered as objects, and the operations and actions that interact with these objects are referred to as instructions or statements. This what we will explore in the following sections. #### 1.3.2 Expressions **Definition 1.12** Expressions are composed of objects (constants, variables, values) and/or functions called operands, linked together by operators. An expression yields a value as a result after its evaluation. In this chapter, we present the basic operators that apply to the fundamental data types mentioned above. These operators are represented in the table below: | Domain | Operation Signification | Types | Example | Result | |---|---|---|---|---| | Arithmetic | addition | int, float, bool | 5 + 7 | 12 | | | subtraction | | 6 - 4 | 2 | | | multiplication | | 2 * 7 | 14 | | | exponetinal (power) | | 2 ^ 3 | 8 | | | division | | 7 / 3 | 2.33 | | | remainder of division (modulo) | | 7 % 3 | 1 | | | quotient | | 7 // 3 | 2 | | String | concatenation | str | grandfather + grandfather | grandfathergrandfather | | | repetition | | "ab" * 3 | ababab | | | membership | | "a" in "year" | True | | | non-membership | | "a" not in "month" | False | | Logical | and | bool | x and y | see Figure 1.7 | | | or | | x or y | | | | not | | not x | | | Relational comparison | > | int, float | 6 > 5 | True | | | < | | 6 < 5 | False | | | == | | 6 == 6 | True | | | <= | | 6 <= 6 | True | | | >= | | 5 >= 6 | False | | | != | | 6 != 5 | True | **Figure 1.7:** The truth tables for the operators and, or, and not. * **Well-formed expression** For a correct evaluation of the expression, it must be well-written and well-formed. If the expression contains multiple operands and operators, it is better to organize them using parentheses according to the intended meaning of the expression. It’s also important to respect the operator-operand association according to their application, as shown in the table 1.1. A well-formed expression has a type that depends on the evaluation rules of the expression. **Example 1.9.** 5 + ‘ab’ * 3: It is an ill-formed expression, we cannot apply the arithmetic operators + and * to numeric operands and a string. 5 + 3 ^ 2: This is an example of an ill-formed expression because it yields a result of 11 while the intention might have been to calculate 5 + 3 first and then multiply the result by 2. It is best to use parentheses to clarify the order of evaluation. #### 1.3.3 Assignment: assigning values to variables The assignment statement allows you to assign a new value or modify the values of data referenced by variables. The value can be a constant, an immediate value, an expression to be evaluated, or another variable. The value will also be stored in a memory location **Definition 1.13** The assignment statement "=" corresponds to the operation of assigning a value to a variable. #### 1.3.4 Input/Output Instructions (I/O) In this section, we will explore two types of instructions that work with fundamental objects and facilitate a form of interaction with the user of our algorithm or script: namely, print and input. **Definition 1.14** A data output statement corresponds to the operation of displaying the values of variables after processing. The output will be shown on the screen or on an output device. This instruction also enables the display of messages (strings). **Definition 1.15** A data input statement corresponds to the operation of entering values and assigning them to variables. The input is collected through the keyboard or another data input device. Subsequently, the entered value is stored in a designated memory location. We can use the input() function with empty parentheses or provide it with an explanatory message as an argument for the user. #### 1.3.6 Trace of execution and debugging Debugging, involving the manual execution of the script step by step with the trace of execution, is not a part of the algorithm itself. However, it is crucial for verifying whether the script produces the desired results. #### 1.3.4 Input/Output Instructions (I/O) In this section, we will explore two types of instructions that work with fundamental objects and facilitate a form of interaction with the user of our algorithm or script: namely, print and input. **Definition 1.14** A data output statement corresponds to the operation of displaying the values of variables after processing. The output will be shown on the screen or on an output device. This instruction also enables the display of messages (strings). <start_of_image> Definition 1.15 A data input statement corresponds to the operation of entering values and assigning them to variables. The input is collected through the keyboard or another data input device. Subsequently, the entered value is stored in a designated memory location. We can use the input() function with empty parentheses or provide it with an explanatory message as an argument for the user. #### 1.3.6 Trace of execution and debugging Debugging, involving the manual execution of the script step by step with the trace of execution, is not a part of the algorithm itself. However, it is crucial for verifying whether the script produces the desired results. ### 1.4. EXERCISES 1. Analysis of the problem which reads the concentration of a chemical solution and provides its pH. * **Problem Analysis:** * **Inputs:** concentration c * **Processing:** ph=log10(c) * **Outputs:** display the result: ph 2. Analysis of the problem that enables the conversion of a quantity into moles. * **Problem Analysis:** * **Inputs:** quantity n, number of Avogadro Na=6.02214076*10^23 * **Processing:** number of moles: nm=n/Na * **Outputs:** display the result: nm 3. Analysis of the problem that converts a temperature in degrees Celsius to degrees Fahrenheit. * **Problem Analysis:** * **Inputs:** Celsius temperature C * **Processing:** Fahrenheit temperature: F=(C+9/5)+32 * **Outputs:** display the result: F 4. Analysis of the problem that determines the components X and Y of a vector V based on its magnitude and the angle (expressed in degrees) relative to the horizontal axis. * **Problem Analysis:** * **Inputs:** magnitude n, angle θ * **Processing:** convert θ to radians: 0= θ * 3.14 /180 * **Vector’s components:** x= magnitude * cos(θ), y=magnitude * sin(θ) * **Outputs:** display the results: x, y 5. Analysis of the problem which reads the components x and y of a vector V and calculates its magnitude. * **Problem Analysis:** * **Inputs:** Vector’s components V(Xv, Yv) * **Processing:** The magnitude: m= sqrt(Xv^2+Yv^2) * **Outputs:** display the result: m 6. Analysis of the problem which reads the coordinates of points A and B, and calculates the coordinates of the midpoint of the segment connecting them. * **Problem Analysis:** * **Inputs:** Points coordinates: A(Az, Ay), B(Bx, By) * **Processing:** Segment’s midpoint coordinates: Mr=(Ar+Br)/2, My=(Ay+By)/2 * **Outputs:** display the result: M(Mr.My) 7. The analysis involves reading a time duration provided in hours, minutes, and seconds, and then converting it into seconds. * **Problem Analysis:** * **Inputs:** time duration: h, m, s * **Processing:** duration in seconds: ds= (h * 3600 + m * 60 + s) * **Outputs:** display the result: ds 8. The analysis involves reading the coordinates of two points, A(Az, Ay) and B(Bx, By), and then determining the equation of the line that passes through both points. * **Problem Analysis:** * **Inputs:** Points coordinates A(Ar, Ay) and B(Br, By) * **Processing:** * slope: a = (By-Ay) / (Bx-Ar) * y_intercepts: b=By - a * Br * **Outputs:** display the line’s equation: y=ax+b 9. Analysis of the problem that reads a four-digit number and decomposes it into thousands, hundreds, tens, and units. * **Problem Analysis:** * **Inputs:** the number n * **Processing:** the decomposition: * The number in thousands: t = n // 1000 * The number in hundreds: h = (n // 100) % 10 * The number in tens: d = (n % 100) // 10 * The number in units: u = (n % 100) % 10 * **Outputs:** display the results: t, h, d, u #### 1.4. Exercises In this section, we will delve into comprehensive solutions for a few straightforward problems. **Exercise 1.1.** Write an algorithm that calculates the distance between two points A and B on a Cartesian plane. To calculate the distance between two points A and B on a Cartesian plane, we can use the Pythagorean theorem. Here’s an analysis of the problem: * **Problem analysis:** * **Inputs:** Get the coordinates of points A(ax, ay) and B(bx, by) * **Processing:** Dm = square root((bx-ax)**2 + (by-ay)**2) * **Outputs:** The distance variable D will contain the distance between points A and B **Example 1.17.** round(3.26957845331,2) → 3.27 round(21.1234567) → 21 - rounds to two decimal places - in this case the method rounds to the nearest integer (21) **Exercise 1.3.** Consider the following problems along with their analyses. You are tasked with writing their corresponding algorithms. * **Analysis of the problem which reads the concentration of a chemical solution and provides its pH** * **Problem Analysis:** * **Inputs:** concentration c * **Processing:** ph=log10(c) * **Outputs:** display the result: ph * **Analysis of the problem that enables the conversion of a quantity into moles:** * **Problem Analysis:** * **Inputs:** quantity n, number of Avogadro Na=6.02214076*10^23 * **Processing:** number of moles: nm=n/Na * **Outputs:** display the result: nm * **Analysis of the problem that converts a temperature in degrees Celsius to degrees Fahrenheit** * **Problem Analysis:** * **Inputs:** Celsius temperature C * **Processing:** Fahrenheit temperature: F=(C+9/5)+32 * **Outputs:** display the result: F * **Analysis of the problem that determines the components X and Y of a vector V based on its magnitude and the angle (expressed in degrees) relative to the horizontal axis.** * **Problem Analysis:** * **Inputs:** magnitude n, angle θ * **Processing:** convert θ to radians: 0= θ * 3.14 /180 * **Vector’s components:** x= magnitude * cos(θ), y=magnitude * sin(θ) * **Outputs:** display the results: x, y **Exercise 1.4.** Convert the previously analysed problems into scripts. **Exercise 1.1.** Write an algorithm that calculates the distance between two points A and B on a Cartesian plane. **Python implementation of the algorithm:** ```python import math #inputs ax = float(input("Enter the x-coordinate of point A: ")) ay = float(input('Enter the y coordinate of point A: ')) bx = float(input("Enter the x-coordinate of point B: ")) by = float(input("Enter the y-coordinate of point B: ")) #Calculate the Distance distance = math.sqrt((bx-ax)**2 + (by-ay)**2) #the result or outputs print("The distance between points A and B = ", distance) ``` **Note 1.13:** In a Python editor, you can choose your mode of writing the program, either in the script window or in the console (shell). The script window in a Python editor is where programmers write their code, which can be saved and modified. The console (shell) is where the program runs, and users enter inputs requested by the program. For the Python code in the script window and its execution in the console, please refer to the Figure 1.11.