0

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!

6
Contributors
9
Replies
10
Views
5 Years
Discussion Span
Last Post by mike_2000_17
0

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.

0

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.

0

> 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)

0

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.

Edited by Lerner: n/a

0

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.

0

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)?

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.