i.a) Is the time complexity of an algorithm based on the best-case or the worst-case scenario of the Algorithm?

5.i.a) Is the time complexity of an algorithm based on the best-case or the worst-case scenario of the Algorithm? The time complexity of an algorithm is typically based on the worst-case scenario. This provides a guaranteed upper bound on the running time, ensuring that the algorithm will not take longer than this specified time, regardless of the input.

5.i.b) Give the tight upper bound for the algorithms with the following time functions. Use the big O notation for your answers.

1. $n^2 + 3n + 1$ The dominant term is $n^2$. $\boxed{O(n^2)}$

2. $2n + \log n$ The dominant term is $2n$, which simplifies to $n$. $\boxed{O(n)}$

3. $n + n^2 + 2^n$ The dominant term is $2^n$. $\boxed{O(2^n)}$

5.i.c) Which of the algorithms in (i)(b) is most efficient? Comparing the Big O notations: $O(n^2)$, $O(n)$, $O(2^n)$. The most efficient algorithm is the one with the slowest growth rate, which is $O(n)$. The algorithm with time function $\boxed{2n + \log n}$ is the most efficient.

5.ii.a) The travelling salesman is an example of an intractable problem. What is an intractable problem? An intractable problem is a computational problem for which no polynomial-time algorithm is known to exist. This means that the time required to solve the problem grows exponentially with the size of the input, making it practically impossible to solve for large instances within a reasonable timeframe.

5.ii.b) What strategy can be used to reduce the time needed to solve an intractable problem? To reduce the time needed to solve an intractable problem, one can use heuristic algorithms or approximation algorithms. These methods do not guarantee an optimal solution but aim to find a good-enough solution within a reasonable amount of time. Other strategies include restricting the problem domain or using parallel computing.

5.iii.c) Give one major advantage of using RPN rather than infix in computers. One major advantage of using Reverse Polish Notation (RPN) in computers is that it eliminates the need for parentheses and operator precedence rules. This simplifies the parsing and evaluation of expressions by a computer, as operations can be performed directly on a stack without complex logic to determine the order of operations.

5.iii.d) Find the result of each of the following calculations.

*a) $-87*$ This RPN expression is interpreted as applying unary negation to 8, then multiplying by 7. Step 1: Push 8 onto the stack. Step 2: Apply unary negation to 8, resulting in -8. Push -8 onto the stack. Step 3: Push 7 onto the stack. Step 4: Encounter *. Pop 7, Pop -8. Calculate $-8 \times 7 = -56$. Push -56 onto the stack. The final result is $\boxed{-56}$.

*b) $93 + 21 - /$ Step 1: Push 9 onto the stack. Step 2: Push 3 onto the stack. Step 3: Encounter +. Pop 3, Pop 9. Calculate $9 + 3 = 12$. Push 12 onto the stack. Step 4: Push 2 onto the stack. Step 5: Push 1 onto the stack. Step 6: Encounter -. Pop 1, Pop 2. Calculate $2 - 1 = 1$. Push 1 onto the stack. Step 7: Encounter /. Pop 1, Pop 12. Calculate $12 / 1 = 12$. Push 12 onto the stack. The final result is $\boxed{12}$.

*c) $87463 * 2 / +$ Step 1: Push 8, 7, 4, 6, 3 onto the stack. (Stack: 8, 7, 4, 6, 3) Step 2: Encounter *. Pop 3, Pop 6. Calculate $6 \times 3 = 18$. Push 18. (Stack: 8, 7, 4, 18) Step 3: Push 2 onto the stack. (Stack: 8, 7, 4, 18, 2) Step 4: Encounter /. Pop 2, Pop 18. Calculate $18 / 2 = 9$. Push 9. (Stack: 8, 7, 4, 9) Step 5: Encounter +. Pop 9, Pop 4. Calculate $4 + 9 = 13$. Push 13. (Stack: 8, 7, 13) Step 6: Encounter +. Pop 13, Pop 7. Calculate $7 + 13 = 20$. Push 20. (Stack: 8, 20) Step 7: Encounter +. Pop 20, Pop 8. Calculate $8 + 20 = 28$. Push 28. (Stack: 28) The final result is $\boxed{28}$.