Scheme - Help me come up with a few and simple programming challenges

Author

Help me come up with a few and simple programming challenges

Emre Sevinc

2005-08-27, 6:59 pm

Can programming languages really shape the ways we think
about solving problems?

http://en.wikipedia.org/wiki/S apir-Whorf_and_programming_lan guages

I know this is an endless discussion. The same questions
is asked again and again related to natural language.

What I want to do is gather some data for a comparative study. I have
a bunch of CS students who saw some Scheme programming but
no other programming language. And then it is easy to find
some programmers (close to the avg. age of the first group, which
is 19 years) who used C-like languages (C, C++, Java, Perl, PHP, etc.) but
not Lisp, Scheme or other Lisp variants.

Now I need to find some small programming challenges. The problems
need to be precise, well defined and short. The solution must not
take long in Scheme because I don't have time until
the end of the world, a couple of students in a class setting
and about 1-2 hours. Maybe 4-5 programming questions. What
I want to have is not the exact solution but capture the thought
processes of those students, thus I will tell them (or their professor
will tell) to note down every trial they make, not only the exact
solution (if they can find it).

My first candidate question is the famous permutation task, which
can be expressed roughly as "given a set of elements, write a program
that produces all the permutations of that set". My intuition and hypothesis
is that the thought process of Scheme (or Lisp) programmer is going
to be different than a non-Lisp programmer (maybe similar things can
be said for a Prolog programmer but I don't have such participants
for this study unfortunately).

I'd be very glad if comp.lang.lisp participants can come up
with small programming challenges having the characteristics
described above that can help me distinguish between those
Scheme-but-no-other-language knowing kids and another group
of non-Lisp programmers. If the challenges seem a little bit complex
but have easy and short solutions in Lisp/Scheme (contrasting the
solutions in C, Java, Perl, etc.) I believe they can help me
with this research.

Thanks in advance.

--
Emre Sevinc

eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr

Brian Harvey

2005-08-27, 6:59 pm

Emre Sevinc <emres@bilgi.edu.tr> writes:
>Now I need to find some small programming challenges. The problems
>need to be precise, well defined and short.

Given a binary search tree and two numbers LOW and HIGH, generate a list of
all the values X in the tree such that LOW <= X <= HIGH, taking advantage of
the ordering property of the BST to minimize the number of nodes examined.

This is a pretty easy four-line Lisp program. You can write exactly the same
four-line program (plus a bazillion declarations) in C/C++/Java/etc., but
nobody ever does. Many years ago I naively gave this as a midterm exam
question in a C-based CS 2 class, and *nobody* got it. Ever since then I've
used it as an example on the last day of my SICP class to illustrate why they
shouldn't think "okay, that's over, back to reality" and forget everything
they learned right after the final exam. (P.S. The students who couldn't do
it in C *had* taken the Scheme-based course, but they were all so deeply
immersed in the real-men-don't-use-recursion culture that they couldn't make
the connection.)

Ulrich Hobelmann

2005-08-28, 7:57 am

Brian Harvey wrote:
> Emre Sevinc <emres@bilgi.edu.tr> writes:
>
> Given a binary search tree and two numbers LOW and HIGH, generate a list of
> all the values X in the tree such that LOW <= X <= HIGH, taking advantage of
> the ordering property of the BST to minimize the number of nodes examined.

IMHO the problem with programs like these is that they naturally map to
functional programming, and in real life actual algorithmic development
is rather rare; most programming is more about data structures and
communication (YMMV of course).

Giving these students only exercises that encourage functional style
skewes the whole experiment I guess.

--
My ideal for the future is to develop a filesystem remote interface (a
la Plan 9) and then have it implemented across the Internet as the
standard rather than HTML. That would be ultimate

.
Ken Thompson

2005-08-28, 6:57 pm

On Sun, 28 Aug 2005 13:38:23 +0200, Ulrich Hobelmann wrote:

> Brian Harvey wrote:
>
> IMHO the problem with programs like these is that they naturally map to
> functional programming, and in real life actual algorithmic development
> is rather rare; most programming is more about data structures and
> communication (YMMV of course).
>
> Giving these students only exercises that encourage functional style
> skewes the whole experiment I guess.

http://www.itasoftware.com/careers/eng/job1.php

http://www.itasoftware.com/careers/...ers-archive.php

Ulrich Hobelmann

2005-08-28, 6:57 pm

BR wrote:
> On Sun, 28 Aug 2005 13:38:23 +0200, Ulrich Hobelmann wrote:
>
>
> http://www.itasoftware.com/careers/eng/job1.php
>
> http://www.itasoftware.com/careers/...ers-archive.php

I've seen those ads, but I don't care to apply there after graduation,
because I don't really care to do some toy programs for funny toy
exercises. Maybe in some cases stuff like that could be applied to
real-life problems, but I've never even heard of anything like that, so
I don't bother. There are more than enough problems that I can solve,
and that are currently being solved badly, so I don't put my energy in
funny math, or puzzle exercises.

--
My ideal for the future is to develop a filesystem remote interface
(a la Plan 9) and then have it implemented across the Internet as
the standard rather than HTML. That would be ultimate

