Throw me potential CS research topics!

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

zidaneqrro
Posts: 5
Joined: Tue Dec 15, 2009 11:46 am UTC

Throw me potential CS research topics!

Postby zidaneqrro » Mon Jan 31, 2011 8:37 am UTC

Hey guys, I'm in my first year of the IB programme and I'm pretty sure I'm going to be doing a CS topic for my EE (Extended Essay). I was wondering if you guys could help me broaden potential fields or topics I can investigate. I'd like to do something I can potentially create code for or contribute to, not just rehash something that someone has already said.

Potential topics I have so far:
Genetic Algorithms
Compression Algorithms
Creating my own compiler (I dont know if this is really feasible.)

Anything else you guys think could be interesting?

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6598
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Throw me potential CS research topics!

Postby Thesh » Mon Jan 31, 2011 9:32 am UTC

Personally, I am really interested in cryptography (even though I don't understand the math enough to fully get it), which isn't necessarily CS related; I have written my own encryption algorithms which I wouldn't trust but were fun to do (although I did modify serpent to add a built-in mode of operation to increase secrecy and provide authentication, which might be fairly strong). I also find database related topics fairly interesting (creating your own simple database would be an interesting project). Of course, what I find interesting and what you find interesting isn't necessarily the same.
Summum ius, summa iniuria.

zidaneqrro
Posts: 5
Joined: Tue Dec 15, 2009 11:46 am UTC

Re: Throw me potential CS research topics!

Postby zidaneqrro » Mon Jan 31, 2011 12:29 pm UTC

Thesh wrote:Of course, what I find interesting and what you find interesting isn't necessarily the same.


Yep! I just want to see what everyone was interested in and hopefully broaden the topics I can choose from and see if I can get into them.

I'll definitely look into cryptography and databases, thanks!

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Throw me potential CS research topics!

Postby Yakk » Mon Jan 31, 2011 4:57 pm UTC

A 4000 word essay on one of those subjects? Not sure how IB EE interfaced with writing a compiler.

Writing an interpreter is in some senses easier than writing a compiler, but the language theory of writing a decent interpreter/compiler can be tricky. It is hard to understand how hard it is to write a good compiler without the language theory backing until you try and it explodes in your face. ;)

What is the format of an IB EE for CS?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

Re: Throw me potential CS research topics!

Postby Cleverbeans » Wed Feb 02, 2011 6:52 pm UTC

I think computational geometry might be of interesting as well if you're so inclined and it's relative easy to explore the problems and algorithms by sketching them out. You could also take a look at finite state machines and try to implement some simple calculations using them.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

zidaneqrro
Posts: 5
Joined: Tue Dec 15, 2009 11:46 am UTC

Re: Throw me potential CS research topics!

Postby zidaneqrro » Tue Feb 08, 2011 2:12 pm UTC

Yakk wrote:A 4000 word essay on one of those subjects? Not sure how IB EE interfaced with writing a compiler.

Writing an interpreter is in some senses easier than writing a compiler, but the language theory of writing a decent interpreter/compiler can be tricky. It is hard to understand how hard it is to write a good compiler without the language theory backing until you try and it explodes in your face. ;)

What is the format of an IB EE for CS?


Thanks for responding Yakk!

The EE consists of this:

Title page
· Abstract
· Contents page
· Introduction
· Body (development/methods/results)
· Conclusion
· References and bibliography
· Appendices

The 4000 words only include the Introduction Body and Conclusion though.

For code, the IB states that "Each line of code that appears in the body of the essay should
count as two words when calculating the length of the essay, while any internal documentation of a
program fragment should be ignored."

Do you think that this is doable in terms of an interpreter?

Thanks!

Cleverbeans wrote:I think computational geometry might be of interesting as well if you're so inclined and it's relative easy to explore the problems and algorithms by sketching them out. You could also take a look at finite state machines and try to implement some simple calculations using them.


Thanks, I'll check that out too!

There's only one advisor for Comp Sci and five of us want to do a Comp Sci EE.

Wish my proposal luck!

Thanks everyone

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Throw me potential CS research topics!

Postby Yakk » Tue Feb 08, 2011 2:54 pm UTC

