This week we will complete our study of stings.
Monday, February 14th
We'll begin class with a short quiz on the content in Chapter 4: Strings from our text.
Then, given all the work she put into it, I would like to discuss the problem that Leila and Christopher worked on from the VCU programming contest, for which Leila did some extensive reflection:
To which I want to add some of my own:
- It is a lot easier to understand a problem like this when you can restate it with clear, precise, mathematical definitions, so let's do that.
- A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.
- A monotonically increasing sequence is a sequence S such that Sn ≤ Sn+1 for all elements of the sequence.
- We can define a strictly increasing sequence as a sequence S such that Sn < Sn+1 for all elements of the sequence.
We can now rewrite the task from Problem D: A New Lottery Game precisely and succinctly:
Given a sequence of natural numbers, determine the number of strictly increasing subsequences of length 3 that can be derived from the sequence.
With that clear statement of the problem, a delightfully short Python solution to the problem was not too difficult to write. (You just gotta love Python! ;-)
Find another programming problem from either the VCU or UMD problem sets that involves strings, and develop a solution to it in C.