Here at uni we had our first exercise lesson for "Datastructures and Algorithms". Among other things, we had to write pseudocode to detect a so-called "famous person" in a group of random people. The characteristics of a famous person are: Everyone in the group knows the famous person The famous person knows no one from the group We were able to use a function "person x knows person y" to detect it. The algorithm I came up with uses one "for-loop". Here's the (not so) pseudocode: (there are n persons in the group) CurrentPerson = 0 for (int i=1; i<=(n-1); i++) { if Person[CurrentPerson].Knows(Person) then CurrentPerson = i; } The value in CurrentPerson is the index of the famous person after the program has executed. It's scaringly simple, yet effective. I can't find a situation in which it wouldn't find the famous person. Yet the assistant said it wasn't correct. When I asked for the reason he said he "Doesn't believe it is possible this way". Later anoter person gave a correct answer that uses two for-loops and was way more complicated than my simple solution. It just sucks you know? In a class where we learn about efficiency and stuff like that I find this disturbing. My solution is imo correct (if someone finds a flaw please do tell!) and if this was an exam my much simple and effective solution would get zero points because the corrector doesn't think it's right. Bah! /rant
i agree with the efficiency thing - its like when people say includes are great because they can make a very complex web site only 3 lines long. what they dont say is that within the files they include, there is loads and loads of code you have to write in the first place! crazy! but if you have ofund a better answer, show then it, and write down WHY its works, then its all good the only things yours may not detect is more than 1 famous person, which is the only tiem i could imagine more than 1 for loop being needed!
maybe that's why. or maybe they meant that wasn't psuedo code. have you actually implemented it? wouldn't take a mo.
Bogomip, there can't be two famous persons in one group, else the characteristics won't work. It's a paradox! I talked to another assistent (it turns out the assistent that checked my work was on his first day) and he says that my algorithm is indeed correct, but I was wrong in presuming that there is one famous person, there could be none as well. In that case my algorithm doesn't work, which I agree with. Still, scaryingly simple...
err what happens if current person knows no one? a lot of lecturers would do nasty stuff like that, to make you really learn the specification, so if no one knew person 0, and he knew no one, he wouldn't be famous person. <=(n-1) === <n so just use n, the other will make work for the optermisor. but the real problem is if the famous person isn't the only person to not know anyone. then it fails totally. if u feal ur been pissed on by the staff, bring up ur problem (at the end of lecturer is more polite) and they are normally more than happy to hear ur ideas.
I would have to say that your algorithm is wrong. It doesn't say that a person only knows the famous person. They might also know someone else in the group that isn't famous. In which case your program will find the first person in the group that they know. You solution also only looks at who person zero knows. The questions states that everyone knows the famous person so you must check that everyone knows your candidate famous person.
You're all wrong. Please read and think thanks. TheAnimus: I didn't know the optimiser could do things like that, thanks! I'll mention it next time we discuss efficiency . I will also take your advice about the lecturers . Edit: okay, for everyone who is still in the dark (you really should read my post), here are the answers: TheAnimus: Like I said, a famous person is known by everyone, and as there's one in the group, there's no one who knows nobody. The only time it wouldn't work is if there's no famous person in the group. This I also stated clearly in my first post Spike: The algorithm will indeed find the first person they know, but then it will continue from that person to find the first person they know. Eventually it'll arrive at the famous person. Because the famous person doesn't know anyone, it'll stick to the famous person. I shouldn't check that everyone knows the person, that's just the strength of my algorithm. Also, everyone note that it has been discussed and approved with the assistant who has experience in this field for several years on academic level and it is thus indeed correct. So anyone trying to proof it's wrong will only make a fool out of himself.
I don't think your code would work, for reasons Spike has stated: I can't see a way around this without using a nested loop.
Assuming there is always a famous person, you don't need to check that everyone knows this person, as the famous person is the only person to know no one (all others must know at least the famous person). The algorithm will keep setting "currentperson" to the last known person, once "currentperson" is set to the famous person, it will stay set to the famous person until the loop ends (as the famous person knows no one). Not quite sure how to explain, but if you think it doesn't work give an example of it not working...
NuTech, using a nested loop for this would be terrible innefficient. To fulfill the task completely (with the possibility of there being no famous person) you'll only need two loops after each other, not nested. Yay for JumperFly you, sir, competely got it
Didn't thread the thread properly. Was under the impression more than 1 person knew the famous person, not everyone (more of a real-world situation). Anyway, erm yeah. Go break the assistants legs.
That only suggests that each person who isn't the famous person, knows each of the other non-famous people. This needs to be specified. Assuming that the non-famous all know each other, it could work, but if it's not the case, the code would break as soon as it encounters some one who doesn't know the next person in the loop. Personally, I'd use a more water-tight, albeit longer, piece of code.
If someone doesn't know the next person in the loop, i gets incremented, and it checks for the person after that, and so on. Once the famous person is reached they will always know this person. How exactly does the code break? It doesn't make any assumptions on who the non-famous people know. If it's wrong please give a working example, showing each stage in the loop and the end result etc. I'm fairly sure you won't find one.
you nutty belgian, you stated that in ur 3rd post not first. But as for what the others are saying, there wrong, and right. assuming the data is fitting ur specification, your right. because all data *should* be in that format your okay, but things like multipule famous people can course problems. people not marking first years code properly, welcome to uni no matter how good the institute (imperal,york,cam) i know someone who's had issues with them (normally as first years only thou!)
Ok, on second look, like everyone else said, it does work, assuming there's only one famous person. Smack your assistant
TheAnimus, there is no way there could be multiple famous persons. Let's say there are two famous persons. The definition of a famous person goes: everyone knows a famous person, and the famous person knows no one. This means the first famous person must know the second famous person, yet a famous person knows no one, thus there can't be two famous persons in one group. This equals the paradox of the barber, stated by Burali-Forti on the first international Congres of Mathematicians in Zurich in 1897, which degrounded the naive version of the set-theory created in the last quarter of the 19th century by G. Cantor, if I remember correctly. And sorry about the third/first post mixup Edit: well okay, maybe it doesn't ressemble the barber-paradox that much, but it's a paradox nonetheless. Plus I wanted to pimp my l33t knowledge