I could write a simple compiler in fewer lines than that with little problem. I'd grab some toolkit to do the parsing (flex/bison, or boost::spirit, or something), build a grammar, hook production rules up, interface it with a few simple (probably stolen from the STL) data structures (for variable storage or the like), and interpret some kind of toy language.

I don't know if you could. Do you have any backing in computer grammars? Are you willing to do a really simple language? What languages are you familiar with? (something ridiculously simple, like a reverse polish notation, or LISP-style formatted language without the fancy parts, would be easier -- ie, something that is closer to assembly than anything.)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

adamse
Posts: 3
Joined: Fri May 14, 2010 11:40 am UTC

Re: Throw me potential CS research topics!

Postby adamse » Thu Feb 17, 2011 7:31 pm UTC

Remember that 4000 words are just the upper limit, there is no danger in writing 2000 words as long as they are good. I would make sure that students at your school have previously written their essays in computer science. You're probably at a larger school, but at my school most students either wrote language A1 or A2 or history essays, with the odd Biology essay; making my choice of writing in mathematics a pain since there were no teachers to help me.

userxp
Posts: 436
Joined: Thu Jul 09, 2009 12:40 pm UTC

Re: Throw me potential CS research topics!

Postby userxp » Thu Feb 17, 2011 8:03 pm UTC

I already turned my EE in. I'd like to give you a suggestion: DO ALL YOUR ESSAYS AS SOON AS POSSIBLE! FOR THE LOVE OF GOD, DON'T LEAVE BOTH LITERATURE ESSAYS FOR THE LAST WEEK!

The problem with doing CS in EE is that "Let's make a compiler!" is not an acceptable topic. You have to "formulate a research question". From the guide:
Students should not work with a research question that is too broad or too vague, too narrow, too
difficult or inappropriate. A good research question is one that asks something worth asking and that is
answerable within 40 hours/4,000 words. It should be clear what would count as evidence in relation to
the question, and it must be possible to acquire such evidence in the course of the investigation. If a
student does not know what evidence is needed, or cannot collect such evidence, it will not be possible
to answer the research question.


So you have to do something like "Will dynamic languages become the predominant class of programming languages?" or "How will the switch from IPv4 to IPv6 affect Internet users?". You could always go for Information technology in a global society.

User avatar
martin878
Posts: 63
Joined: Mon Nov 03, 2008 12:47 pm UTC
Location: Oxford, UK

Re: Throw me potential CS research topics!

Postby martin878 » Thu Feb 24, 2011 1:30 pm UTC

Something I always wanted to try was the minimum effort required to cross a hilly plain. The land is defined with some function z(x,y) which should be smooth (Bezier etc) and the objective is to get from x1,y1 to x2,y2 using the least energy. I.e. not a straight line if it takes you over a hill.

AFAIK this isn't a trivial problem, and you get to talk about lost of different optimisation techniques in your essay. Plus it makes nice landscape type pictures.

HungryHobo
Posts: 1708
Joined: Wed Oct 20, 2010 9:01 am UTC

Re: Throw me potential CS research topics!

Postby HungryHobo » Tue Mar 01, 2011 2:23 pm UTC

I did my FY project on digital image forensics/image tampering detection, it's unusual and is kinda interesting.
Basically "dat looks shopped" only in a rigorous manner and objective.
Give a man a fish, he owes you one fish. Teach a man to fish, you give up your monopoly on fisheries.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Throw me potential CS research topics!

Postby Yakk » Tue Mar 01, 2011 2:42 pm UTC

martin878 wrote:Something I always wanted to try was the minimum effort required to cross a hilly plain. The land is defined with some function z(x,y) which should be smooth (Bezier etc) and the objective is to get from x1,y1 to x2,y2 using the least energy. I.e. not a straight line if it takes you over a hill.

AFAIK this isn't a trivial problem, and you get to talk about lost of different optimisation techniques in your essay. Plus it makes nice landscape type pictures.

Quantize, error bound, run standard pathfinding? In the event that your pathfinding algorithm is making a decision at the error bound point, subdivide further?

An analytic solution would be interesting.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
martin878
Posts: 63
Joined: Mon Nov 03, 2008 12:47 pm UTC
Location: Oxford, UK

Re: Throw me potential CS research topics!

