Quantcast

Maximum PC

It is currently Mon Sep 22, 2014 7:22 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 23 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Dijksra's Algorithm
PostPosted: Thu Nov 25, 2004 1:48 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Our assignment for our last project is to make a directed graph program that 'maps' cities and the distances between them. We were given a header file to modify (template class graph header) added this algorithm. The book we are using for the class is: Introduction to Algorithms: second edition, Cormen, Leiserson et al. Anyway, the algorithm/pseudocode is hard to follow and the algoritm does not make sense to me (or rather I cannot visualize it)

Here is a link to the notes for the class that the proff put on her site:

http://eecs.utoledo.edu/~ckiel

the class is EECS 1550.

It is the last lab posted on the lab page, and the last set of notes (or towards the end).

I am not sure how to set up a test program to use the header file to build the graph (I don't really understand how this graph stuff really works). Any and ALL help is greatly appreciated!


Top
  Profile  
 
 Post subject:
PostPosted: Thu Nov 25, 2004 6:22 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24224
Location: Granite Heaven
Start by learning the algorithm. Dijkstra's algorithm is very well known, very well documented, and the subject of much undergraduate angst.

Once you understand the algorithm, THEN go back and try to figure out the assignment. I suggest researching the algo on the web until you find an explanation that you understand ... there is a lot of info out there, if you are willing to look for it.


Top
  Profile  
 
 Post subject:
PostPosted: Fri Nov 26, 2004 4:48 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
TopCoder has a couple of articles on graph problems. You should check them out. Introduction to graphs and their data structures.


Top
  Profile  
 
 Post subject:
PostPosted: Fri Nov 26, 2004 9:58 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Thanks. I will definatly check that out. I was just a little nervous when the best programmer in my class said that he couldnt actually see it in his head like he did with the other assignments (the lucky s.o.b. is getting to intern with Intel over the spring semester! and might actually get to do some work on Warhammer 40k: Dawn of war!!!)

Thanks agian.


Top
  Profile  
 
 Post subject:
PostPosted: Fri Nov 26, 2004 2:04 pm 
Team Member Top 100
Team Member Top 100

Joined: Fri Sep 17, 2004 5:35 pm
Posts: 1176
Off-topic, but if you're looking to get your foot in the door to game programming like your friend (on Warhammer), I think you should check out Gearbox software's new initiative :
http://gbxforums.gearboxsoftware.com/po ... =insidegbx

Gearbox software is the company that ported Halo PC and are developing Brothers in Arms.

If you meet the requirements, check it out :)


Top
  Profile  
 
 Post subject:
PostPosted: Fri Nov 26, 2004 6:43 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Kybo_Ren wrote:
Off-topic, but if you're looking to get your foot in the door to game programming like your friend (on Warhammer), I think you should check out Gearbox software's new initiative :
http://gbxforums.gearboxsoftware.com/po ... =insidegbx

Gearbox software is the company that ported Halo PC and are developing Brothers in Arms.

If you meet the requirements, check it out :)

With the rash of class action lawsuits filed by employees against some of the big companies like EA, why would anyone want to work in the game industry?

Slave labor is alive and well in America (OK - that is by far an overstatement, but you get the point - hopefully, no one will be offended).


Top
  Profile  
 
 Post subject:
PostPosted: Fri Nov 26, 2004 6:46 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
Thanks. I will definatly check that out. I was just a little nervous when the best programmer in my class said that he couldnt actually see it in his head like he did with the other assignments <snip>

