Jump to content
Sign in to follow this  

CS EE

Recommended Posts

Hi,

I'm writing an extended essay where I compare iterative and recursive solutions to the Tower of Hanoi puzzle (link).

The recursive solution I have right now is the pretty standard recursive solution that solves the general form of the puzzle where you have to move n - 1 disks to move n disks, n - 2 disks to move n - 1 disks, etc (link).

However, the iterative solution I have is not so standard - it's based off of research conducted that shows that odd numbered disks should be moved clockwise and even numbered disks should be moved counterclockwise so that the puzzle can be solved (link). It's a somewhat unorthodox solution, but it works.

I'm stuck here, though: I can't decide if I can actually compare my two solutions. Although the clockwise/counterclockwise pattern holds true in the recursive solution, I'm worried that comparing the two solutions has become an apples to oranges comparison rather than a "green apples to red apples" comparison, if you will.

I'm a little lost here, and my advisor has limited expertise in this field. I'd appreciate any kind of advice. Thanks!

Share this post


Link to post
Share on other sites

First and foremost, I don't take CS so I'm not particularly familiar with the syllabus, nor what specifically is expected for an EE on it. I can give some advice, but I would recommend double checking things with your supervisor and/or with other users here.

Looking at the official guide booklet, comparisons of algorithms do seem to be an appropriate topic, so you look to be on the right track. There are a number of things such as complexity, efficiency, code simplicity and correctness that you could compare, along with implications and real world implementations.

In terms of the Towers of Hanoi problem however, I'm honestly not too sure if it'll work. It's generally considered as an example problem for teaching recursion, but there's not much you can do in terms of applications. If the two algorithms give the same solutions, you can't really compare asymptotic complexity. While I don't think it's much of a problem that they are different in nature, there doesn't seem to be a lot to cover.

One thing you could focus on is the choice of iteration vs recursion, then expand from there and look at other cases. Alternately, you could investigate possible generalisations to the problems, where you may find one to work better there.

Personally however, I'd recommend looking into other problems that can be solved with algorithms. My knowledge is rather limited here so I can't give specific suggestions, but I think an EE on comparing algorithms to solve a particular, useful problem would work well, if you choose the right one.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.