I’ve just started teaching a new module today to second year Computer Science students. It’s the Programming Languages module where students are supposed to be exposed to alternative paradigms and programming languages.
Today I had a lab session with one of the group of students and, as lecture hasn’t started yet, I asked them to write a number of moderately challenging C++ programs for me to make sure they were competent programmers. Those students studied the imperative portions of C++ during Year I and object-oriented Java during the first semester of Year II so I expect them to be able to complete the lab sheet.
Just for fun, here are the problems I’ve asked them to solve. I’m sure most of you will find them relatively easy but, remember, the point is to make sure everyone starts with (more or less) the same grasp of imperative programming.
Problem 1 – Two kinds of Fibonacci
Write a program in C++ that prompts the user for any non-negative integer n and displays on screen the times required (in seconds) to calculate fib(n) both recursively and iteratively.
(I told the students about the C time() function)
Problem 2 – Generation of numbers
Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22:
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16.
Write a program in C++ that prompts the user for any positive integer n and displays on screen (i) the sequence of numbers generated for that n and (ii) the cycle length.
(This is a slightly modified version of a real ACM ICPC problem)
Problem 3 – String subsequence
Given two strings a and b, print the longest string x of letters which is a subsequence of both a and b. For example,
- if a is pretty and b is typing, then x is ty,
- if a is walking and b is king, then x is king and
- if a is iris and b is aqua, then x is an empty string.
Write a program in C++ that prompts the user for the two strings a and b and displays on screen the appropriate x.
(I told the students about C++’s extensive string manipulation facilities)
My first objective is to make sure that students understand than programming can be fun and rewarding as an intellectual (unmarked) activity. My second objective is to make sure that the students are ready to digest whatever I’ve prepared for them as from Friday…