Sure sounds very possible, you could get something to run every x minutes using cron, just with multiple crontab entries in the minute field (so run @ 5, 10, 15 ...0).
To check if the program is running, you could try:
ps -A | grep <process> | grep -v grep
and get a shell script to test output for a certain string.
I know that's a bit vague but I think it's a good way to do it of the top of my head, there may be much better ways though that might be suggested by other people.
Maybe if you give us a bit more info on which program you want to run we might be able to help you more :)