Then he is probably not the best programmer in your class (unless you're just starting out in CS still). ;)

Representing a graph as a two deminsional array is easy - you'll have it down in no time. When learning the actual algorithms, use the normal graph techniques you've already seen in math (nodes and edges).


Top
  Profile  
 
 Post subject:
PostPosted: Fri Nov 26, 2004 7:53 pm 
7yrs+11,000 Posts
7yrs+11,000 Posts
User avatar

Joined: Tue Jul 27, 2004 5:44 pm
Posts: 11242
Location: The kitten above is not on fire.
.....wait, is this anything like the travling busynessmad problem, becuase it smells like it.


Top
  Profile  
 
 Post subject:
PostPosted: Sat Nov 27, 2004 2:14 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
gamerfreak wrote:
.....wait, is this anything like the travling busynessmad problem, becuase it smells like it.

It is a similiar problem. I'm impressed gamerfreak. :)


Top
  Profile  
 
 Post subject:
PostPosted: Sat Nov 27, 2004 7:35 pm 
7yrs+11,000 Posts
7yrs+11,000 Posts
User avatar

Joined: Tue Jul 27, 2004 5:44 pm
Posts: 11242
Location: The kitten above is not on fire.
Quote:
It is a similiar problem. I'm impressed gamerfreak. :)

No one will be smart here after they try to figure out my binanry calculs problem


Top
  Profile  
 
 Post subject:
PostPosted: Sat Nov 27, 2004 9:33 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24224
Location: Granite Heaven
gamerfreak wrote:
Quote:
It is a similiar problem. I'm impressed gamerfreak. :)

No one will be smart here after they try to figure out my binanry calculs problem


Sounds like a challenge ... lay it on us, gamer. :D


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 28, 2004 9:11 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
No, the kid really is the best programmer in our class. (This is only the start of the 3rd semester for us).

www.streethacker.com

That is the game he programmed in his spare time over the past 2 or so years.

I guess my problem is the book sucks... lol. I am going to try to sit down and read some of it tomorrow... I wanted to do it today, but I woke up, and would have gone back to bed if my g/f had not called me. My mom made breafkast, so I decided I would get up and atleast eat..

I know this stuff is not complicated, but she doesnt explain it very well using the book we have. I had to laugh, becuase the previous assignment was a Red-Black binary tree which had to build a tree from a list of cities and their populations (sorting by name, so we just used a struct and sorted by the name field) Mine worked flawlessly, but the Proff took off a single point, becuase when the item we had to search for was not found, I did not output the number of probes into the tree it took. I did not see it as being necessary... but apparently, it was. Well, this one guy in the class (he has temper problems.) started flipping out (we were in the sun lab on our laptops... they have 10 PCs in there... but they are horribly outdated PII 333mhz.... nuff said) anyway, he was like "I have the worlds longest binary search tree!!!" He tried to be slick and use a class to handle the city data, and even though the class worked, I think that was his problem. He had all of the algorithms coded correctly, it just didnt function as a red-black tree.... I laughed... he gets so stressed and so tempromental about all that stuff... he is going to give himself an brain anurysm (sp).


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 28, 2004 9:13 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
my bad, it is the end of the 3rd semester. Our 3rd programming class in C++.... but the second class was horrid. It combined Non-linear data structures, and discrete math into one class. it was aweful.


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 28, 2004 9:49 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24224
Location: Granite Heaven
Data structures, discrete, and programming ... in one class?

You might want to look into a different programme, my friend .. 'cause that sounds pretty awful to me.


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 28, 2004 6:19 pm 
7yrs+11,000 Posts
7yrs+11,000 Posts
User avatar

Joined: Tue Jul 27, 2004 5:44 pm
Posts: 11242
Location: The kitten above is not on fire.
Jipstyle wrote:

Sounds like a challenge ... lay it on us, gamer. :D


i idid in the ll.


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 28, 2004 6:56 pm 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24224
Location: Granite Heaven
gamerfreak wrote:
Jipstyle wrote:

Sounds like a challenge ... lay it on us, gamer. :D


i idid in the ll.


Yeah, I saw it ... I was hoping it would be difficult. :P


Top
  Profile  
 
 Post subject:
PostPosted: Sun Nov 28, 2004 9:15 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
They changed the class right after we took it. They split it into 2 classes, and changed the intro programming classes to Java instead of C++ (guess they had to balance the good decision with a bad one!)


Top
  Profile  
 
 Post subject:
PostPosted: Mon Nov 29, 2004 2:56 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
gamerfreak wrote:
Quote:
It is a similiar problem. I'm impressed gamerfreak. :)

No one will be smart here after they try to figure out my binanry calculs problem

I don't not no if know ones will smart here after they figure out what the hell you just said either.


Top
  Profile  
 
 Post subject:
PostPosted: Mon Nov 29, 2004 2:59 am 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
They changed the class right after we took it. They split it into 2 classes, and changed the intro programming classes to Java instead of C++ (guess they had to balance the good decision with a bad one!)

Watch it. :twisted:


Top
  Profile  
 
 Post subject:
PostPosted: Mon Nov 29, 2004 7:40 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
lol. My bad. I am not too crazy about java. I think C++ is a better language to start out with... although Java is better than VB... correct me if I am wrong, but I read something a few months ago about VB possibly going down the tubes in the real world industry? It just doesn't cut the mustard? I don't know.


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 23 posts ]  Go to page 1, 2  Next

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group