Postby martin878 » Tue Mar 01, 2011 2:54 pm UTC

Yakk wrote:Quantize, error bound, run standard pathfinding? In the event that your pathfinding algorithm is making a decision at the error bound point, subdivide further?


Yea, so an interesting, manageable project.

kmatzen
Posts: 214
Joined: Thu Nov 15, 2007 2:55 pm UTC
Location: Ithaca, NY

Re: Throw me potential CS research topics!

Postby kmatzen » Tue Mar 01, 2011 3:40 pm UTC

HungryHobo wrote:I did my FY project on digital image forensics/image tampering detection, it's unusual and is kinda interesting.
Basically "dat looks shopped" only in a rigorous manner and objective.


Did you cite the Nillius CVPR '01 paper or something?

HungryHobo
Posts: 1708
Joined: Wed Oct 20, 2010 9:01 am UTC

Re: Throw me potential CS research topics!

Postby HungryHobo » Tue Mar 01, 2011 6:21 pm UTC

actually no I believe I cited another on light source estimation.

if anything it's interesting that about 80%+ of the papers in the area seems to have less than 10 names popping up again and again and again.

I created an implementation to look for jpeg ghosts which worked surprisingly well and another to look for duplicate image regions(which didn't work so well, it turned out that the method in the paper I was basing it on was a fairly poor method and while they kinda skirted over that they only used 512*512 images for their tests it turned out that that was pretty much an upper bound unless you have lots and lots of CPU power and time.).
I'd intended to build another module for looking for incorrect chromatic abberation to tell if stuff had been inserted into an image but ran out of time.

there's a pretty wide range of methods.
long story short though it's a pretty hard problem to tell if an image has been tampered with a harmless manner(lightening,darkening, cropping or even simply re-compressing) vs whether an image has been tampered with in a serious manner(insertions, deletions etc) but not too bad if you're simply trying to decide if something is a virgin untouched image straight from the camera, particularly if you have the camera the image is claimed to have come from.
Give a man a fish, he owes you one fish. Teach a man to fish, you give up your monopoly on fisheries.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Throw me potential CS research topics!

Postby Yakk » Tue Mar 01, 2011 7:33 pm UTC

martin878 wrote:
Yakk wrote:Quantize, error bound, run standard pathfinding? In the event that your pathfinding algorithm is making a decision at the error bound point, subdivide further?

Yea, so an interesting, manageable project.
Ah yes, AP/IB level. :)

Might actually be too hard for that.

Instead of something that complex, even implementing an A* pathfinding with some tweaks would be hard enough.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Red Rule
Posts: 23
Joined: Thu Apr 29, 2010 11:24 am UTC

Re: Throw me potential CS research topics!

Postby Red Rule » Sun Mar 20, 2011 1:42 am UTC

I don't know whether this really counts as a CS topic but you could try rolling you own Linux Distro with Linux from Scratch (LFS) you could also tag on the 'hardening' of the system and delve into computer security. It'll quite a bit of practical work, but if you combine the theory with something like a build log (in which you can also explain your actions) you'd definitely be able to write 4000 words.

I apologize if this is a completely unsuitable topic for IB, but the only IB we have here is advanced English classes, we don't even have a proper normal CS class :P
"I gotta have a little bit of Orange juice
I gotta have.. my.. Orange juice!
I gotta have.. my.. Orange juice!
Juice juice juice juice juice juice juice juice
"

~Richard Feynman

archeleus
Posts: 240
Joined: Wed Sep 29, 2010 1:49 pm UTC
Location: Valenvaryon
Contact:

Re: Throw me potential CS research topics!

Postby archeleus » Sun Mar 20, 2011 9:29 am UTC

Recently someone suggested this on a kernel mailing list: full HFS+ support for Linux. It would require a lot of reading up/coding in C.
I write a blog rant here.

Algrokoz
Posts: 39
Joined: Sun May 02, 2010 1:36 am UTC

Re: Throw me potential CS research topics!

Postby Algrokoz » Tue Mar 22, 2011 2:46 am UTC

martin878 wrote:Something I always wanted to try was the minimum effort required to cross a hilly plain. The land is defined with some function z(x,y) which should be smooth (Bezier etc) and the objective is to get from x1,y1 to x2,y2 using the least energy. I.e. not a straight line if it takes you over a hill.

