DA4. Control Structures and Subprograms

Question 1

Question 1: We learned that when calling subprograms or functions that we can pass data to the subprogram or function by ‘value’ or by ‘reference’. Describe what each approach is, how it works and what the potential security disadvantage is when passing parameters by reference.

Passing parameters to a subprogram means supplying actual parameters during a function call, the caller can pass the r-value of the parameter (the value itself) or the l-value of the parameter (the address of the value). The former is called pass by value and the latter is called pass by reference (UoPeople, 2023).

To pass by value, the caller must consult the memory and get the value and pass it to the callee (the subprogram), such that the callee does not need to know the address of the value. This works great for variables with simple values (primitives), however, for more complex structure, the entire structure must be copied to the callee, which is inefficient.

To pass by reference, the caller must expose the address of the value to the callee, such that the callee can access the value directly. This works great for complex structures as it eliminates the need for copying the value, and then copy the result back. However, the callee can modify the value, which is a security risk. If the callee happen to be be some third part code that contains malicious code, it can modify the value and can arbitrarily guess the address of other variables and modify them as well, or change the return address to execute arbitrary code.

Question 2

Question 2: Recursion is one way of implementing recursion in programs to solve complex problems. Select one of the following three common computer science problems and describe how recursion can be used to solve this problem more efficiently (sorting, minimum cost spanning tree, knapsack problem). You must generally describe the algorithm that would be used to solve the problem and detail how recursion makes the algorithm more asymptotically efficient.

Divide and conquer is a common technique to solve problems, it works by dividing the problem into smaller sub-problems; tackling the sub-problems is usually easier and more efficient than tackling the original problem. The sub-problems are solved recursively, and the results are combined to solve the original problem (Shaffer, 2011).

Sorting is one of the problems that can be solved using divide and conquer on recursive basis. The algorithm works by splitting the array into two halves, and recursively sort each half, then merge the two halves into one sorted array. The algorithm is more efficient than other approaches such as bubble sort, as it has an O(n^2) time complexity.

The MergeSort is a divide and conquer algorithm, as it divides the array into halves until it reaches the base case, which is an array of size 1 (sorted by default). Then it merges the two halves into one sorted array until it reaches the original array.

References

• Shaffer, C. (2011). A Practical Introduction to Data Structures and Algorithm Analysis. Blacksburg: Virginia. Tech. https://people.cs.vt.edu/shaffer/Book/JAVA3e20130328.pdf. Chapter 7: Internal Sorting.
• UoPeople. (2023). CS4402: Comparative Programming Languages. Lecture Notes Unit 4.