Functions and Algorithmic Problems PDF

# Functions and Algorithmic Problems ## 4.1 Fundamentals of Subroutines - Many imperative programs offer a way to define subroutines and functions. - This allows for much more structured and sophisticated programs at a much larger scale. - At a very basic level, a subroutine lets us collect a sequ...

# Functions and Algorithmic Problems ## 4.1 Fundamentals of Subroutines - Many imperative programs offer a way to define subroutines and functions. - This allows for much more structured and sophisticated programs at a much larger scale. - At a very basic level, a subroutine lets us collect a sequence of instructions into a unit that has a name. - To execute this sequence of instructions in our program, we can call or invoke the subroutine by using its name. - In Python, it looks like this: ```python def name(): block ``` - A subroutine may receive parameters, variables that pass information to the subroutine when it is called and that can be used inside the subroutine. - The parameters must be declared in the definition of the subroutine, and the subroutine call must conform exactly to this declaration. - For example: ```python def greet(firstname, lastname): print("Hello " + firstname + " " + lastname + ", nice to meet you.") print("How are you doing?") greet("Helmut", "Roth") greet("Günter", "Alt") # Output on screen: # Hello Helmut Roth, nice to meet you. # How are you doing? # Hello Günter Alt, nice to meet you. # How are you doing? ``` ## 4.1.1 Functions - A subroutine may also have a return value. - In this case, the subroutine is called a function. - The value is returned using the return-statement. - The return-statement also finishes the execution of the function, even if there are instructions that come after it. - For example: ```python def square(x): return x*x def greet2(timeofday): print("Good " + timeofday + " .") name = input("What is your name? ") return name z = square(5) + square(10) name = "Person" + greet2("morning") ``` - In Python, every subroutine is a function and may be used in an expression (whereas other programming languages distinguish between subroutines/procedures and functions). - If there is no return statement, the function value is `None`. - We can also use a return statement without a value. - This is interpreted as returning `None`. - Functions in Python that return `None` are called methods. **Attention:** There is an essential difference between the method `print()` and the return-statement: While `print()` simply prints something on the screen it has return value `None`. On the other hand, the return-statement is used to pass the value to the invoking instance. This difference is highly relevant for the exact specification of functions. For example, the following function prints 42 on the screen but returns 0. ```python def func(): print(42) return 0 a: int = func() + 3 print(a) # Output on the screen: # 42 # 3 ``` ## 4.1.2 Scope - The Scope is the notion that certain identifiers in a program are valid only in a given part of the code, and that it cannot be used in another part of the program. - A function in Python defines a local scope, and a variable name that is created inside the function is not visible outside the function. - For example: ```python def f(): x = 1 print(x) f() print(x) ``` - This would result in an error, because the variable `x` is defined only in the local scope of the function `f`, and it is not a valid name outside the function. - Scopes can be nested. - For example, the scope of the main program is called the global scope, and variable names that are in the global scope can also be used in functions that are defined inside the main program: ```python x = 10 def f(): print(x) f() print(x) ``` - It may happen that we define a variable in a local scope that has the same name as a variable in the outer scope. - This defines two different variables with the same name. - In the inner scope, we can access only the local variable, and once we leave the inner scope, the local variable disappears. - We say that the variable in the inner scope shadows the variable in the outer scope: ```python x = 10 def f(): x = 20 print(x) print(x) f() print(x) ``` - In Python, we can used the `global` keyword to instruct Python not to create a new local variable but to use the variable from the global scope: ```python x = 10 def f(): global x x = 20 print(x) print(x) f() print(x) ``` ## 4.2 The 5 steps - Functions and methods are used to handle well-defined tasks, like for example computing the largest number in a list of numbers. - It is used to improve the program structure. - For this, it is important to specify the exact behaviour of a function and to provide comments for further details. - Hence, when implementing functions, we always have to use the following concepts that strengthen the readability of a function. ## 4.2.1 Signature - The signature provides the name of the function, the types of the input parameters, and the type of the return values. - Since Python is dynamically typed, we can always use parameters of different types, like in this example: ```python def double(x): return 2 * x print(double(4)) # outputs: 8 print(double([0,1])) # outputs [0,1,0,1] ``` - However, the is bad programming style and in languages with static type systems (like Scala, Java) not allowed. - Therefore, we use comments in Python to state the signature of a function. - The signature must be formulated before the function is implemented. - Here are some examples: ```python #double(int): int # maximum(List[int]): int ``` - The function `double()` shall be used to return the double of an integer value, which is itself again an integer value. - Moreover, the function `maximum()` shall be used get a list of integers and returns an integer. ## 4.2.2 Specification - The specification is a contract between the developer and the user of the function. - It is a precise description of the preconditions under which a function can be called and its result (what is the return-value of the function?) and effect (how does the function affect the global state?). - The result and the effect is written in stative passive. - The specification must be formulated before the function is implemented. - Here are some examples with signature and specification: ```python #double(int): int # Precondition: None # Effect: None # Result: The double of the input number is returned. # maximun(List[int]): int # Precondition: list is not empty #Effect: The largest number of the list is printed on the screen. # Result: The largest number of the list is returned. def maximum(list: list[int]) -> int: erg = list[0] for i in range(1, len(list)): erg = max(erg, list[i]) print(erg) return erg #bar(float, float) -> float # Precondition: b is not Zero # Effect: The input numbers are printed on the screen. # Result: The quotient of a and b is returned. def bar(a: float, b: float) -> float: print(a, b) return a / b ``` - Note the difference between `print()` and `return` and how they affect the specification: The `print()`-function changes the state of the machine (output device) and belongs to the effect of the function. The value of the `return`-statment corresponds to the result of the function. **Attention:** Whenever possible, a function should either have an effect or a result bot not both. The reason is as follows: - Functions sometimes have hidden effects in addition to just returning a value. These effects are called the side effects of the function evaluation. - Sometimes, unintended side effects may lead to errors that are hard to find in an imperative program. - The following implementation of the minimum(-)-function has the side effect that it changes the input list: ```python # maximum(List[int]): int # Precondition: list is not empty # Effect: list[i] contains the minimum of the elements at # indices 0 to i of the input list # Result: The smallest number of the list is returned. def minimum(list: list[int]) -> int: min = list[0] for i in range(1, len(list)): min = min(min, list[i]) list[i] = min # This modifies the input list return min ``` ## 4.2.3 Tests - Tests are used to show the existence of program errors. - They will never show the absence of program errors - this is only possible by using correctness proofs. - In many cases the program is too complex to give a correctness proof. - Therefore, it is elemental to think about test cases that cover all important and edge cases. - The test cases have to be formulated after we finished the specification and before we implement the function. - Here are some examples: ```python #double(int): int # Precondition: None #Effect: None # Result: The double o the input number is returned. # Test cases: double(4) == 8 # positive number double(0) == 0 # number 0 double(-1) == -2 # negative number # mazimum(List[int]): int # Precondition: list is not empty # Effect: The largest number of the list is printed on the screen. # Result: The largest number of the list is returned. # Test cases: mazimum([1,2,3,2,1]) == 3 mazimum([1,2,3,4]) == 4 mazimum([4,3,2,1]) == 4 mazimum([1,1,1,1]) == 1 mazimum([42]) == 42 ``` - Observe that `maximum([])` was not a test case although it could be an important edge case. - However, we omitted this case since we already excluded this case by our specification. ## 4.2.4 Definition - Once the signature, the specification, and the test cases have been formulated, we can give the definition of the function, i.e., the actual implementation. - Once we have implemented the function we use the formulated test cases to find potential errors in our implementation. ## 4.2.5 Comments - Finally, we use natural language to write comments in our code - these are descriptions of the behaviour of certain parts and represent the used programming ideas. - These comments are important when different people work on the same project - it is easier to understand what other people did. ## 4.3 Evaluation strategy - The parameters in the declaration of a function are called the formal parameters. - The parameters that are used in an actual invocation of a function are called actual parameters. - For example, in: ```python def func(a, b): return a + b func(3 + 7//2, -42 + 7) ``` - the function has formal parameters `a` and `b` and the actual parameters in the invocation are `3 + 7//2` and `-42 + 7`. - There are several kinds of how the formal and the actual parameters can be related to each other. We distinguish these kinds by their evaluation order. ## 4.3.1 Strict evaluation order - In the strict evaluation order, we start by evaluating the parameter of the function. - Once this process is done, we invoke the function with the evaluated parameters. - In the example above we would first evaluate `func(3 + 7//2, -42 + 7)` to `func(6, -35)` and then invoke the function with actual parameters 6 and 35. - The relation of these actual parameters and the formal parameters now depend on the call by convention. - We distinguish at least two types. ### Call by value - The simplest way in which the formal and the actual parameters relate is called call by value. - We can imagine that when a function is called, there are assignment operations that assign the expressions that are passed as the actual parameters to the corresponding formal parameters. - Therefore, it is also sometimes called call by assignment. - The relation between the actual and the formal parameters is like after a regular assignment operation. - Most modern programming languages (like Python, C, C++) use call by value. **Attention:** Call by value does not mean that there is no relation between the formal and the actual parameter. For example, if we pass a mutable data object to a function in Python, changes to the data object that occur in the function are visible outside the function. This is consistent with the interpretation of the call by value convention as an assignment. As an example see the implementation of `minimum()` from the last Attention-Box. ### Call by reference - If a parameter is passed by call by reference, the actual parameter may typically only be a variable name, and not an expression or a constant (literal). - If we use call by reference, then the formal and the actual parameter become synonymous. - If the formal parameter is changed in the function by an assignment statement, this is also visible outside the function. - For example, using call by reference, we could implement a swap function like this: ```python def swap(a, b): temp = a a = b b = temp x = 10 y = 20 swap(x, y) # In Python, we would still have x = 10, y = 20. # But if we used call by reference, we would now have # x = 20, y = 10. # Call by reference is supported for example in Visual Basic, C++, or Pascal. ``` ## 4.3.2 Non-strict evaluation order - In the non-strict evaluation order a function may return a result before all of its arguments have been evaluated. We also distinguish at least two types. ### Call by name - We do not evaluate the actual parameters. - Instead, we may imagine that every occurrence of a formal parameter is replaced by the corresponding actual parameter, at a textual level. - This is particularly relevant if the actual parameter is an expression. - Then, this expression is evaluated every time when the formal parameter is used, possibly with different results. ```python def func(a): print("Hello") return a * a def by_name(input): return input + input z = by_name(func(3)) # Output: # Hello # z = 18 # Since Python does not use call by name, the output is just: # Hello # z = 18 # If Python would use call by name it would evaluate as follows: # by_name(func(3)) => return func(3) * func(3) and therefore the output would be # Hello # Hello # z = 18 # Scala and the macros of the C preprocessor can use call by name. ``` - Sometimes, actual parameters are never evaluated - which might save a lot of evaluation time or ignores infinite loops or undefined expressions. - This behaviour is also used in boolean expressions in Python: ```python >>> True or 1/0 # True # Although 1/0 is not defined (division by zero), the expression still evaluates to True because, whenever one boolean value is True, the whole boolean expression True as well. Hence, Python simply ignores 1/0. However, if we would write >>> 1/0 or True # Error # the expression would cause an error, because 1/0 will be evaluated first. ``` ### Call by need - This call by convention is like call by name but whenever a parameter has been evaluated its value is stored for subsequent use. - In the example above, the expression `by_name(func(3))` would cause only one Hello-output, since func(3) is evaluated the first time and its result is stored for the second time. - Call by need is sometimes called Lazy evaluation and is used in Haskell. ## 4.4 Recursion - A function may call itself. - This is called recursion. - When this happens, each invocation of the function has its own local scope and its own variables. ```python def f(x: int): if x == 0: print(0) else: print(2*x) f(x-1) print(2 + x) ``` - The following function computes the factorial of n, i.e., n! = 1 * 2 * ... * n. ```python def factorial(n: int) -> int: val = 1 for i in range(1, n+1): val = val * i return val ``` - This approach is called iterative, since we use loops instead of recursion. T - For a recursive function, it is very important that there is at least one case in the function definition where the function does not call itself. - This case must be reachable from every possible function call. - These cases are called the recursion anchor. - The other cases are called recursion steps. - Last, we can see two detailed examples using recursion: ```python #summe (List[int]): int # Precondition: None # Effect: None # Result: The sum of the elements of the list is returned. # If the list is empty, 0 is returned # Test cases: summe([3,3,3,3]) == 12 summe([5]) == 5 summe([]) == 0 summe(range(1,101)) == 100 * 101 // 2 summe([9,-9]) == 0 summe([1, 5, 2, 4, 9]) == 13 def summe(list: list[int]) -> int: if len(list) == 0: # recursion anchor return 0 else: return list[0] + summe(list[1:]) # recursion step # mazimum (List[int]): int # Precondition: list is not empty # Effect: None # Result: The largest number of the list is returned. # Test cases: mazimum([1,2,3,2,1]) == 3 mazimum([1,2,3,4]) == 4 mazimum([4,3,2,1]) == 4 mazimum([1,1,1,1]) == 1 maximum([42]) == 42 def maximum(list: list[int]) -> int: if len(list) == 1: # recursion anchor return list[0] else: return max(list[0], maximum(list[1:])) # recursion step ``` ## 4.5 Algorithmic problems - An algorithmic problem is a problem that is suitable for processing with computers. - It consists of a formal description of the input and a formal description of the corresponding output. - Here you can see some examples: ### Factorial - Input: $n \in \mathbb{N}_0$ - Output: $n!$ ### Product - Input: $a, b \in \mathbb{R}$ - Output: $a\cdot b$ ### GCD - Input: $a, b \in \mathbb{N}_0$ - Output: greatest common divisor $gcd(a, b)$ of a and b, i.e., the largest number that is divisible by a and b (with $gcd(0,0) = 0$). ### Single-pair-shortest-path problem - Input: public transport of Berlin, start and target station - Output: shortest path between the start and the target station - In computer science we want to develop algorithms, that can provably solve algorithmic problems and which are provably efficient. - This raises some questions: How do we argue about correctness and efficiency? What means "efficient"? Does each algorithmic problem can be solved with an algorithm? - The answer for the last question is 'no', but this will not be part of this lecture (see fundamentals of theoretical computer science). ## 4.5.1 Search problems - Search problems belong to the fundamental problems of computer science. - In most cases we have some big data structures and would like to know if some given value is contained in this data structure. - First, we focus on lists, but later we also consider more complex data structures like trees. - For example, the campus management system has a huge list of student entries. - Then given the student number we can find the position of the student in this list as well as the corresponding data. - We distinguish two types of search-problems: ### Search problem - Input: list `xs` of elements some type $T$, value $k \in T$ - Output: position of the value $k$ in the list `xs` (if existing) ### Sorted search problem - Input: list `xs` with ascending sorted elements of a totally ordered universe $U$, value $k \in U$ - Output: position of the value $k$ in the list `xs` (if existing) - The search problem is obviously more general than the sorted search problem. - That means, an algorithm that computes a solution for the search problem will always compute a solution for the sorted search problem. ## 4.5.2 Linear search - The general search problem can easily be solved by going through the input list and check each position. - This is the best approach we can do. - The algorithm is called linear search and can be implemented using an iterative approach: ```python # linear_search (List [T], T): int # T is an arbitrary type # Precondition: None # Effect: None # Result: The first position of k in zs is returned. # If as does not contain k, the length of as is returned. # Test cases # Your task: find some good test cases def linear_search(xs: list[T], k: T) -> int: n = len(xs) # n is the length of xs for i in range(n): if k == xs[i]: return i return n # k is not an element of xs ``` - In the worst case the algorithm has to check each element, i.e., if the list has n elements the algorithm will check n positions. - We say that the algorithm has running time $O(n)$, which is also called linear running time.¹ ## 4.5.3 Binary search - Now consider the case that the input list is ordered. - Of course the linear search algorithm would still find a solution. - But using the fact, that the list is ordered we can develop a much better algorithm, which we call binary search. - The idea for this algorithm is as follows: Compare the value $k$ with the middle element $m$ of the list. - Then we have three different cases: - (i) If $k == m$, then we found the element and can output the position. - (ii) If $k < m $, then each element in the right half of the list must be larger than $k$. Hence, we can focus our search in the left half of the list. - (iii) If $m < k $, then each element in the left half of the list must be smaller than $k$. Hence, we can focus our search in the right half of the list. - We use a recursive approach for this algorithm: - Finally, we can argue that binary search is much better than linear search by estimating the number of elements that are compared with $k$. - First, let $n$ be the number of elements in the list `xs`. - After each comparison we discard one half of the elements (either the left or the right half). - That means in the beginning n elements are relevant, then $n/2$, then $n/4$, then $n/8$, and so on... - In general, after $t$ steps there are $n/(2^t)$ elements relevant. - The algorithm runs as long as there is at least one element relevant, after this the algorithm terminates. - Thus, we can conclude: $$ \frac{n}{2^t} \geq 1 \Leftrightarrow n \geq 2^t \Leftrightarrow t \leq log_2(n) $$ - Hence, we have shown, that binary search applied to a list of n elements needs at most $log_2(n)$ steps. - We say that binary search has running time $O(log_2(n))$, which is also called logarithmic time. - This is much better than linear time, since the linear function grows much faster than the logarithmic function. ¹We will see the O-Notation in further examples. A formal definition will be given in higher semesters.