AFAIK this isn't a trivial problem, and you get to talk about lost of different optimisation techniques in your essay. Plus it makes nice landscape type pictures.


Crazy to think about how the human mind can give an incredibly good approximation of the answer to this problem without even really thinking about it, but when you demand replication, things get hairy. Also to fully track this problem you would need to make a clear distinction of "minimum effort" between "power" or "work." The work problem probably is trivial since it would basically just be the shortest path through the troughs. Its only when you add emphasis on balancing work and time that things get interesting.

HungryHobo
Posts: 1708
Joined: Wed Oct 20, 2010 9:01 am UTC

Re: Throw me potential CS research topics!

Postby HungryHobo » Tue Mar 22, 2011 2:24 pm UTC

sounds like the sort of problem that ant-based algorithms would be good for.
Those sorts of problems are only horrible if you want to guarantee that you have the shortest path but if you don't mind only getting within a few percent of it then you're ok.
Give a man a fish, he owes you one fish. Teach a man to fish, you give up your monopoly on fisheries.

poohat
Posts: 230
Joined: Mon Apr 07, 2008 6:21 am UTC

Re: Throw me potential CS research topics!

Postby poohat » Wed Mar 23, 2011 6:55 am UTC

martin878 wrote:Something I always wanted to try was the minimum effort required to cross a hilly plain. The land is defined with some function z(x,y) which should be smooth (Bezier etc) and the objective is to get from x1,y1 to x2,y2 using the least energy. I.e. not a straight line if it takes you over a hill.

AFAIK this isn't a trivial problem, and you get to talk about lost of different optimisation techniques in your essay. Plus it makes nice landscape type pictures.

I dont know a huge amount of differential geometry, but assuming z(x,y) and your work function werent too pathological, I suspect you could do this analytically by writing down the distance as an integral and then minimising it using variational techniques.

User avatar
modularblues
Posts: 689
Joined: Sun Nov 08, 2009 8:33 am UTC
Location: Escher's Wonderland
Contact:

Re: Throw me potential CS research topics!

Postby modularblues » Sat Mar 26, 2011 1:49 am UTC

For a more EE bent, multi-core processing :P For a physics bent, quantum computing. :P

User avatar
naschilling
Posts: 142
Joined: Wed Apr 06, 2011 2:52 pm UTC
Contact:

Re: Throw me potential CS research topics!

Postby naschilling » Wed Apr 06, 2011 3:51 pm UTC

From the time early man began to use rocks as primitive tools to the time they had refined their technique enough to form a recognizable stone "blade," 2.5 million years elapsed. Their technique changed minimally, someone just had to figure out that they wanted a blade-like shape, and go for it. The same idea is the basis of most computer innovation. No one needs to solve an impossible problem. It is just a matter of figuring out a great tool and forging it.

I'm often surprised by the number of people who attempt problems that fall under the P=NP heading. Even if only to find a "good enough" answer, there is a lot of work to be done and almost zero chance anyone will do anything that hasn't been done before. Yet there are many simple problems that no one has come up with a simple solution to solve. I compare this to art often: there is little chance that you will find a medium or technique that no one else has ever used, but you can definitely paint a picture that no one else has ever painted.

There is a problem in the Linux community that goes back to a thought expressed by Linus Torvalds: "No one really uses the kernel of an operating system." The Linux kernel is a masterful work of art, but users don't see that. While every non-trivial program "touches" the kernel in one way or another, it is usually done in a way that a non-technical user is completely oblivious to.

Apple is remarkable in their way of picking out problems that everyone else seems to just deal with and solving them. Their use of the Mach-O kernel stands as proof that a BSD-style kernel can work with a simple, intuitive user interface. Their products, such as iTunes, iPhoto, and Time Machine took problems that required several applications and technical knowledge, and reduced it to an intuitive interface.

I would suggest looking at your own computer usage habits and try to recognize the problems that you have been overlooking for years. Then try to come up with a model to fix them. For purposes of your IB essay, you don't need a working demo, only statement of a problem and an idea of how to fix it. You could use sketches and diagrams, but you should need very little actual code.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 4 guests