.
Ken Thompson

Matthias Buelow

2005-08-29, 7:56 am

BR <brodriguez@comcast.net> wrote:

>http://www.itasoftware.com/careers/eng/job1.php

Hehe...

"Must have exceptional programming skills and be willing to code full time"

probably means:

"You'll be three months behind schedule on your first day."

mkb.

Dave Vandervies

2005-08-29, 7:02 pm

In article <deqdbd$fiu$1@abbenay.CS.Berkeley.EDU>,
Brian Harvey <bh@cs.berkeley.edu> wrote:
>Emre Sevinc <emres@bilgi.edu.tr> writes:
>
>Given a binary search tree and two numbers LOW and HIGH, generate a list of
>all the values X in the tree such that LOW <= X <= HIGH, taking advantage of
>the ordering property of the BST to minimize the number of nodes examined.
>
>This is a pretty easy four-line Lisp program. You can write exactly the same
>four-line program (plus a bazillion declarations) in C/C++/Java/etc., but
>nobody ever does. Many years ago I naively gave this as a midterm exam
>question in a C-based CS 2 class, and *nobody* got it.

That would be this four(ish)-line function?
--------
void print_sublist(struct node *n,int low,int high)
{
if(n->val > low)
print_sublist(n->left,low,high);
if(n->val >= low && n->val <= high)
printf("%d ",n->val);
if(n->val < high)
print_sublist(n->right,low,high);
}
--------
(Assumes values in the tree are unique; first and last comparision should
include equality if they aren't.)
I find it both surprising and extremely disturbing that nobody got it.
(Of course, having said that, if my solution turns out to be wrong I'll be
suitably embarrassed.) How can you do ANYTHING with trees without having
wrapped your brain around recursion well enough to do something like this?
(This ties in nicely with the "Why is recursion hard?" thread.)

For the OP: Try fuzzy lookups on multi-dimensional data (given a set of
data points, find points that are "close to" an arbitrary input point).
This is something I've had the opportunity to use in a few places at
my day job at WeBuildRadar, and it also abstracts nicely to a general
programming problem.

There are a few ways of approaching it, and which programmers find/use/
reject which ones (and why, if you can get that out of them) would
probably provide some interesting insights. Note that you can make it
a different problem based on whether you start with the complete set of
match data or have to build it incrementally (or leave it unspecified
and compare which set of initial assumptions is made by the programmers
with which solution they choose).

dave

--
Dave Vandervies dj3vande@csclub.uwaterloo.ca
How frequently "every once in a while" comes around is a direct function of
how long it takes me to forget how gross the _last_ hot dog was.
--Julie Lavoie in uw.general

Brian Harvey

2005-08-30, 3:56 am

dj3vande@csclub.uwaterloo.ca (Dave Vandervies) writes:
>void print_sublist(struct node *n,int low,int high)
>{
> if(n->val > low)
> print_sublist(n->left,low,high);
> if(n->val >= low && n->val <= high)
> printf("%d ",n->val);
> if(n->val < high)
> print_sublist(n->right,low,high);
>}

Not quite; you're *printing* the values instead of creating a list:

if (n == NULL) return NULL;
if (n->val < low)
return sublist(n->right, low, high);
if (n->val > high)
return sublist(n->left, low, high);
return append(sublist(n->left, low, high),
cons(n->val,
sublist(n->right, low, high)));

Dave Vandervies

2005-08-30, 3:56 am

In article <df0skn$une$1@abbenay.CS.Berkeley.EDU>,
Brian Harvey <bh@cs.berkeley.edu> wrote:
>dj3vande@csclub.uwaterloo.ca (Dave Vandervies) writes:
>
>Not quite; you're *printing* the values instead of creating a list:

The problem statement said "generate a list". I chose to generate it
as text representations on stdout; if you wanted it generated in a form
that could be returned to the caller, you should've been more precise.

But I do seem to have missed the base case.

Still, getting the substance right after maybe a minute and a half
of thought definitely says things about the mindset of a class of CS
students who manage to not come up with it among the bunch of them that
I'd rather didn't need to be said.

> if (n == NULL) return NULL;
> if (n->val < low)
> return sublist(n->right, low, high);
> if (n->val > high)
> return sublist(n->left, low, high);
> return append(sublist(n->left, low, high),
> cons(n->val,
> sublist(n->right, low, high)));

If I were stuffing the values into an ordered linked list in a C-like
language, I'd probably pass around a pointer to the list's head pointer
(or to a list handle structure), build it backwards, and then wrap the
whole thing with a function that handled the extra argument and reversed
the result, rather than defining lisp-ish append and cons functions.
(Mutation! Heresy! And pointers! Even worse!) But that's not something
I'd expect a CS student to come up with a polished implementation of on
an exam; I'd've probably had trouble getting the 'i's dotted and the
't's crossed when I was a CS student, and I was complaining about low
standards among CS students even back then.

dave

--
Dave Vandervies dj3vande@csclub.uwaterloo.ca
How about we maximize length instead? I think I can do one that searches the
complete works of Shakespeare (the text of which will be embedded into the
code) for dirty words before printing out the numbers. --Kevin Goodsell in CLC

Abdulaziz Ghuloum

2005-08-30, 3:56 am

Dave Vandervies wrote:

> In article <df0skn$une$1@abbenay.CS.Berkeley.EDU>,
> Brian Harvey <bh@cs.berkeley.edu> wrote:
....
>
>
> If I were stuffing the values into an ordered linked list in a C-like
> language, I'd probably pass around a pointer to the list's head pointer
> (or to a list handle structure), build it backwards, and then wrap the
> whole thing with a function that handled the extra argument and reversed
> the result, rather than defining lisp-ish append and cons functions.
> (Mutation! Heresy! And pointers! Even worse!) But that's not something
> I'd expect a CS student to come up with a polished implementation of on
> an exam; I'd've probably had trouble getting the 'i's dotted and the
> 't's crossed when I was a CS student, and I was complaining about low
> standards among CS students even back then.

You can do it without mutation and without using append (creating
only as many cons cells as needed) using an accumulator.

(define (sublist tree lo hi)
(let f ((tree tree) (ac '()))
(cond
((null? tree) ac)
((< (tree-val tree) lo) (f (tree-right tree) ac))
((> (tree-val tree) hi) (f (tree-left tree) ac))
(else
(f (tree-left tree)
(cons (tree-val tree) (f (tree-right tree) ac)))))))

Aziz,,,

Emre Sevinc

2005-08-30, 7:57 am

bh@abbenay.CS.Berkeley.EDU (Brian Harvey) writes:

> Emre Sevinc <emres@bilgi.edu.tr> writes:
>
> Given a binary search tree and two numbers LOW and HIGH, generate a list of
> all the values X in the tree such that LOW <= X <= HIGH, taking advantage of
> the ordering property of the BST to minimize the number of nodes examined.
>
> This is a pretty easy four-line Lisp program. You can write exactly the same
> four-line program (plus a bazillion declarations) in C/C++/Java/etc., but
> nobody ever does. Many years ago I naively gave this as a midterm exam
> question in a C-based CS 2 class, and *nobody* got it. Ever since then I've
> used it as an example on the last day of my SICP class to illustrate why they
> shouldn't think "okay, that's over, back to reality" and forget everything
> they learned right after the final exam. (P.S. The students who couldn't do
> it in C *had* taken the Scheme-based course, but they were all so deeply
> immersed in the real-men-don't-use-recursion culture that they couldn't make
> the connection.)

Thank you very much for the suggestion. I'll examine this and the problems
stated on ITA's site.

A programmer from comp.lang.lisp told me that I can also check
this problem:

http://en.wikipedia.org/wiki/Subset_sum_problem

which has a very simple description (but NP-complete).

I'm still in the process of collecting problems and thinking
about how to evaluate the data I can gather. It is not
going to be quantitative but qualitative which makes evaluation,
interpretation and hypothesis testing difficult (anybody knows
of a book SIED - Structure and Interpretation of [qualitative]
Experiment Data). ;-)

--
Emre Sevinc

eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr

bondowine@yahoo.com

2005-08-30, 7:01 pm

A shortest path problem can be pretty elegant in Scheme/Lisp. Just use
a simple breadth first search. The biggest problem is the input
represtation of the network.

Dave Vandervies

2005-08-30, 7:01 pm

In article <df156s$nh3$1@rainier.uits.indiana.edu>,
Abdulaziz Ghuloum <aghuloum@c-s-remove-dashes.indiana.edu> wrote:
>Dave Vandervies wrote:
>
>...
>
>
>You can do it without mutation and without using append (creating
>only as many cons cells as needed) using an accumulator.
>
>(define (sublist tree lo hi)
> (let f ((tree tree) (ac '()))
> (cond
> ((null? tree) ac)
> ((< (tree-val tree) lo) (f (tree-right tree) ac))
> ((> (tree-val tree) hi) (f (tree-left tree) ac))
> (else
> (f (tree-left tree)
> (cons (tree-val tree) (f (tree-right tree) ac)))))))

Hmm, traversing the tree backwards is a clever way to avoid having to
reverse the list when you're done. I like it.

Using an accumulator is pretty much equivalent to passing a pointer to a
head node that you mutate; which one you'd choose depends which language
you think in - procedural-think makes it seem perfectly reasonable to
mutate an object owned by the caller as a way of building a nontrivial
accumulated value (where each entry you process is just being fed to the
side effect "Add this to the list", where that can be building a linked
list, or output, or whatever else the programmer thinks is worth doing,
easily abstracted to just giving it to a callback along with a magic
cookie once the procedural-thinking programmer has grokked higher-order
functions), while functional-think leads more naturally to thinking
"Why would anyone want to do that when you can just return a value?".

dave

--
Dave Vandervies dj3vande@csclub.uwaterloo.ca
Dan, perhaps this is a marketing opportunity waiting to happen. The first
approved comp.lang.c drink?
--Ian Woods, on Dan Pop, in comp.lang.c

Sponsored Links