Need suggestions for scientific/logic application

[kbar1]

I'd like to spend some time killing my brain cells over a small program which nevertheless uses appreciably high logic, e.g. some scientific application. I'd classify myself as a mid-range, so please go easy. Thanks!

[mrnutty]

Try creating simulations.

- Waves simulation
- Orbital simulations
- Pathfinding simulation

[Lerner]

If you've got the time and drive to keep at it then consider stepping into the waters of graphics programming. Create code to visualize the nucleus of a helium atom, a sun with a planet spinning around it, simple molecules that spin and tumble or, a little more playfully, implement a visual solution to Rubiks cube.

[kbar1]

Thanks for the suggestions guys. Unfortunately, my graphics coding knowledge is next to nil. While I intend to correct that, in the meantime, something which doesn't require above-average graphics would be nice. Like Tower of Hanoi perhaps. Or something purely mathematical.

Also, where can I get more info on graphics programming (the kind you had suggested)? I use CodeBlocks, with MinGW.

[vijayan121]

> Or something purely mathematical.

A problem in combinatorics.

A sequence of N integers contains the numbers [1,N] in some random order. For example:

enum { N = 25 } ;
std::vector<int> seq ;
for( int i = 0 ; i < N ; ++i ) seq.push_back(i+1) ;
// the sequence contains N integers [ 1, 2, 3 ... N-1, N ]
std::random_shuffle( seq.begin(), seq.end() ) ; // in some random order

The tranformation of this sequence is a sequence of N integers where each element is the count of integers appearing later in the original sequence that are less than the number in that position.

std::vector<int> transform_sequence( const std::vector<int>& seq )
{
    std::vector<int> result_seq( seq.size(), 0 ) ;

    for( std::vector<int>::size_type i = 0 ; i < seq.size() ; ++i )
        for( std::vector<int>::size_type j = i+1 ; j < seq.size() ; ++j )
            if( seq[j] < seq[i] ) ++result_seq[i] ;

    return result_seq ;
}

If the original sequence is: [ 5 2 7 3 1 6 8 4 ]
The transformation of it is: [ 4 1 4 1 0 1 1 0 ]

If the original sequence is: [ 3 1 2 5 6 4 ]
The transformation of it is: [ 2 0 0 1 1 0 ]

If the original sequence is: [ 3 6 9 7 2 8 1 4 5 ]
The transformation of it is: [ 2 4 6 4 1 3 0 0 0 ]

As input to the program you are given the transformed sequence.
Find the original sequence (ie. the inverse of the tranformation).

(From "Combinatorial algorithms: theory and practice" by Reingold, Nievergelt and Deo)

[Mr_Null_andVoid]

A Simple Quadratic Equation Solver.

[Lerner]

Two strings made up of random sequences of the letters, A, T, C, and G . Determine what the longest common substring is and where it occurs in both strings.

[mike_2000_17]

Here are some good suggestions of algorithms to implement for practice that are a bit more substantive than those suggested already, grouped by topics of scientific computing, most of which are fundamental algorithms that are very relevant in practice too. I also noted rough line-of-code counts (assuming you don't implement each algorithm from scratch) and difficulty level, these estimates are based on my own experience implementing them in C++ (your mileage might differ).

Simple numerical methods (assuming some basic calculus knowledge):
- Golden-section search algorithm (easy, ~10-15 LOCs)
- Secant root-finding methods (Illinois, Ford, or Brent's methods) (easy, ~30 LOCs)
- Runge-Kutta numerical integration (easy, ~25 LOCs)
- Runge-Kutta-Fehlberg numerical integration (bit harder than RK, ~50 LOCs)

Simple matrix decompositions (assuming some knowledge of linear algebra):
- PLU decomposition (easy, ~15 LOCs)
- Cholesky decomposition (easy, ~15 LOCs)
- QR decomposition (medium, ~50 LOCs)
- QR Algorithm (hard, ~200 LOCs)

Optimization algorithms (assuming some knowledge of vector calculus):
- Nelder-Mead's Simplex method (medium, ~150 LOCs)
- Simplex method (medium, ~250-500 LOCs)
- Mehrotra's method for Quadratic programming (hard, ~300 LOCs)
- Gauss-Newton method (easy, ~100 LOCs)
- Quasi-Newton BFGS method (medium, ~300 LOCs)

Multi-body dynamics (assuming some knowledge of mechanics and dynamics):
- Forward kinematics of a serial robot (easy)
- Inverse dynamics of a serial robot (medium)
- Inverse kinematics of a serial robot (hard)

Graph theory:
- Dijkstra's algorithm (medium, ~150 LOCs)
- A* algorithm (medium, ~ 200 LOCs)
- Any other algorithms listed on BGL (from medium to hard)

Artificial intelligence (assuming some knowledge of probability theory):
- Clustering algorithms (easy, ~100 LOCs)
- Genetic algorithms for optimization (easy, ~200 LOCs)
- Back-propagation learning on neural-networks (medium, ~300 LOCs)
- Expectation-Maximization Algorithm (hard, ~400 LOCs)
- Q-learning algorithm (medium-easy, ~200 LOCs)

None of the above require any advanced knowledge of C++ (although it helps), none require graphics programming (although it will make things nicer in some cases), and none really require math knowledge beyond high-school (or some first-year college math courses, like vector calculus and probability theory). I would have plenty more to suggest, but if you start by browsing through the above and figure out what area is most interesting to you, that's already a great start.

[kbar1]

Whoa. Thanks guys. That should keep me busy for a long time. :icon_cheesygrin:
I'd mark off this thread as solved, but I have one more question. Where can I get info on graphics programming (beginner-level; I'm just starting)?

[mike_2000_17]

You can check explore things on gamedev.net, like the game programming wiki and NeHe's opengl tutorials. For more scientific graphics, you can check out VTK. For more simple graphics, you can check out SDL. And for GUI, you can check out Qt.