<p>Of course, for us in academia, most problems are fun anyway: we would not be there otherwise ;) But I understand that you might be more interested in problems which do not require much background and/or which are related to mundane topics like social games. Note that it might be harder (and more important) for you to find someone willing to comment on your solution and help you to improve it than to find a fun problem itself. For this reason,  asking a professor in your department might be a better starting point. That said, here are some suggestions as to where to find ideas, and a modest proposal of mine.</p>

<ol>
<li><p>Have a look at the  proceedings of the conference "<a href="http://www.dsi.unive.it/~fun2012/" rel="nofollow">Fun with Algorithms</a>": they should provide you with a good selection of "Fun" problems to work on, and a venue where to submit your results for feedback.</p></li>
<li><p>Check the publications of people known to consider fun problems and problems for fun. For instance:</p>

<ul>
<li><a href="http://www.mpi-inf.mpg.de/~mehlhorn/" rel="nofollow">Kurt Mehlhorn</a> has several, one of the latest being a study of a variant of the game "Master Mind", published in "<a href="https://domino.mpi-inf.mpg.de/intranet/ag1/ag1publ.nsf/AuthorEditorIndividualView/58981d4951d4ce56c1257aef004cbd53?OpenDocument" rel="nofollow">The Query Complexity of Finding a Hidden Permutation</a>" (another one of his is a mathematical model for how a mold can compute the path of minimal length in a maze).</li>
<li><a href="http://erikdemaine.org/" rel="nofollow">Erik Demaine</a> has a long sequence of such problems, one of the latest being the study of variants of the game "<a href="http://erikdemaine.org/papers/InstantInsanity_Ianfest2013/" rel="nofollow">Instant Insanity</a>".</li>
<li><a href="http://www.stat.berkeley.edu/~mossel/" rel="nofollow">Elkhanan Mossel</a> wrote a nice study of the "<a href="https://dl.acm.org/citation.cfm?id=970844.970849" rel="nofollow">Mine Sweeper game</a>".</li>
</ul></li>
<li><p>Have a look at my (modest) proposal of "fun" problem below. If you work on it, get in touch with me!</p></li>
</ol>

<hr>

<h2>Levitating Towers</h2>

<p>As an undergraduate, you probably know the problem of the <a href="https://en.wikipedia.org/wiki/Tower_of_Hanoi" rel="nofollow">Hanoi Tower</a>. If you want to "have fun", you might consider simple variants of it. Here is a very simple variant you might be interested in, which I designed for an assignment while I was a TA for an algorithm course, but never gave to students because I found it too hard for undergraduate (at least too hard for a marked assignment).</p>

<p>Consider the case where you insert and remove disks always in the middle of the tower (defined in a symmetric way when the number of disks is even, so that you always remove the last disk that you inserted), while keeping at all time the constraint that no disk stands upon a smaller one. In how many moves can you move a tower of $n$ disks from one peg to another?</p>

<p>The exact answer is not known. I obtained at the time a complicated upper bound of $2^{n/2}$ via a combination of 3 recursive functions. The graph of all possible states and transitions (a classical way to study the original Hanoi tower problem) is fragmented. I believe there should be a reduction to the original problem but did not find it when I played with it.</p>

<p>Play with it. An example of the difficulty of the analysis (say, for symmetric rules removing the lower middle disk when the number of disks on a peg is even, and inserting below the center disk when the number of disk is odd) is the case where there is $1$ small disk (e.g. $1$) on the destination peg and $2$ larger ones (e.g. $8,9$) on the source peg. This particular sub-tower of height $2$ can be moved without any intermediate peg in $2$ moves (as opposed to $3$ moves and one intermediate peg in the traditional Hanoi tower): the removal order of the source peg is the same as the insertion order of the destination peg.</p>

CC BY-SA 3.0
2013-08-22T11:55:38.217Z
Thanks @jeremy :). The TOH variant seems interesting enough..

