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)
Objective
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…
Factor? Scheme? Ruby? I’ll tell you on Friday :-)
kinda easy…
but i think, return in problem 1 will have been zero most of the time..
it might also be interesting to compare time taken for problem 3 in c++ and prolog..
anyway am sure you’ll make the class fun both yourself and the students!!..
quote
“My second objective is to make sure that the students are ready to digest whatever I’ve prepared for them as from Friday”
students don’t forget your Andrews lol!!
Only for the iterative version. The recursive version takes a substantial time as from n=20-25. My objective is that CS = Maths + Time + Space. I want them to understand that a CS looks not only for the correct solution but also for the most efficient one…
As for the rest, I’ll let you know on Friday if they are still alive!
:P
a good starting point is needed ;) but for sure as roopa said,they will have fun, directly or indirectly :D and then tackling third year would be easy ;)
Why do i have the inner feeling it will be Ruby :D,but like i said before ,if they are having fun,then its all good :)
having a quick glance at the others, scheme seems interesting as well ^^ factor as well..should see how they work…personally i thk its too bad that i/most of us are still in the concept of what to learn/think and not how to learn/think,would have been fun if it was “easy” to grasp any pl language as plain english :)
In non-recursive fibonacci function, there need not be an ‘old_a’ variable; we can manage with the two existing ‘a’ and ‘b’ variables. ;-) :P
b += a;
a = b-a;
Cool :-)
In programming languages where parallel assignment can be done (e.g. Ruby), the above can simply (and beautifully) be written as:
a, b = b, a+b