Optimizing Algorithms on runtime

Ask questions about projects relating to: computer science or pure mathematics (such as probability, statistics, geometry, etc...).

Moderators: MelissaB, kgudger, Ray Trent, Moderators

Optimizing Algorithms on runtime

Postby islamfaisal » Thu Nov 01, 2012 11:32 pm

Hello,

I've come up with a new idea, which is analyzing and optimizing algorithms on running time. This means that algorithms can develop as long as they run. For example, on running numerical algorithms we can analyze the output for MANY different test cases and detect some special test cases if any to add to the algorithm which may reduce the average running time. If you consider someone who wrote a primality check algorithm without noticing that every even number (except 2) can't be prime. His algorithm may be updated and will do better on average. Another one wrote an algorithm for finding Combinations and didn't notice that C(100,99) and C(100,1) are the same will be much helped by this analyzer.

Now my questions are:
Should I build an application to work with all algorithms or even numerical ones?
OR Should I choose a couple of algorithms to prove my principle on?
Does My project's idea differ from MatLab, GNU Octave and other numerical software functions or they include them? I guess they don't analyze algorithms?
Any guidance would be helped.

PS: I have 2-3 months to finish the project.
I am good with C,C#, basic algorithms & basic analysis of algorithms.
I may learn statistics, machine learning or numerical if important.
Thanks our dear experts,
Last edited by islamfaisal on Sat Nov 03, 2012 6:55 am, edited 1 time in total.
islamfaisal
 
Posts: 12
Joined: Tue Sep 18, 2012 3:25 am
Occupation: Student 12th grade
Project Question: Physics or Computer Science
Project Due Date: 31 Jan 2013
Experimental Fair: 25 Nov 2012
Project Status: I am just starting

Re: Optimizing Algorithms on runtime

Postby vysarge » Fri Nov 02, 2012 3:27 pm

Hey islamfaisal!

Correct me if I'm wrong, but I think what you want to do is produce a program/algorithm to analyze and improve the runtimes of other algorithms?

As far as I know, MatLab and similar applications don't analyze the code and algorithm itself with the purpose of optimization; rather, if they have any optimization, it'll be in compiling and information storage. So a program like the one you're proposing would be fairly new.

Personally, with two months to complete a project, I'd recommend sticking with numerical algorithms, or even with a specific set of algorithms, such as primality algorithms or the like. That way, it would be much quicker to implement, debug, and test your code, without the risk of hitting a wall and being unable to complete your project.

I'd also recommend that you take some time to look at current optimization strategies- a Google search of 'optimization algorithms' might be helpful. Perhaps you might want to look at genetic algorithms as well- I've heard good things about those.

If you have additional questions or want clarification, please feel free to ask! Good luck!
-Vysarge

~~~~~~~~~~~~~
Nature uses only the longest threads to weave her patterns, so that each small piece of her fabric reveals the organization of the entire tapestry.
-Richard Feynman
vysarge
Expert
 
Posts: 63
Joined: Tue Sep 27, 2011 4:56 pm
Occupation: Student: 12th grade
Project Question: Student volunteer.
Project Due Date: N/a: see above.
Project Status: Not applicable

Re: Optimizing Algorithms on runtime

Postby islamfaisal » Sun Nov 04, 2012 10:10 am

Vysarge,

Thanks for your reply!
Correct me if I'm wrong

Yes, this is what I'd like to do.

I have a couple of questions.
1) Is this project a scientific research or an engineering design?
2) I have an experimental fair on 25th November. What do you suggest for me to finish in this short time? There is no judging or dues in this experimental fair. However, it's to get students' feet on the right way.
3) Should I read about mathematical optimization itself?
4) How much workload would be fairly enough for this project? 10 Hours/week?
islamfaisal
 
Posts: 12
Joined: Tue Sep 18, 2012 3:25 am
Occupation: Student 12th grade
Project Question: Physics or Computer Science
Project Due Date: 31 Jan 2013
Experimental Fair: 25 Nov 2012
Project Status: I am just starting

Re: Optimizing Algorithms on runtime

Postby hhemken » Tue Nov 06, 2012 4:35 pm

islamfaisal,

This is a very interesting project. It embodies both math and engineering, so you can emphasize one or the other or both, as you wish.

I'm doubtful that there is any general way to optimize all kinds of algorithms irrespective of their domains or details. I agree with Vysarge, pick a class of related algorithms and focus on them. By Nov 25 you should be able to write a program that can optimize one or a few e.g. primality algorithms. They would have to be suitably instrumented so that your optimizer can watch what they are doing, what goes in, what comes out, timings, memory use, and whatever else you can think of.

