This Blog is devoted to the Algorithm 2500 section thought by Dr. Simone Silvestri at the Missouri University of Science and Technology.
Students are welcome to ask questions to the instructor as well as to discuss with other students regarding the assignments and the course in general.
Sunday, 16 November 2014
Projects
In this post students can discuss and ask question on the projects.
You can advertise if you are looking for group member as well.
How does meeting at 4 at the front of the library work for you guys? If you wanna meet at some other location I would be down with that as well...just my timeframe isn't as open this week.
Could you please give a little more detail concerning the flow of time in the scenario? Is there a limited amount of time in which the algorithms are expected to execute? I am not talking about time from the perspective of the user, but within the context of the mission assignment scenario and parameters.
Could you give more specificity on "meaningful" start and end time generation? Obviously, the end time cannot precede the start time, but what other constraints should be considered?
The parameters are all correlated together. Hence, if you generate too many missions in a short time interval, no matter what algorithm you use, there will be no way of assigning the missions. Similarly, if missions are all disjoints the problem is also oversimplified.
By meaningful I mean that the final graph will show differences between the algorithms, and that missions are distributed well enough to provide insights on the final results.
I would suggest to start not caring too much about the mission distribution, and then once everything is implemented, to adjust these parameters.
Should we use Pythagorean's Theorem to see if a sensor is within the radius of some mission area? Also, when we are randomly distributing sensors, do we allow multiple sensors to have the same position?
Oh, so sensors don't have to just use integer positions?
For the Abstract Section, does it need to include a "descriptive" summary of the rest of the sections, or should it just be very general? In others words, should it be a page long, or just a paragraph?
Also, I had a few questions about submissions. So correct me if I'm wrong, but for the first deadline, we're supposed to give you a hardcopy of the first report and additionally email it to the TA. Then for the second report, we again turn in the hardcopy to you that excludes the code, but email the report and the code to the TA. Is that correct?
Lastly, what does "The project should be discussed with the TA within 1 week from the deadline of the second report" mean?
There is no fixed length, but I would say at least one page. You should describe what experiments you want to do and how, and what results you are planning to obtain. Implementation section explains how you developed your project, data structures, etc. that you have used. The two sections are completely different.
Your goal should be to have results that are meaningful (i.e. show differences between the approaches). Set an upper bound and see how the results look like, if they all look alike, then try different settings. This applies also to other parameters.
I am having significant troubles parsing the gml file. I have attempted writing my own code to do the parsing, and I have tried to use a standard pre-built parser, with no avail. Any recommendations?
Assuming you're using C++, what I did was I began by creating a storage string. I then used a while loop to begin feeding strings into the storage string, using a file istream. I had the first while loop run until it found the word "node". Then another loop ran until I had found the word "Longitude". Then, since I knew the next string was a float, I stored it into a float instead. I then continued looping until I found the word "Latitude", and stored the following float as well.
After that, I created the node using the stored coordinates, and placed it into a vector. Then, I began reading strings again, looking for either "node" or "edge". If I found node, I repeated the above process. If I found edge, I then began a similar looping process where I instead created edges and stored them in a different vector. Once I read two "]" in a row, I knew I had reached the end of the file, and terminated the loop.
If those are ignored, there are edges that reference them that cause problems. They wouldn't be a problem if you could perhaps provide some latitude and longitude values which we could assign to them.
Concerning flows, am I correct in thinking that the max flow in any event could not exceed 10? Also, am I right in assuming that would occur only in the very unlikely case that there existed a path from source to destination along which every edge had a capacity of 10?
This is not correct. The flow may take multiple paths concurrently, you can imagine that edges are pipes, you put water at the source and want to know how much water can get to the destination given the link capacities.
Hello, I have a question regarding project submission. I have just realized that tomorrow is both Monday and the submission deadline. Is there a specific time by which we must have the finished project handed to you and/or emailed to Maria? Additionally, I don't seem to be noticing that you have office hours on Mondays. Forgive me if you've told us and I've forgotten, but how should we give you our projects?
I am looking for a group for project 1.
ReplyDeleteI'm looking for a Project Group as well. Perhaps if we find one more person, we could form one
ReplyDeleteThis comment has been removed by the author.
DeleteI would be cool with that.
DeleteAlright, we can wait for someone else or just schedule a time to meet up at some point
DeleteWhen would be a good time to meet?
DeleteI'm free every day after 3:00 with the exception of Tuesday, in which I'm filled up
DeleteWanna meet up Friday after 3? If so then the question is where.
DeleteHey still looking for another group member?
DeleteAshley Painter
Yep! We would be more than happy to have you join the crew.
DeleteI don;t mind, we could just go to any of those rooms in the library
DeleteWe could meet in the library, but as to which room...i haven't been to the library much so i don't know the room numbers all to well.
DeleteCool count me in. However I won't be able to make a meeting on Friday unless its at noon.
DeleteWhat about meeting up Saturday then?
DeleteI'll be out of town all weekend. Would Monday anytime after 2 work?
DeleteI can do monday anytime after 3.
DeleteMe as well!
DeleteHow does meeting at 4 at the front of the library work for you guys? If you wanna meet at some other location I would be down with that as well...just my timeframe isn't as open this week.
DeleteSounds good. Honestly, mine is that open this week either, what with midterms and all
DeleteSounds good see you then
DeleteOk, I'm here
DeleteHey ashley, jacob and i are at te first table on the right as you enter the library.
DeleteI am currently looking for a group for project 1.
ReplyDeleteThis comment has been removed by the author.
DeleteThis comment has been removed by the author.
DeleteI would like to team up
DeleteSounds good, guessing we need to find one more person?
DeleteYeah if we could get another person that would be great, otherwise we might just have to make do with 2
DeleteI need a group too, bazrc@mst.edu
DeleteThis comment has been removed by the author.
ReplyDeleteCould you please give a little more detail concerning the flow of time in the scenario? Is there a limited amount of time in which the algorithms are expected to execute? I am not talking about time from the perspective of the user, but within the context of the mission assignment scenario and parameters.
ReplyDeleteThank you for pointing this out. I changed the project description, now missions have a start and end time.
DeleteYou can have time counter t, and a mission arrives when t is equal to the start time of the mission.
So, if the mission cannot begin at its start time it must be irrevocably rejected?
DeletePrecisely.
DeleteCould you give more specificity on "meaningful" start and end time generation? Obviously, the end time cannot precede the start time, but what other constraints should be considered?
DeleteThe parameters are all correlated together. Hence, if you generate too many missions in a short time interval, no matter what algorithm you use, there will be no way of assigning the missions. Similarly, if missions are all disjoints the problem is also oversimplified.
DeleteBy meaningful I mean that the final graph will show differences between the algorithms, and that missions are distributed well enough to provide insights on the final results.
I would suggest to start not caring too much about the mission distribution, and then once everything is implemented, to adjust these parameters.
We assume that the missions in M are sorted by start time. Do we ensure that they are or generate them randomly and let things happen as they will?
DeleteYou can sort them by start time once generated, then use the algorithms for the assignment.
DeleteIs anyone still looking for a group member or willing to take in one more? I haven't had any luck asking around.
ReplyDeleteHey do you already have a group now? Can I join your group at project2?
Deletejc5w4@mst.edu
Should we use Pythagorean's Theorem to see if a sensor is within the radius of some mission area? Also, when we are randomly distributing sensors, do we allow multiple sensors to have the same position?
ReplyDeleteEuclidean distance will be enough ;)
DeleteIf you pick sensor positions randomly using real numbers (float, double), the probability that they have the same position is 0.
Oh, so sensors don't have to just use integer positions?
DeleteFor the Abstract Section, does it need to include a "descriptive" summary of the rest of the sections, or should it just be very general? In others words, should it be a page long, or just a paragraph?
Also, I had a few questions about submissions. So correct me if I'm wrong, but for the first deadline, we're supposed to give you a hardcopy of the first report and additionally email it to the TA. Then for the second report, we again turn in the hardcopy to you that excludes the code, but email the report and the code to the TA. Is that correct?
Lastly, what does "The project should be discussed with the TA within 1 week from the deadline of the second report" mean?
Thanks
Positions can be "real" number (e.g. double).
DeleteAbstract should summarize the report, I would say 3-5 paragraphs.
The submission procedure is correct.
You need to discuss the project with the TA after the second submission, within one week from the deadline.
About how long should the Plan of Experiments section be? And how is it different from the Implementation section in report 2?
ReplyDeleteThere is no fixed length, but I would say at least one page. You should describe what experiments you want to do and how, and what results you are planning to obtain. Implementation section explains how you developed your project, data structures, etc. that you have used. The two sections are completely different.
DeleteWhen randomly generating missions, should there be an upper bound for the start time?
ReplyDeleteYour goal should be to have results that are meaningful (i.e. show differences between the approaches). Set an upper bound and see how the results look like, if they all look alike, then try different settings. This applies also to other parameters.
DeleteI am looking for a group for project2. Is there any one need a partner?
ReplyDeletejc5w4@mst.edu
For Project 2, what is the standardized way of representing the loss of a node in an adjacency matrix representation of a graph?
ReplyDeleteThere is no standard way of doing it, you can decide the more appropriate data structure.
DeleteI am having significant troubles parsing the gml file. I have attempted writing my own code to do the parsing, and I have tried to use a standard pre-built parser, with no avail. Any recommendations?
ReplyDeleteAssuming you're using C++, what I did was I began by creating a storage string. I then used a while loop to begin feeding strings into the storage string, using a file istream. I had the first while loop run until it found the word "node". Then another loop ran until I had found the word "Longitude". Then, since I knew the next string was a float, I stored it into a float instead. I then continued looping until I found the word "Latitude", and stored the following float as well.
DeleteAfter that, I created the node using the stored coordinates, and placed it into a vector. Then, I began reading strings again, looking for either "node" or "edge". If I found node, I repeated the above process. If I found edge, I then began a similar looping process where I instead created edges and stored them in a different vector. Once I read two "]" in a row, I knew I had reached the end of the file, and terminated the loop.
Hope that helps.
This comment has been removed by the author.
ReplyDeleteNode 69 is called a Hyperedge. What does that mean and what should be done with it?
ReplyDeleteyou can ignore them
DeleteIf those are ignored, there are edges that reference them that cause problems. They wouldn't be a problem if you could perhaps provide some latitude and longitude values which we could assign to them.
ReplyDeleteThat is fine as well. When dealing with real datasets, there are always some discrepancies that need to be fixed.
DeleteSo you mean we can ignore node 69 and all the edge connect with that node (there are two actually)?
ReplyDeleteThere is no specific rule, you can do anything reasonable to make the dataset usable. Remember to keep the network connected.
DeleteConcerning flows, am I correct in thinking that the max flow in any event could not exceed 10? Also, am I right in assuming that would occur only in the very unlikely case that there existed a path from source to destination along which every edge had a capacity of 10?
ReplyDeleteThis is not correct. The flow may take multiple paths concurrently, you can imagine that edges are pipes, you put water at the source and want to know how much water can get to the destination given the link capacities.
ReplyDeleteHello, I have a question regarding project submission. I have just realized that tomorrow is both Monday and the submission deadline. Is there a specific time by which we must have the finished project handed to you and/or emailed to Maria? Additionally, I don't seem to be noticing that you have office hours on Mondays. Forgive me if you've told us and I've forgotten, but how should we give you our projects?
ReplyDeleteOh, wow, I did not mean to reply to this thread... I'm sorry!
DeleteSara, I sent an email to all students regarding your questions.
DeleteRegards,
Simone Silestri