Exercise 1 Write a function that has as parameters a string, an unsigned number k, and an array of 26 (possibly NULL) strings, one for each uppercase letter. A string is rewritten by replacing each uppercase letter with the string given for that letter in the array (if non-NULL), leaving each other character unchanged. Write the result obtained by rewriting the initial string k times (applying each rewrite on the previous result).
This problem is naturally recursive since you can view the rewriting as a tree that expands the original string, starting from the root. Alternatively, this is a particular case of composing a function (here: the replacement) k times with itself; the function operates independently on each string character.
Similar exam problem: replace some letters in all possible ways, from a replacement list
Exercise 2 Powerset Write a function that prints all subsets of a set of n elements (given as array, e.g. of numbers or strings), one per line.
Hint You can either select or not select each element, and then go on to the next.
Of course, the problem can also be solved nonrecursively: every number from 0 to 2n - 1 corresponds to a set, based on its binary representation.
Similar problem solved in the lab: n choose k.
Marius Minea Last modified: Sun Mar 1 17:30:00 EET 2015