Two broad approaches are 1) finding patterns and optimizing the operation of the algorithms based on them, and 2) creating rules and applying them somehow within the algorithms. One is machine learning, the other is sort of rule-based AI. For Nov 25, keep it as simple and clear as possible, but see if you can successfully optimize at least a couple of algorithms, sketch out your approach in a minimally functional test program, or some similar not-too-ambitious milestone.

Vysarge's suggestion to use genetic algorithms (GA) is ambitious, but would allow you to learn some very interesting notions about how things work. If you can parameterize the algorithms in such a way that "chromosomes" holding the parameters (the more parameters the better, the greater the range of possible values for each the better) are amenable to the GA process, you might be able to find some genuinely unexpected optimizations. You would learn one or two secrets of the universe!

As to questions 3 and 4, don't overextend yourself or neglect the rest of your school work or personal life. Ultimately, though, you must let your heart be your guide.

Good luck!

Heinz
Heinz Hemken
Mentor
Science Buddies Expert Forum
hhemken
Expert
 
Posts: 260
Joined: Mon Oct 03, 2005 3:16 pm

Re: Optimizing Algorithms on runtime

Postby islamfaisal » Thu Nov 08, 2012 12:39 pm

Hello,

Thanks for reply! I've decided to let the first milestone of the project analyze input, output and running time. I'll work with some numerical algorithms. I 'd like to know what topics in Machine Learning can help me in analyzing the data, checking for special test cases, symmetry. I'd like to know as well how can I deal with the input code. For example, If I wrote the algorithm to process code in C. It wouldn't be fair to write a library to help me detect loops, conditionals and their behaviour. What library or something like that should I use?
Genetic Algorithms look very interesting, it is worth going into! However, can you please explain more or give me a resource explaining about these "chromosomes" holding parameters?

Thanks & Regards,
islamfaisal
 
Posts: 12
Joined: Tue Sep 18, 2012 3:25 am
Occupation: Student 12th grade
Project Question: Physics or Computer Science
Project Due Date: 31 Jan 2013
Experimental Fair: 25 Nov 2012
Project Status: I am just starting

Re: Optimizing Algorithms on runtime

Postby hhemken » Thu Nov 08, 2012 2:10 pm

islamfaisal,

You can easily google for it, there's quite a lot of info out there. Here's one with some (supposedly) working Java code:

http://www.theprojectspot.com/tutorial- ... eginners/3

In that example the chromosomes are just strings of 0s and 1s, and the object is to evolve a population until an individual matches the target string.

In your case the fitness criterion can be anything you want. For example, you can encode some integer parameters as 0s and 1s and concatenate them all into a string and run the GA algorithm on a population as in the example above. The fitness criterion could be to 1) convert the string of 0s and 1s back into integers, 2) use the integers as parameters into an algorithm, to choose what functions the algorithm uses, or to somehow vary the way the algorithm works, and 3) to measure how efficient that algorithm variant is and use that result as a fitness score. As you can see, it's a pretty open ended mechanism that you can adapt to your needs and imagination.

There are many other things you can do. Just google "machine learning algorithms open source" or something similar. There's a lot of stuff out there.

Good luck!


Heinz
Heinz Hemken
Mentor
Science Buddies Expert Forum
hhemken
Expert
 
Posts: 260
Joined: Mon Oct 03, 2005 3:16 pm

Re: Optimizing Algorithms on runtime

Postby islamfaisal » Sun Nov 18, 2012 3:44 am

Hello again our dear experts,

I've nearly finished my representation and algorithm for optimizing primality test with Genetic Algorithms. However, I am going to use a project to implement my Genetic Algorithm. Is this OK? or Shouldn't I use this library code?

http://code.google.com/p/genericga/

Thanks & Regards,
islamfaisal
 
Posts: 12
Joined: Tue Sep 18, 2012 3:25 am
Occupation: Student 12th grade
Project Question: Physics or Computer Science
Project Due Date: 31 Jan 2013
Experimental Fair: 25 Nov 2012
Project Status: I am just starting

Re: Optimizing Algorithms on runtime

Postby hhemken » Mon Nov 19, 2012 2:46 pm

Islamfaisal,

You can write your own or use an available library, whichever works best. Note that developing, debugging, and testing your own library with known inputs and outputs adds more work.


Heinz Hemken
Heinz Hemken
Mentor
Science Buddies Expert Forum
hhemken
Expert
 
Posts: 260
Joined: Mon Oct 03, 2005 3:16 pm


Return to Grades 9-12: Math and Computer Science

Who is online

Users browsing this forum: No registered users and 1 guest

cron