Data Structure & Algorithms 1 PDF

Data Structure & Algorithms 1 CHAPTER 3: (PART2) MODULAR PROGRAMMING Sep – Dec 2023 PROCEDURE  Modular Approach and Formalism PROCEDURE STRUCTURE Procedure Head Procedure Procedure_name (Input/output formal parameters) Declarations Environment BEGIN...

Data Structure & Algorithms 1 CHAPTER 3: (PART2) MODULAR PROGRAMMING Sep – Dec 2023 PROCEDURE  Modular Approach and Formalism PROCEDURE STRUCTURE Procedure Head Procedure Procedure_name (Input/output formal parameters) Declarations Environment BEGIN - Function - Body - - - END Modular Approach and Formalism PROCEDURE STRUCTURE The body of the procedure can contain all the declarations and algorithmic structures. The list of formal parameters describes the input and output parameters including their types and their passing mode The parameter passing is identical to that of functions, but ALL output parameters must be defined with a pass-by-variable method. Modular Approach and Formalism PROCEDURE Call Calling a procedure is done by stating its name followed by the list of actual parameters, just like an instruction. The calling of a procedure is, in fact, a primitive action, consisting of the procedure name followed by the list of actual input and output parameters enclosed in parentheses, separated by commas. Just like with functions, the number, order, and type of actual parameters must match those of the formal parameters. Call Example: EQU2D(e, f, g, Nr, S1, S2) Modular Approach and Formalism Procedure Declaration (Example): Write an algorithm that solves a second-degree equation with coefficients A, B, and C read from the keyboard. PROCEDURE REAL X1, X2 REAL A, B, C EQU2D INTEGER N Role: Find the number of solutions (N) and the roots (X1 and X2) of a quadratic equation with coefficients A, B, and C. Modular Approach and Formalism Procedure Declaration (Example): Analysis: Calculation of Delta = BB - 4A*C IF (Delta < 0) THEN N=0 ELSE IF (Delta == 0) THEN N=1 X1 = -B / (2*A) X2 = X1 ELSE Ns = 2 X1 = (-B - SQRT(Delta)) / (2*A) X2 = (-B + SQRT(Delta)) / (2*A) END IF END IF Modular Approach and Formalism Procedure Declaration (Example): PROCEDURE EQU2D(Real A, B, C; Var Integer N; Var Real X1, X2) Variable Real Delta BEGIN Delta = B*B - 4*A*C IF (Delta > 0) THEN X1 = (-B - SQRT(Delta)) / (2*A) X2 = (-B + SQRT(Delta)) / (2*A) N = 2 ELSE IF (Delta == 0) THEN X1 = -B / (2*A) x2 = X1 N = 1 ELSE N = 0 END IF END IF END PROCEDURE EQU2D(Real A, Real B, Real C, Var Integer N, Var Real X1, Var Real X2) Modular Approach and Formalism Procedure Declaration (Example): Algorithm Example_Procedure Variable Real e, f, g, S1, S2 Integer Nr //Procedure declaration Procedure EQU2D(Real A, B, C; Var Integer N; Var Real XI, X2) … The body of EQU2D procedure here … BEGIN WRITE (‘Give the parameters: A, B and C: ’) READ(e, f, g) EQU2D(e, f, g, Nr, S1, S2) CASE OF Nr 0: WRTIE (‘No Solution’) 1: WRITE (‘One double root X1 = X2 = ‘, S1) 2: WRITE (Two distinct roots, X1 = ’, S1, ‘X2 = ’, S2) ENDCASE END Modular Approach and Formalism Procedure Declaration (Example): ALGORITHM PROCEDURE -1.0 2.0 3.0 -1.0 2.0 3.0 e f g A B C 16.0 delta 3.0 -1.0 2 S1 S2 Nr X1 X2 N  MODULAR DECOMPOSITION EXAMPLE Modular Decomposition: Example Consider the sequence: 1, 11, 21, 1112, 3112,... What is the next element? You've found it! Now, let's build an analysis to obtain an element from the previous one. Justification: We observe that each element is derived from the previous one. It consists of the number of 1s followed by 1 and then the number of 2s followed by 2. These elements are concatenated as we progress. 1, 11, 21, 1112, 3112, 211213... This sequence is formed by concatenating the counts of 1s and 2s to the previous element. Modular Decomposition: Example ANALYSIS  Let N be an integer representing an element of the sequence.  For each digit D (from 1 to 9): ❑ Count the number of times (NB) the digit D appears in N. ❑ Compose the desired number N2.  Display N2.  Additional instructions may be required. We will need two modules:  A module that calculates the number of occurrences of a given digit in a number (FREQDG).  A module that concatenates two numbers (CONCAT). Modular Decomposition: Example Algorithm Sequence Variable Integer N, D, N2, N3, Nb Integer Function FREQDG (Integer N , D) … //Function Body here Integer Function CONCAT (Integer A , B) … //Function Body here BEGIN READ (N) N2 = 0 FOR D FROM 1 TO 9 DO Nb = FREQDG(N,D) IF (Nb 0) THEN N3 = CONCAT(Nb, D) N2 = CONCAT(N2, N3) END IF END FOR WRITE(N2) N = N2 END Modular Decomposition: Example FUNCTION Integer Function FREQDG (Integer N , D) INTEGER N, D INTEGER Variable Integer Cpt, NbD, i FREQDG BEGIN Cpt = 0 NbD = NbDigit(N) Role: Provide the number of times the digit D FOR i FROM 1 TO NbD DO appears in N IF (N Mod 10 == D) THEN Cpt = Cpt + 1 END IF ANALYSIS: N = N Div 10 The algorithm decomposes N digit by digit END FOR FREQDG = Cpt until a quotient of 0 is obtained. For each END digit obtained (N Mod 10), if it is equal to D, it is counted. Modular Decomposition: Example FUNCTION 1230000 INTEGER A, B INTEGER + 4567 CONCAT ------------- Role: Concatenate integer A with integer B = 1234567 ANALYSIS: When you want to concatenate N1 (123) and N2 (4567), you can achieve this by adding 4 zeros to N1 and then adding N2 (4 is the number of positions in N2). Result = N1 * 10^Np + N2 = N1 * N3 + N2, where N3 = 10^Np. In this context, Np represents the number of positions in N2 that determine how many zeros need to be added to N1 for concatenation. From the analysis we need to construct the following 2 modules: CONCAT, NbDigits Modular Decomposition: Example Integer Function NbDigits(Integer N) //….. Function Body Integer Function CONCAT(Integer A, B) Variables Integer NP, P1 BEGIN NP = NbDigits (B) P1 = 10 ** NP CONCAT = A* P1 + B END Modular Decomposition: Example Function Integer Function NbDigits (Integer N) Integer N NbDigits Integer Variable Integer i BEGIN i = 0 Role: return the # digits in N WHILE (N > 0) DO i = i + 1 N = N DIV 10 END WHILE NbDigits = i END PRAMETER PASSING Parameter Passing Parameter passing is a concept that needs to be mastered; otherwise, there is a risk of losing control over the functioning of modules, especially in terms of the flow of our algorithms. There are two modes of parameter passing: 1. Value passing mode 2. Reference or variable passing mode Parameter Passing  When a parameter is provided to a module, and we want the module to return the same value that the parameter had at the input, we will perform a value passing of parameters.  But when a parameter is modified during the execution of a module, and we want to have the modified content of the parameter at the output of the module, we will perform a variable (or reference) passing. In this case, the formal parameter must be preceded by the word "VAR." Parameter Passing In general It is necessary to use:  Variable passing for ALL output parameters of a procedure- type module.  Value passing for input parameters of a function. Parameter Passing PROCEDURE EQU2D(Real A, B, C; Var Integer N; Var Real X1, X2) The absence of "VAR" indicates that the parameter passing "VAR" indicates that the mode is a value passing mode. parameter passing mode is 6 Formal parameters a variable passing mode. Procedure Call: EQU2D (i, j, k, Nr, r1, r2) EQU2D (-2.0, 3.0, 1, Nr, r1, r2) 6 Actual parameters Parameter Passing in C++ Call by value Copy of data passed to function Changes to copy do not change original Call by reference Function can directly access data Changes affect original  Parameter Passing in C++ Reference parameter Function call with omitted parameters Alias for argument in function call If not enough parameters, rightmost go to Passes parameter by reference their defaults Use & after data type in prototype Default values void myFunction( int &data ) Can be constants, global variables, or function calls Read “data is a reference to an int” Function call format the same Set defaults in function prototype int myFunction( int x = 1, int y = 2, int z = 3 ); However, original can now be changed myFunction(3) x = 3, y and z get defaults (rightmost) myFunction(3, 5) x = 3, y = 5 and z gets default Math Library in C++  LOCAL & GLOBAL OBJECT Local and Global Objects A block corresponds to a region of a program. In a program, blocks can be nested within each other. This structure, known as the block structure, defines levels of blocks:  The main program forms block level 0. Level 0 (Main Program |  Procedures and functions declared directly Level 1 Procedures/Functions in Main Program) within the main program each form a block of | level 1. Level 2 (Procedures/Functions in Level 1)  Procedures and functions declared within |... level 1 procedures or functions each form a block of level 2. Local and Global Objects  Procedures and functions declared within procedures or functions of level N each form a block of level N+1.  The level number is referred to as the depth of the level. A block of level 5 is deeper than a block of level 2. Local and Global Objects Scope of an object An object is known and usable:  In its defining block as soon as the object has been declared.  In all blocks at deeper levels if they are declared within and after its defining block. The region of a program where an object can be used is called the object's scope. Local and Global Objects Scope of an object An object is known and usable:  An object is local to a block if it is declared in the declarative part of the block.  An object is global to a block if it is declared outside the block, and the block is within the scope of that identifier. SIDE EFFECT Side Effects A side effect is when a function relies on, or modifies, something outside its parameters to do something. For example, a function which reads or writes from a variable outside its own arguments, a database, a file, or the console can be described as having side effects. Side Effects Algorithm Side_Effect Variable Integer A, B, E Caller Module Integer Function Test(Integer C) BEGIN A B E A = A * B Callee Module B = A – C 1 5 Test = A + B C Test END 5 4 BEGIN 1 1 9 20 19 A = 1 B = 5 1 39 380 379 E = 1 WRITE (Test(E)) 1 759 WRITE (Test(E)) WRITE (Test(E)) END Side Effects To avoid side effects, simply follow the following rule:  Whenever possible, do not use global variables within a module. Otherwise, only modify local objects.