And by 'fun', i meant 'any other' open ended problems from the domain of Theory, not necessarily about games.. theory is pretty much interesting by itself ;)

More suggestions are still welcomed :)
Subhayan
CC BY-SA 3.0
2013-08-22T14:48:22.393Z
Please see [the policy on project topic questions](http://meta.cstheory.stackexchange.com/questions/802/policy-questions-about-topic-for-research-project/).
Kaveh
CC BY-SA 3.0
2013-08-22T10:40:49.417Z
2013-08-22T10:40:49.417Z
J.y B.y
<p>What can be a possible open ended research topics in Computational Complexity (or something equally fun), for an undergraduate to think about?</p>

<p>[I am planning to take up <em>something</em> fun, however my objective is not to publish a paper, but just to think about it for the joy of the subject :) , but of course, if a paper comes along, that might be fun as well...</p>

<p>P.S. I have taken basic courses in Theory of Computing, Algorithms, Advanced Algorithms, Advanced DS and Discrete Mathematics among others.]</p>

CC BY-SA 3.0
2013-08-22T08:18:45.573Z
This depends on your strengths/weaknesses and interests.
András Salamon
CC BY-SA 3.0
2013-08-22T14:47:05.263Z
[cstheory policy on project topic questions](http://meta.cstheory.stackexchange.com/questions/802/policy-questions-about-topic-for-research-project/). Also see [about] and [help/on-topic].
Kaveh
CC BY-SA 3.0
2013-08-22T14:58:18.660Z
@Kaveh My Apologies :)
I did not realize this would be against the policies of the forum, However in my defense, I would like to state that this was asked not in the lines of pursuing a research project but in the spirit of learning something new and _think about ideas_  . 
If you still think this is wrong, I would be more careful in the future :)
Subhayan
CC BY-SA 3.0
2013-08-22T16:47:20.743Z
"I want something to think about" is not a suitable question for this site, the questions should be more focused.
Kaveh
CC BY-SA 3.0
2013-08-23T01:55:46.947Z
well, I thought I was asking for a list of open ended problems accessible for undergraduates (something like [this](http://cstheory.stackexchange.com/questions/1015/open-problems-on-the-frontiers-of-tcs) ), anyway I trust your judgement, so sure, i'll be more careful from next time :)
Subhayan
<soft-question><advice-request><project-topic>
What are the open ended questions for an CS Undergraduate to think about?
Subhayan
# What are the open ended questions for an CS Undergraduate to think about?

(Asked by: username_0 on 2013-08-22)

What can be a possible open ended research topics in Computational Complexity (or something equally fun), for an undergraduate to think about?

[I am planning to take up *something* fun, however my objective is not to publish a paper, but just to think about it for the joy of the subject :) , but of course, if a paper comes along, that might be fun as well...

P.S. I have taken basic courses in Theory of Computing, Algorithms, Advanced Algorithms, Advanced DS and Discrete Mathematics among others.]

**Tags:** soft-question, advice-request, project-topic
> **Comments:**
> **username_1**: This depends on your strengths/weaknesses and interests.  
> **username_2**: [cstheory policy on project topic questions](http://meta.cstheory.stackexchange.com/questions/802/policy-questions-about-topic-for-research-project/). Also see [about] and [help/on-topic].  
> **username_0**: @Kaveh My Apologies :) I did not realize this would be against the policies of the forum, However in my defense, I would like to state that this was asked not in the lines of pursuing a research project but in the spirit of learning something new and _think about ideas_  .  If you still think this is wrong, I would be more careful in the future :)  
> **username_2**: "I want something to think about" is not a suitable question for this site, the questions should be more focused.  
> **username_0**: well, I thought I was asking for a list of open ended problems accessible for undergraduates (something like [this](http://cstheory.stackexchange.com/questions/1015/open-problems-on-the-frontiers-of-tcs) ), anyway I trust your judgement, so sure, i'll be more careful from next time :)  

---

## 1 answers

### Answer by username_3 on 2013-08-22. Score: 0 | Accepted answer

Of course, for us in academia, most problems are fun anyway: we would not be there otherwise ;) But I understand that you might be more interested in problems which do not require much background and/or which are related to mundane topics like social games. Note that it might be harder (and more important) for you to find someone willing to comment on your solution and help you to improve it than to find a fun problem itself. For this reason, asking a professor in your department might be a better starting point. That said, here are some suggestions as to where to find ideas, and a modest proposal of mine.

1. Have a look at the proceedings of the conference "[Fun with Algorithms](http://www.dsi.unive.it/~fun2012/)": they should provide you with a good selection of "Fun" problems to work on, and a venue where to submit your results for feedback.
2. Check the publications of people known to consider fun problems and problems for fun. For instance:

   * [Kurt Mehlhorn](http://www.mpi-inf.mpg.de/~mehlhorn/) has several, one of the latest being a study of a variant of the game "Master Mind", published in "[The Query Complexity of Finding a Hidden Permutation](https://domino.mpi-inf.mpg.de/intranet/ag1/ag1publ.nsf/AuthorEditorIndividualView/58981d4951d4ce56c1257aef004cbd53?OpenDocument)" (another one of his is a mathematical model for how a mold can compute the path of minimal length in a maze).
   * [Erik Demaine](http://erikdemaine.org/) has a long sequence of such problems, one of the latest being the study of variants of the game "[Instant Insanity](http://erikdemaine.org/papers/InstantInsanity_Ianfest2013/)".
   * [Elkhanan Mossel](http://www.stat.berkeley.edu/~mossel/) wrote a nice study of the "[Mine Sweeper game](https://dl.acm.org/citation.cfm?id=970844.970849)".
3. Have a look at my (modest) proposal of "fun" problem below. If you work on it, get in touch with me!

---

## Levitating Towers

As an undergraduate, you probably know the problem of the [Hanoi Tower](https://en.wikipedia.org/wiki/Tower_of_Hanoi). If you want to "have fun", you might consider simple variants of it. Here is a very simple variant you might be interested in, which I designed for an assignment while I was a TA for an algorithm course, but never gave to students because I found it too hard for undergraduate (at least too hard for a marked assignment).

Consider the case where you insert and remove disks always in the middle of the tower (defined in a symmetric way when the number of disks is even, so that you always remove the last disk that you inserted), while keeping at all time the constraint that no disk stands upon a smaller one. In how many moves can you move a tower of $n$ disks from one peg to another?

The exact answer is not known. I obtained at the time a complicated upper bound of $2^{n/2}$ via a combination of 3 recursive functions. The graph of all possible states and transitions (a classical way to study the original Hanoi tower problem) is fragmented. I believe there should be a reduction to the original problem but did not find it when I played with it.

Play with it. An example of the difficulty of the analysis (say, for symmetric rules removing the lower middle disk when the number of disks on a peg is even, and inserting below the center disk when the number of disk is odd) is the case where there is $1$ small disk (e.g. $1$) on the destination peg and $2$ larger ones (e.g. $8,9$) on the source peg. This particular sub-tower of height $2$ can be moved without any intermediate peg in $2$ moves (as opposed to $3$ moves and one intermediate peg in the traditional Hanoi tower): the removal order of the source peg is the same as the insertion order of the destination peg.

> **Comments:**
> **username_0**: Thanks @jeremy :). The TOH variant seems interesting enough..  And by 'fun', i meant 'any other' open ended problems from the domain of Theory, not necessarily about games.. theory is pretty much interesting by itself ;)  More suggestions are still welcomed :)  
> **username_2**: Please see [the policy on project topic questions](http://meta.cstheory.stackexchange.com/questions/802/policy-questions-about-topic-for-research-project/).  

---

