Computer Science Canada Some challenges... |
Author: | wtd [ Mon Oct 22, 2007 9:47 am ] | ||||||||||
Post subject: | Some challenges... | ||||||||||
Unless otherwise specified, any programming language may be used. Any language that is, with the exception of Turing. 1. Write a very short program to demonstrate polymorphism (in the object-oriented sense of the word). Note: you will likely want to use some form of object-oriented programming language. 2. Demonstrate statically verified structural subtyping in a language without mandatory explicit type annotations. 3. Explain how an object-oriented programming language can lack classes, and how inheritance can work in such a language. Offer some code to demonstrate. 4. Explain why "foo" in the following is available from within "bar" in the "Baz" class. Note: Ruby.
Also, explain why the "foo" in the class Baz overrides the previously defined "foo" when called from "bar" in Baz.
5. Consider the following Objective-C source file. Modify it such that the Bar class' "bar" method can be statically verified. Do not introduce a new class.
6. Translate the following to C++ from Java.
7. Write a tail-recursive factorial function which takes a single integer argument. 8. Going back to Objective-C, make the following work without modifying the Foo class, and without introducing a new class. The implementation of Foo (Foo.m) is considered unimportant and has no bearing on your work.
9. Write a simple program to demonstrate a closure. 10. Create a circular array type which can be shifted left or right such that the element on the far left will appear on the far right when the array is shifted left, and vice versa. It should be non-expandable, but the size of the array should be specified when the data structure is instantiated. The data structure must be efficiently implemented using an array. It may NOT be implemented using any sort of linked list data structure. |
Author: | PaulButler [ Mon Oct 22, 2007 5:40 pm ] |
Post subject: | RE:Some challenges... |
Good list, I will try some of these (#7 in particular has me thinking...). One question, are you ok with us posting here when we have a solution? |
Author: | rdrake [ Mon Oct 22, 2007 6:05 pm ] | ||
Post subject: | Re: Some challenges... | ||
|
Author: | wtd [ Tue Oct 23, 2007 12:43 am ] |
Post subject: | RE:Some challenges... |
Note: successfully answering all questions will earn a great deal of respect from me. |
Author: | Zampano [ Tue Oct 23, 2007 7:35 am ] |
Post subject: | Re: Some challenges... |
And I'm there's nothing more than any of us crave than the respect of a random guy on a forum somewhere miles away (unless otherwise noted). |
Author: | wtd [ Tue Oct 23, 2007 10:07 am ] |
Post subject: | RE:Some challenges... |
I'm just a "random guy" on "some internet forum"? For me, compsci.ca is more than just that. It stands for something: students coming together and taking charge of their own education, and by extension their lives. Or maybe it's just some random internet forum, and I was bored. Whichever. |
Author: | richcash [ Tue Oct 23, 2007 3:44 pm ] | ||
Post subject: | Re: Some challenges... | ||
3. Are you talking about a language like Javascript?
|
Author: | wtd [ Tue Oct 23, 2007 3:49 pm ] |
Post subject: | RE:Some challenges... |
You're pretty close, but explain it in English so I can see that you really understand it. Especially the inheritance bit. |
Author: | richcash [ Tue Oct 23, 2007 4:51 pm ] |
Post subject: | Re: Some challenges... |
Well, let's say FooBar is inheriting from Foo (as in above). I believe it is just a property of objects. Calling a function in a function will just give the result, but calling a function belonging to an object in that object (using the 'this' keyword) will give this object everything in that function (then return the result). So, we have to make a function for each object equal to Foo and then calling this function in each object will give each object everything in the function (all functions and variables). Is this right? The prototype is easier to explain. It basically says make every object of FooBar an instance of Foo(). 'FooBar.prototype' refers to every instance of FooBar. |
Author: | wtd [ Tue Oct 23, 2007 5:07 pm ] |
Post subject: | RE:Some challenges... |
You're making it sound far more complicated than it is. |
Author: | richcash [ Tue Oct 23, 2007 5:37 pm ] | ||
Post subject: | Re: Some challenges... | ||
Whever an object's function is called, the object receives all the functions and variables of that function.
So to inherit all of a structure function's stuff [Foo] into all the objects of another structure function [FooBar] (as I did in my last-last post), we need to give each object of FooBar (using 'this') a function equal to Foo so it can be called and use the above property. |
Author: | wtd [ Tue Oct 23, 2007 9:57 pm ] |
Post subject: | RE:Some challenges... |
This still does not get at the heart of the matter of how inheritance works in such a model. Javascript is not the easiest language to think about this in. |
Author: | richcash [ Fri Oct 26, 2007 9:43 am ] | ||||
Post subject: | Re: Some challenges... | ||||
Well, I might as well put my newly found knowledge of O'Caml polymorphic classes into use. So ... 10.
|
Author: | wtd [ Fri Oct 26, 2007 11:05 am ] |
Post subject: | RE:Some challenges... |
Way too much copying and moving of stuff going on. There's a more efficient way to handle this. |
Author: | richcash [ Fri Oct 26, 2007 12:55 pm ] | ||
Post subject: | Re: Some challenges... | ||
Yeah, you're right. I threw that together too quickly. Here is a more efficient way.
|
Author: | wtd [ Fri Oct 26, 2007 1:30 pm ] |
Post subject: | RE:Some challenges... |
Congratulations on figuring it out. Deceptively simple, wasn't it? |
Author: | richcash [ Fri Oct 26, 2007 3:54 pm ] |
Post subject: | Re: Some challenges... |
Indeed, nice question. Oh yeah, I'm no longer working on #3, so if someone else wants to explain it, feel free to. |
Author: | McKenzie [ Fri Oct 26, 2007 8:45 pm ] |
Post subject: | Re: Some challenges... |
wtd @ Mon Oct 22, 2007 9:47 am wrote: Unless otherwise specified, any programming language may be used. Any language that is, with the exception of Turing.
Why ??? Why put out a challenge then say no Turing? If some kid knows how to do this in Turing why discourage him/her? |
Author: | wtd [ Fri Oct 26, 2007 10:33 pm ] |
Post subject: | RE:Some challenges... |
Turing's deficiencies are well known, and do not need to be reiterated. I do not think anyone here would be shocked if I said I hope that students will take the initiative to learn some other programming language to expand their horizons. That said, if someone wants to submit a Turing solution to one of these problems, the worst that can happen is that some random guy on a web forum will be upset. Or I might be mightily impressed. Nothing is written in stone. |
Author: | PaulButler [ Sat Oct 27, 2007 4:29 pm ] | ||||
Post subject: | RE:Some challenges... | ||||
I did #7, but using a global variable seems like cheating.. is there a nicer way to do this?
|
Author: | wtd [ Sat Oct 27, 2007 7:35 pm ] |
Post subject: | RE:Some challenges... |
There is a nicer way, and you should not need to mutate any variables. |
Author: | rdrake [ Sat Oct 27, 2007 8:02 pm ] | ||
Post subject: | RE:Some challenges... | ||
I think I cheated more on #7:
|
Author: | rdrake [ Sat Oct 27, 2007 10:54 pm ] | ||
Post subject: | RE:Some challenges... | ||
Ok, finally got around to creating a legitimate entry:
|
Author: | wtd [ Sat Oct 27, 2007 11:19 pm ] |
Post subject: | RE:Some challenges... |
Thanks for playing our game. Can someone show rdrake his consolation prize? The challenge specifies that the function may take only one argument. |
Author: | rdrake [ Sat Oct 27, 2007 11:28 pm ] | ||
Post subject: | Re: RE:Some challenges... | ||
wtd @ Sat Oct 27, 2007 11:19 pm wrote: Thanks for playing our game. Can someone show rdrake his consolation prize? The challenge specifies that the function may take only one argument. Whoops!
|
Author: | wtd [ Sat Oct 27, 2007 11:35 pm ] |
Post subject: | RE:Some challenges... |
Excellent.I leave it to future challengers to figure out other ways of accomplishing this. |
Author: | Nick [ Sat Oct 27, 2007 11:59 pm ] |
Post subject: | RE:Some challenges... |
ok im working on number 10 in turing just to impress wtd ill post it when it's complete |
Author: | Nick [ Sun Oct 28, 2007 12:05 am ] | ||
Post subject: | RE:Some challenges... | ||
ok ok how is this?
and to boot its in turing |
Author: | wtd [ Sun Oct 28, 2007 9:46 am ] |
Post subject: | RE:Some challenges... |
It looks to me like there's an awful lot of copying of data going on, and the conditional in "move" can be tremendously simplified anyway. |
Author: | Saad [ Sun Oct 28, 2007 10:28 am ] | ||
Post subject: | Re: Some challenges... | ||
Here is what i used to test my submission for number 10. Language : C++ Compiler: MinGW Compiler Set.
And i have attached CircleArray.cpp For number 4. I'm going to say that due to scoping, It calls the method foo which is defined for bar not the global function. |
Author: | Nick [ Sun Oct 28, 2007 10:33 am ] | ||
Post subject: | Re: RE:Some challenges... | ||
wtd @ Sun Oct 28, 2007 9:46 am wrote: It looks to me like there's an awful lot of copying of data going on, and the conditional in "move" can be tremendously simplified anyway.
hmm it seems that it can... ill work on that and post when its better EDIT: ok its done but its not that much better but remember this is turing lol
|
Author: | wtd [ Sun Oct 28, 2007 12:16 pm ] | ||
Post subject: | Re: Some challenges... | ||
This loop can still be refactored considerably. |
Author: | Nick [ Sun Oct 28, 2007 12:43 pm ] | ||
Post subject: | RE:Some challenges... | ||
ok i did change the loop somewhat but not that much better
|
Author: | zylum [ Sun Oct 28, 2007 2:33 pm ] | ||
Post subject: | RE:Some challenges... | ||
#10
|
Author: | Nick [ Sun Oct 28, 2007 2:36 pm ] |
Post subject: | Re: Some challenges... |
wtd @ Mon Oct 22, 2007 9:47 am wrote: It should be non-expandable
nice zylum its still better than mine |
Author: | Aziz [ Sun Oct 28, 2007 3:07 pm ] | ||
Post subject: | RE:Some challenges... | ||
#10 in Java. Didn't read any other solutions before I did it Also comes with a nice tester main method, and can easily be fitted to the List interface and added to a homegrown collections framework!
|
Author: | zylum [ Sun Oct 28, 2007 11:01 pm ] |
Post subject: | RE:Some challenges... |
its not really expandable. when you create the object you set the size of the array when you call the initialize method. i wouldnt have use a flexible array if i could define the size of the array during runtime but hey, its turing. aziz > i dont think its necessary to check if the index is in bounds because this is a circular array.. if the bound is higher than the size of the array, you just move on to the next elements in the circle no? |
Author: | Aziz [ Mon Oct 29, 2007 9:48 am ] |
Post subject: | RE:Some challenges... |
Yeah, I suppose that's right! I wrote those methods before most of the rest and didn't really think much about it. |