I want my students (equivalent first-year college students) to work on algorithmic paradigms during a 2 hours practical programming session in OCaml.
I chose the subset sum problem since it can illustrate different paradigms:
Given an array $A = [a_1, …, a_n]$ of positive integer values, and a target $T$, is there a subset $I \subset \{1, …, n\}$ such that $\sum\limits_{i\in I}a_i = T$?
The algorithms I chose are:
- brute force testing is interesting because students must iterate through all subsets;
- dynamic programming algorithm is a classical pseudo-polynomial time algorithm;
- even a (non-optimal) greedy algorithm can be worked on if we consider the optimization version of the problem.
My question is about a divide-and-conquer algorithm. I couldn't find anything about it, so I thought about a way to do it:
- If $n = 1$, answer $a_1 = T \vee 0 = T$, if $n = 0$, answer $0 = T$;
- Otherwise, if for any $t\in \{0, …, T\}$, SSE has a solution for $[a_1, …, a_{n/2}]$ and $t$, and a solution for $[a_{n/2+1}, …, a_n]$ and $T-t$, answer True;
- Otherwise answer False.
One of the problem is that the time complexity is quite ugly to compute. I found the relation: $$C(n, T) = \sum\limits_{t=0}^T\left(C\left(\frac{n}{2}, t\right) + C\left(\frac{n}{2}, T-t\right)\right) + \Theta(1)$$ I am not sure about the solution, but I found $\Theta(n^{1+\log_2 T})$ but it might be too difficult to compute (however, this is a practial session, so computing time complexity formulas is not the main objective). I finally found out that by memoizing, the algorithm can reach a time complexity of $O(nT)$, which is the same as the DP algorithm.
Currently, I have worked with students on the binary search and square-and-multiply algorithms. A future class session on mergesort and quicksort is already planned (as well as different classical examples for dynamic programming).
Have you seen the previous algorithm (or something similar) anywhere? Do you think this algorithm (and the session overall) is relevant? If not, do you have any suggestion about another interesting problem for a 2h practical programming session?
