Newbie - Trying to find a small application to write

Newbie - Trying to find a small application to write

Post by BDra » Sun, 06 Feb 2005 13:08:18


I'm a computer science student, and my structures of languages teacher
asked us each to pick a language we'd never formally studied before, so
I went with Prolog. I've been slowly working through both books listed
as "Introduction" in the group's faq. Prolog Programming for AI is
especially good, since the 'exercises' at the end of sections help a
good deal.

Now. Part of this assignment is the typical paper and report, but he
also asked us to write a small, non-trivial (IE, no 'hello world')
program. I've found plenty of sample code on the web, but well - how
lame is it to yank code I found on some website?

Could one of you suggest a type of program you've seen as maybe
assignments in formal classes, or some problem a beginner like me would
be able to solve? I don't really want to regurgitate an example from
these books, though I suppose a twist on the given examples would be
ok.

Aside from that - hello! I'm actually very glad to be learning prolog.
It gives my brain a little bit of a work out, and I enjoy it. Have a
good one, all. (I also appologize if this offends anyone - I'm really
not asking for answers, just... a direction, I suppose.)

~BDrae
 
 
 

Newbie - Trying to find a small application to write

Post by Bart Demoe » Sun, 06 Feb 2005 18:58:26

Drae wrote:

Welcome !

There is a lot in the range between "hello world" and small,
non-trivial programs, and what you can manage depends on what you
have studied before, but here are some tips for what I would consider
small, non-trivial, and still doable for a student in computer science:

1) graph problems: take any basic graph algorithm (shortest
path, minimal spanning tree, vertex cover, partitioning,
maximal flow, matching ...) and implement it in Prolog;
represent the graph for instance as facts of the form
edge(a,b).
edge(b,c).
...
and work from there. This should give you programs that fit on
a page. You can find most of these somewhere on the net, but
maybe you can make your task a little more difficult by putting
some extra requirements (for instance in shortest path: you
could indicate some edges as preferential, and require that you
need a shortest path with the most preferential edges)

2) automata theory: implement one of the algos on finite
automata (union, intersection, minimization, making
deterministic ...) again, most are on the net, so don't peek
too much :-)

3) language recognition - in particular if you are interested in
parsing and using DCG's: there are examples in books, but make
up first a language that you haven't seen in a book yet (why not take
a subset of Pascal for instance) and try writing a parser
for that

4) games: take a game like chess, checkers, card game ...
(preferably something you could change the size of, or you could
have a variety of input - as for card games) and try to solve
"something" - I know that sounds vague, but say for chess: given
some initial position (I mean something half way a real match),
it is your turn and now decide whether you can threathen the
opponents queen in 2 moves

5) numerical algorithms: implement matrix multiplication
(optimally), or some algo like Karatsuba, or Shonhagen-Strassen
(I am not knowledgeable in this field - but I suppose there are
many more) - you will typically not get very interesting Prolog
programs (they are usually deterministic all the way, but still
ok)

6) ... any formal field with algos you ever studied is really
an unbounded source of inspiration for small, non-trivial
programs: computational geometry, algebra, logic ...

7) your own real life problems - depending on what kind of
person you are :-) e.g. write a program that finds for yourself
an optimal schedule for studying/sports/sleep/eat based on data
(you provide yourself) of cost, time budget, pleasure,
exhaustion, long term goals;
or if you have interest in money, take some data from the
stock market and try to find some optimal way of spending your
money there (don't make it too difficult, just particular to
you)

and optionally

8) if you have a problem you can solve in a straithforward way,
try thinking of solving it in a non-straithforward way and do it
in Prolog; e.g. maybe you can sneak in an unnecessary fix point
computation that makes your program horribly slow, but still has
some educational benefit - like using Newton-Raphson for finding
the zeros of a quadratic polynomial

Cheers

Bart Demoen