# Maximum PC

 It is currently Sat Apr 25, 2015 1:38 am

 All times are UTC - 8 hours

 Page 1 of 2 [ 23 posts ] Go to page 1, 2  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Dijksra's AlgorithmPosted: Thu Nov 25, 2004 1:48 pm
 SON OF A GUN

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

 Post subject: Posted: Thu Nov 25, 2004 6:22 pm
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24245
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

 Post subject: Posted: Fri Nov 26, 2004 4:48 am
 Bitchin' Fast 3D Z8000*

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

 Post subject: Posted: Fri Nov 26, 2004 9:58 am
 SON OF A GUN

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

 Post subject: Posted: Fri Nov 26, 2004 2:04 pm
 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

 Post subject: Posted: Fri Nov 26, 2004 6:43 pm
 Bitchin' Fast 3D Z8000*

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

 Post subject: Posted: Fri Nov 26, 2004 6:46 pm
 Bitchin' Fast 3D Z8000*

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

 Post subject: Posted: Fri Nov 26, 2004 7:53 pm
 7yrs+11,000 Posts

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

Top

 Post subject: Posted: Sat Nov 27, 2004 2:14 am
 Bitchin' Fast 3D Z8000*

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

 Post subject: Posted: Sat Nov 27, 2004 7:35 pm
 7yrs+11,000 Posts

Joined: Tue Jul 27, 2004 5:44 pm
Posts: 11248
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

 Post subject: Posted: Sat Nov 27, 2004 9:33 pm
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24245
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.

Top

 Post subject: Posted: Sun Nov 28, 2004 9:11 am
 SON OF A GUN

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

 Post subject: Posted: Sun Nov 28, 2004 9:13 am
 SON OF A GUN

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

 Post subject: Posted: Sun Nov 28, 2004 9:49 am
 Java Junkie

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24245
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

 Post subject: Posted: Sun Nov 28, 2004 6:19 pm
 7yrs+11,000 Posts

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

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

i idid in the ll.

Top

 Post subject: Posted: Sun Nov 28, 2004 6:56 pm
 Java Junkie

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

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

i idid in the ll.

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

Top

 Post subject: Posted: Sun Nov 28, 2004 9:15 pm
 SON OF A GUN

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

 Post subject: Posted: Mon Nov 29, 2004 2:56 am
 Bitchin' Fast 3D Z8000*

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

 Post subject: Posted: Mon Nov 29, 2004 2:59 am
 Bitchin' Fast 3D Z8000*

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.

Top

 Post subject: Posted: Mon Nov 29, 2004 7:40 am
 SON OF A GUN

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 2 [ 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 forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Maximum FAQs    Forum Rules, Posting Guidelines & Announcements    The Good, The Bad & The Banned    FAQs Help/Do It Yourself    PC Building Lab    The Help Desk    PC Modding    Education & Certification Hardware    Nuts & Bolts    Portable Talk    Appraisals, Deals & Bargains (oh my!) OS/Software/Programming    Windows Parlor    Alt.OS.Abode    Games Arena    Programmers' Paradise Networking/Internet    Internet Truckstop    Network Nook In/Out    Magazine and Book Feedback    Forum & Website Feedback    Dog Pound Team Maximum PC Folding at Home    Team Maximum PC - Folding at Home - FIND CURES TO DISEASES    Team MPC - Folding Gauntlets