Ideas for masters project in algorithmic problems?

khs · 2011-08-24 08:41:10

Hi,

I'm about to start my masters project in computer science. The topic is algorithmic problems. So I'm wondering if you have any ideas for a project?

I have some ideas, but I'd like to get more. One of the ideas is to "remake the most annoying app you are forced to use". I'm not really forced to use any annoying apps though, perhaps some of you guys are? It has to require some sort of clever algorithmic design.

Thanks!

Last edited by khs (2011-08-24 08:55:31)

Ashren · 2011-08-24 10:05:26

How about Microsoft Dynamics AX?

khs · 2011-08-24 11:44:30

Ashren wrote:

How about Microsoft Dynamics AX?

Seems like a large application with a lot of functionality. Implementing a (good) substitute would most likely not be possible in the limited amount of time I have. I'm thinking more along the lines of something lightweight, specific and perhaps computationally expensive.

cs_student · 2011-08-26 00:43:53

I have a friend working on phd. He does a work with optimization of gcc.
You could look into doing that.

karabaja4 · 2011-08-26 01:25:57

Well I could tell you some complex ones I got in touch with on my college, but they're pretty scenario-specific, so I don't know how will you like them:

1) Make a fully-playable checkers game with advanced AI.
2) Find fastest route from any point A to any point B on a grayscale map, with white pixel being the lowest altitude, and black being the highest altitude.
3) Make a system for student group substitution. This must include: StudentA from GroupA wants to switch to GroupB, but there are no spaces available in GroupB. StudentB from GroupB wants to switch to GroupC, which is also full. StudentC from GroupC wants to go to GroupA, but only switch available to him is an offer to go to GroupB from StudentB which he can execute. When he does it, he could switch with a StudentA for GroupA. But, he won't do that because he's not sure StudentA wants a spot in GroupB. Design a system which would recognize this and list all the pathways so each student can get into group he wants by switching groups to that target group. Note: this is said to be extremely difficult to make btw
4) ...

I'll edit if I remember more.
These were from few ago and it's possible I missed something in presenting them to you, I wrote them in my own words.

Nisstyre56 · 2011-08-26 01:32:12

@karabaja4, couldn't you use dynamic programming to do #3? (Assuming it's possible)

Google · 2011-08-26 06:01:51

Write a program to prevent malicious memory activity at runtime.

Write a garbage collector that runs c programs in a sandbox.

khs · 2011-08-28 20:58:15

Thanks for all the replies, I like your ideas.

I have decided on looking into a haskell implementation for pypy.

@Nisstyre56: My first intuition was: If you build a graph where the vertices are groups and the edges are student requests to switch from one group too another. Finding cycles in the graph would solve the problem.

karabaja4 · 2011-08-29 13:06:58

khs wrote:

@Nisstyre56: My first intuition was: If you build a graph where the vertices are groups and the edges are student requests to switch from one group too another. Finding cycles in the graph would solve the problem.

I don't think cycles are the answer (why go back to starting vertex?), logically it would be the longest route (chain) between vertex A and vertex B, so most students get switched. Something like that wouldn't be too hard to make with modified Dijkstra's algorithm. Since I wasn't solving this I'm not sure what the solution should be, but I'm fairly certain some problems would come up

@Nisstyre56: no idea, since I didn't thought too much of a solution.

khs · 2011-08-29 21:33:19

karabaja4 wrote:

I don't think cycles are the answer (why go back to starting vertex?), logically it would be the longest route (chain) between vertex A and vertex B, so most students get switched. Something like that wouldn't be too hard to make with modified Dijkstra's algorithm. Since I wasn't solving this I'm not sure what the solution should be, but I'm fairly certain some problems would come up

I guess you are right, I assumed all groups where full. Hmm, now I'm wondering if it could be modelled as a supply and demand problem.

Arch Linux

#1 2011-08-24 08:41:10

Ideas for masters project in algorithmic problems?

#2 2011-08-24 10:05:26

Re: Ideas for masters project in algorithmic problems?

#3 2011-08-24 11:44:30

Re: Ideas for masters project in algorithmic problems?

#4 2011-08-26 00:43:53

Re: Ideas for masters project in algorithmic problems?

#5 2011-08-26 01:25:57

Re: Ideas for masters project in algorithmic problems?

#6 2011-08-26 01:32:12

Re: Ideas for masters project in algorithmic problems?

#7 2011-08-26 06:01:51

Re: Ideas for masters project in algorithmic problems?

#8 2011-08-28 20:58:15

Re: Ideas for masters project in algorithmic problems?

#9 2011-08-29 13:06:58

Re: Ideas for masters project in algorithmic problems?

#10 2011-08-29 21:33:19

Re: Ideas for masters project in algorithmic problems?

Board footer