Governor's Career & Technical Academy Arlington

Computer Science 202: Week 5


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:

Leila's musings on VCU contest prob

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.