DISCLAIMER: The following videos are for educational purposes only. Cheating or any other activities are highly discouraged!! Using another person's code breaks the academic honesty guidelines. This solution is for those who have finished the problem sets and want to watch for educational purposes, learning experience, and exploring alternate ways to approach problem and is NOT meant for those actively doing the problem sets or to those who copy-paste the code. I have also emailed the staff in regards to academic honesty, so please be careful. Besides, if you copy you rob yourself of a valuable opportunity to learn and discover new things for yourselves. :) At any point if you are stuck please reach out to Discord or Facebook groups, there are literally 1000s of people there (no joke!!) who can help and guide you finish your solution!! Good luck!
Thank you so much for explaining the solutions clearly, especially in tideman. I really appreciate your method of writing on a notebook first and thoroughly explaining what's going on for each function!
finally someone explained tideman in an understandable way, thank you for giving me clarity. I have read the disclaimer, I wont copy your code, in stead I feel confident, that I can use recursion technique now.
Hi, thanks for such great explanation with textbook. Very good for understanding. Problem set 2 with Caesar wasn't hard. But problem set 3 with Tideman just broke me completely.
This was probably the best explanation video out there re. Tideman. Using a pen & paper and explaining the same thing a couple of times in a row was the key. Keep up the good word man! You will definitely see more of me.
You're one of the most talented explainers of these difficult algorithms and problems I've come across on youtube. Excellent job brother. Thank you so much.
Simply illuminating. Its 2024 now and this by far is the most indepth explanation video for the Tideman problem set I've ever came across. I finally understood the concept at the 1:00:00 mark. Thank you and subscribed!
Visualizing the algorithm has been one of the hardest parts for me, but you really helped me see what is actually happening with your video. Thanks for the information!
Thanks for the video it was great. Honestly, I couldn't budge at all during this homework. 100% stumped. I watched that lecture twice over and I didn't see anything. I had two major problems. One I had 0 idea as to why the ranks array represented the index of the candidates in the candidates array. Then you drew the 2d preferences array and everything became way easier. My only advice to people trying to do this without resorting to a walkthrough, you have to definitely do the runoff exercise first. Jumping into Tideman without being able to visualize how the preferences array works is tough. I honestly do not think the Week 3 lecture of CS50 prepares you enough for this problem.
Np. Visualizing def helps! Glad it was useful! The walkthrough videos are also pretty visual and great but yeah I agree. Problem sets can be challenging but keep at it! :)
Perfect perfect perfect. I felt like I was keeping track of four different arrays and lists in my head. Your thought process was the best out of the eight videos i’ve seen for this problem. Thank you you’re the best!
Thank you so much! I have been trying to solve tideman, but for some reason I just can't wrap my head around it, but with your explanations, I can. So thank you for not just handing the code to me, but explaining the logic behind it, so I can write the code myself.
Thanks for the breakdown, but I'm still lost on lock_pairs. Two questions: 1. I don't understand the interaction between lock_pairs and hasCycle functions. How is the IF condition below ever supposed to be true? if (locked[i][winner]) { found = true; winner = i; } Didn't we set all the elements of the locked[ ][ ] array to 'false' in main? And to assign any of the locked[ ][ ] elements to 'true' we need to first complete hasCycle, which uses (locked[i][winner]) as one of its conditions. So how does this condition get met? 2. How can 'Alice' be stored as loser in your example at 1:40:18? Let's say we're trying to find a cycle here: Alice -> Bob -> Charlie -> David -> Alice Wouldn't the original winner/loser pair that's passed into hasCycle be Alice/Bob? But then we keep overwriting the winner in the nested for loop and store 'Bob' as loser. So how can we ever get back to 'Alice'?
Disclaimer: I'm just working through this as well, so take with a boulder of salt. But to address your first question, I believe that the hasCycle function must return false at least once in order for this if statement to be true. In other words, the lock_pairs function must have already locked in at least one pair in order for this to ever be true.
@@sumeursault that makes alot of sense now cause basically the logic would be that its almost impossible for there to be a cycle with just one edge locked. btw look out for the exclamation mark "!" cause it makes more sense once you take that into consideration
I was having problems with visualizing the nuts and bolts of this particular problem(tideman) and I was stuck for a long long time building solution for a problem I had no proper understanding of. You video helped me immensely. I just looked at the notebook visualizations/ explanation and went back to the ide to implement those ideas in code without looking at your code. Hope it doesn't violate the rules of academic honesty.
It's sunday morning and I learned sooooooooo much! You're great!!! Love your style of teaching. You could join the CS50 team! Greetings from Germany!!1
Hey, I think you did an awesome job explaining! Understood everything you said, and it helped clear up some misconceptions I had with the pset. Well done and thank you!
1:04:24 why this ++? Where is this 1 being added? How? I can't understand it, and I an't find any video that explains this. How are we supposed to solve this if the lectures don't give us any clue about the problems?
Thank you so much for your explanation on the lock_pairs. I use your method to trace back the winner in locked pairs. I write the function to check the pair if it creates a cycle by calling the function itself.
Great video, you really have a way of simplifying complex problems. I would just add on a little tweak as to the selection sort algorithm. It would be better if the first for loop /*for (int i = 0; i < pair_count - 1; i++)*/ has a condition pair_count - 1 so that the last number does not selfswap.
in 1:38:00 when back tracing reaches to bob and bob is the loser of the new pair we are finding out whether to create a cycle or not, why would we skip david -> bob pair? I know that it creates a cycle but this cycle does not affect the source of the graph which is alive. I am really confused here since CS50 accepted this algorithm.
Thanks man, you were able to explain it so I understood it. I watched each section/function and then took to pen and paper to figure it out and wrote all the code myself. I even used different code that makes more sense to me :)
Just so you know strength of victory is defined as the number of voters who prefer a certain candidate not the difference between the winner and loser so you don't need to find the margin of victory.
I don't think your code is totally correct, what if while looping through locked[i][winner] the are two locked pairs which are true and the first one leads to the cycle. Your code skips the first and store the winner after that, which might not necessarily lead to the cycle. For example, if we had 6 candidates {0, 1, 2, 3, 4, 5, 6} and the graph goes like 5 -> 1 3 -> 5 2 -> 5 1 -> 2 " 1 -> 2" creates a cycle but when your code is looping locked[i][winner] in has_cycle function for this, it gets to 2-> 5, makes winner = 2 which is the path that leads to the cycle, but then changes winner = 3 which doesn't lead to the cycle before checking if winner = 2 leads to a cycle. Hope i'm making sense 😅
Hi. Nice and thorough explanation of tideman.c. I managed to get everything else right in my attempt, but didn't have any ideas on how to check the cycle. I submited tideman.c incomplete (15/18), but I did get 24/24 on runoff, so it's good :). I have a question about the hasCycle function. If we have 4 candidates (0, 1, 2, 3) and the following 6 locked pairs, in this order of strength of victory. 1. locked[0][1] 2. locked[0][2] 3. locked[1][2] 4. locked[2][3] 5. locked[0][3] 6. locked[3][1] The 6th locked pair would create a cycle 1->2->3->1 My understanding is that the hasCycle function will do the following in this situation: 1. We start with winner = 3 and loser = 1 2. On the first iteration, i = 0, we find locked[i][winner] (locked[0][3]) 3. The new winner is 0. 4. The iterations in the new for loop will be: a. locked[0][0] = not found b. locked[1][0] = not found c. locked[2][0] = not found d. locked[3][0] = not found 5. if (!found) then winner = -1 6. winner != loser 7. return false. Did I get this right? If not, can you please explain the flow for this particular case and when does the function look again in the locked pairs. If it looks again, after locked[0][3], then it will find locked[2][3] that will lead to locked[1][2], that would mean that winner == loser, so hasCycle will return true. I hope it makes sense. Sorry if it's a silly question, I started CS50 as a complete beginner, so maybe I'm missing something obvious :) Thanks,
Yes, excellent observation. You are absolutely correct. It's actually a counterexample in my algorithm fails. The test cases aren't comprehensive enough to have a scenario like this so it succeeded in my case. In my algorithm, I start from the most closest locked pair and trace backwards in this scenario mentioned. 1. We start with winner = 3 and loser = 1 On the first iteration, i = 0, we find locked[i][winner] (locked[0][3]) The new winner is 0. On the third iteration, i = 2, we find locked[i][winner] (locked[2][3]) The new winner is 2. Now inner loop ends, next iteration new winner is 2, backtrace from 2 On first iteration , 0 -> 2 yes, new winner = 0 on second iteration, 1 -> 2 yes, new winner = 1 inner loop ends, winner == loser i.e 1 == 1, so return true saying there is a cycle. This works, but in the example you gave just interchange 0 and 2 and see that my algorithm fails and returns false, no cycle, when there is indeed a cycle. My guess is that the test cases aren't comprehensive enough to have a scenario like this so it succeeded, but the true correct solution in this situation would be a recursive solution which exhausts all the possibilities from a given candidate. In other words, the order in which I scan the candidates shouldn't technically matter, but in my code, I have a certain order of scanning candidates and marking as winner, which I get "lucky" in terms of finding the right answer. Good! You found a bug or a flaw in my code :)
Hi! Thank you so much for putting in so much time and effort to explain everything so thoroughly and so clearly! I just have one question, though. When you were explaining bool hasCycle at around 1:33:12, you wrote, "while (winner != -1 ...)... .... "if (!found) { winner = -1" May I ask why you use the number (-1) and what (-1) stands for? Thank you so much!
-1 is an arbitrary value / or a flag which represents the scenario where you try to backtrace from the winner and it does not find a candidate looping back to any of the previous candidates, indicating there is no cycle. In other words, you have compared and backtraced from all the edges and you find that there isn't a candidate. But this algorithm "almost" works and is not foolproof as pointed out by @Dragos Dobre below.
I am stuck on tideman for almost 2 weeks now. I keep trying to debug my code but I am still getting the wrong results. It stresses me that I haven't been able to solve it for such a long time, should I watch this video to see the explanation or keep trying? Honestly whenever I think about trying to debug it again it's turning me off completely and it gives me a prematurely brain fog if I take action. I watched Lecture 4(memory) and understood everything in it, but tideman still giving me hell. What should I do? Would such a misdeed be forgiven? Really need advice. Update: I fixed my code completely after I came back from my first day at the gym today. Physical activity is what helped me get it done. Much clearer vision thanks to it, and also more happy. And this was day one.
Two golden steps which work extremely well when you're stuck: 1. Tackle a problem with a fresh mind (which is what you did) 2. Break down the problem into small parts and tackle each one, one at a time. In this case, try to tackle each function separately by writing down and thinking about what it should do.
Thank you for such a detailed walkthrough. I am new to CS 50. Your video helps me understand the computer logic so much clearer. Though I am still struggling on the Lock_Pair part. If there are two or more branches in the locked pairs, does hasCycle still cover the condition? For example, if my current locked pairs are as follows: Charlie -> David and Alice -> Bob -> David; and the new pair is David -> Alice; when traceback, will I fall into the Charlie -> David branch, then the hasCycle will return false, though there is a loop in the other branch. Could you help me clarify this scenario? Really appreciated.
Great video!! Could you please explain the reason behind incrementing preferences array in record_preferences funtion at line 150 ? I unaware why this is required. Thanks in advance!!
They're building a table of voters preference of candidates vs all other candidates. The ++ acts as a tally for each candidate that a voter prefers over another. So if we have Alice, Bob and Charlie and they prefer Bob, Charlie, Alice, this is stored in ranks array as 1,2,0. So we want to tally once for bob over charlie, once for bob over alice, and once for charlie over alice. That is represented by preferences[1][2]++, preferences[1][0]++ and preferences[2][0]++. Once that gets recorded by the record_preference function, the ranks array is reset and takes the preferences from the next voter.
i understand why in cycles like Bob -> Alice -> Charlie ->Bob are found with this function. but in case we have something like. 1. Bob -> Alice -> Charlie ->Bob and also 2. Peter -> Susan-> Charlie -> Bob. Why could it not be the case that, the function returns no cycle because if the function goes down the second path and (charlie,susan,peter) it then returns no cycle although there is one?! I would really appreciate your answer.
Man it was tough to visualize but this video helped me understand the question in a much clearer way. I do have prior programming experience, however with the lack of more advanced ds, it does become really difficult. Now I appreciate OOPs!
1)what is the difference between (candidates_count) and (candidate.count); and 2) when im seeing some answers like your answer i found that there somethings that they didnot tell us about it like break ; and 3) sometimes i cant make the logic by myself im studing programing by myself im 16 years i dont know what i should do when i studing programing if you can tell what is the best way to study it and achieve all the information >>>>>>>>>>>>>>>>>>>>>>>>>i hope you will answer me ! >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>thanks !!
1. Candidate dot count, is a syntax used when you are accessing a field inside a struct. In this case, count represents a field defined in struct candidate. 2. Break is just a keyword to tell to the program, just exit early in the program, no need to loop further. 3. Best way to study is to visualize and solve it by hand, then find out what actions your brain took to get to the answer, then make the computer do exactly that, step by step.
@@algorithmsillustrator3313 thanks alot , but what if i cant answer some of the psets and i returned and repeat the lesson again and i really understand it really but when i try to answer one of the sets i stuck on it for about 3 days and cant answer it im really triyng to learn programing i dont know what should i do but im tring and thanks again . :)
I mean i cant make the logic of the program and im not stupied i have a good brain . all my family are doctors so i dont know what to do ??????????????????????????????????????????????????????
I am confused about preferences array increment, Will it increment the values inside the array or what? and if it is increment preferences as a whole then how it is helping the vote count to the respective candidate? sorry if this is a silly question, I tried to find the answer, but I felt none have traced the program like you do on paper which is very easy and simple to grasp.
@@algorithmsillustrator3313 check50" reported an error with "sort_pairs", the rest were all green! Here is the code for the sort_pairs function(insertion sort) pair temp; for (int i = 1, j; i < pair_count; i++) { temp = pairs[i]; j = i - 1; for (; j >= 0 && (preferences[pairs[j].winner][pairs[j].loser] - preferences[pairs[j].loser][pairs[j].winner]) < (preferences[temp.winner][temp.loser] - preferences[temp.loser][temp.winner]); j++) { pairs[j + 1] = pairs[j]; } pairs[j + 1] = temp; } return; Please let me know where I have made a mistake. Edit: I have made the correction. Thanks for the video
bro please explain me one thing you used the global variables and use them across different function but how that variable keep on updating its value from one function to another , because when i was doing this i had to use the static function for allowing variable to update its value
It was a great video but i want to ask that in Tideman while doing vote function why do we need found_function.After finding the name in candidates string by strcmp can't we just make "ranks[rank] = i" in that 'if function' and then return true.
Hi Aman, are you talking about updating ranks array as soon as it is found and returning true immediately after that? Yes that will also work. It's personal choice. You can write it however you want. :) I looked for a not or false condition and updated accordingly but you could update as soon as you find true for strcmp.
Hi thanks for your video, i stuck in sort for days, your video did a great help! however, i'm still lost on the final part of the function, what does it mean? pair temp = pairs[max index] pair[max index] = pairs [i] pairs[i] = temp could you explain them one by one please?
I have a question regarding lock_pairs in tideman. what if in pair[0] we have a->b; pair[1]: c->d and pair[2]: d->b. According to your algorithm there could be a cycle cuz the loser in pair[2] which is b was visited in pair[0], this actually is not a cycle. Your algo is assuming that there are links throughout all pairs which might not be true.
No not exactly, here's what will happen for that scenario, has_cycle(a, b) -> returns false , no cycle, so far graph looks like this: a->b has_cycle(c, d) -> returns false, no cycle, so far graph looks like this: a-> b, c -> d then we come to has_cycle(d, b): in this case, store loser = b, and backtrack from winner which in this case is d, who locks onto d? does 'a' lock onto d-> no does 'b' lock onto d -> no does 'c' look onto d -> yes, mark 'c' as new winner and backtrack from c, who locks onto c? does 'a' lock onto c-> no does 'b' lock onto c -> no does 'c' lock onto c -> no does 'd' lock onto c -> no since, no one locks onto 'c' , mark winner as -1, exit out of loop and return false meaning there is no cycle created if you insert this edge, hence there is no cycle.
Hello, first of all thank you so much for your help. I really needed. I was doing the first part of runoff and my compiler said preferences[vote][candidate] = found is past the end of the array :( any idea why?
Apologies for the delayed response but I believe it could be because you’re running past the bounds of the array .can you re-check the bounds. If you’re still stuck I recommend asking help on discord
because it's deisgned to be mutable as per the programming assignment requirements i htink. I think i just followed the guideleines of the programming assignment.
Please first check out the walkthrough and Brian's explanation of tabulate function. Then, the only thing you need to figure out are the inputs and outputs and the algorithm. Once you realize the 2d array manipulation and how to put preferences / votes for individuals, that's the essence of tabulate function.
@@algorithmsillustrator3313 Thanks. this was very helpful. One more thing. You initialized the min_votes variable to crazy high value. what if we initialize it to 101, as we have defined the voters to max 100. how it can exceed 100?
I spent the past 4 hours trying to figure out recordpreferences for tideman with multiple layers of nested for-loops and finally had to come here and see that it's supposed to be done in 3 lines..... What am I doing so wrong?????
I think there is a little mistake in the code for cycle check in tideman. You wrote: if (locked[i][winner]) { found = true; winner = i; } But shouldnt there be the i counter reseted to zero if found is true? Like this: if (locked[i][winner]) { found = true; winner = i; i = 0; }
If we do that, I think the loop will go on forever potentially since when we find the winner we set i = 0 and the loop condition i < candidate_count will always be true
This is awesome. Thanks so much for your effort in explaining the tideman algorithm in particular. I have a question which is probably a bit silly but it refers to locked pairs In the hasCycle function you use the following if (locked[i][winner]) { found = true; winner = i; } I was wondering what what the 'if statement' was checking for in the locked array? Or if it's not checking anything what function does it perform? Thanks again
Sorry for the late reply. The if checks whether another candidate is locked on to a particular candidate. This piece of information can be found from the locked 2d matrix
For runoff: The is_tie section wasn't working for me. That area is overly complicated. Here's what I did for the is_tie section: bool is_tie(int min) { // Determine if tie for (int i = 0; i < candidate_count; i++) { if (!candidates[i].eliminated) if (candidates[i].votes != min) return false; } return true; }
I ended up receiving the answer from chatgpt, as I didn't want to research anything and I was already confused by the explanation... if I had found your channel in time, I would have done it without researching... :( . (Now I'm going to read and understand what he told me, even if it's cheating, I'm going to research and clear all my doubts and also understand the logic of his video, especially the lock_pairs part, where I was confused and couldn't...) I didn't want to get the answer... sorry.
Are you Indian? //I know, it's none of my business, but I kind of felt like you are an Indian and my curiosity has forced me to ask this question😅 printf('Your videos are really very helpful ");
you talk fast, like you're nervous. You don't sound like a native English speaker, and some people think speaking faster will make others think they have a good handle of the language. Not only does you English not sound better, but it actually makes the explanations harder to understand. Just because you say something really fast and say it several times, that doesn't make it clearer. However, you're the only one out there on youtube who's explaining CS50 in pseudo-code, so thanks a lot for that.
DISCLAIMER: The following videos are for educational purposes only. Cheating or any other activities are highly discouraged!! Using another person's code breaks the academic honesty guidelines. This solution is for those who have finished the problem sets and want to watch for educational purposes, learning experience, and exploring alternate ways to approach problem and is NOT meant for those actively doing the problem sets or to those who copy-paste the code. I have also emailed the staff in regards to academic honesty, so please be careful. Besides, if you copy you rob yourself of a valuable opportunity to learn and discover new things for yourselves. :) At any point if you are stuck please reach out to Discord or Facebook groups, there are literally 1000s of people there (no joke!!) who can help and guide you finish your solution!! Good luck!
Sure bro 👍👍👍
@@h.venkateshdeveloper6997 CAN YOU TELL ME THE NAME OF THE GRUOPS, WORKING ALONE IS NOT EASY.
@@henrycastro5723 CS50 Official Discord Group: discord.gg/cs50
Thank you so much for explaining the solutions clearly, especially in tideman. I really appreciate your method of writing on a notebook first and thoroughly explaining what's going on for each function!
No problem.
Thanks a lot! I'm glad this is the hardest exercise in CS50. I was starting to thing the difficulty would ramp up this hard every week from now on!
No problem! Good luck
So it's not gonna be hard like this in the next weeks?
finally someone explained tideman in an understandable way, thank you for giving me clarity. I have read the disclaimer, I wont copy your code, in stead I feel confident, that I can use recursion technique now.
Hi, thanks for such great explanation with textbook. Very good for understanding. Problem set 2 with Caesar wasn't hard. But problem set 3 with Tideman just broke me completely.
This was probably the best explanation video out there re. Tideman. Using a pen & paper and explaining the same thing a couple of times in a row was the key. Keep up the good word man! You will definitely see more of me.
Glad it helped Sean! Thanks for watching!
You're one of the most talented explainers of these difficult algorithms and problems I've come across on youtube. Excellent job brother. Thank you so much.
Thanks ! Means a lot. I have received some criticisms but I mostly just try.
Simply illuminating. Its 2024 now and this by far is the most indepth explanation video for the Tideman problem set I've ever came across. I finally understood the concept at the 1:00:00 mark. Thank you and subscribed!
Visualizing the algorithm has been one of the hardest parts for me, but you really helped me see what is actually happening with your video.
Thanks for the information!
Glad it helped!
Thanks you for taking some of your time to do this videos for begginers, cheers from Brasil!
I have watched over five videos explaining recursion, and you are the best and clearest programmer in delivering the concept.
Thanks for the video it was great. Honestly, I couldn't budge at all during this homework. 100% stumped. I watched that lecture twice over and I didn't see anything. I had two major problems. One I had 0 idea as to why the ranks array represented the index of the candidates in the candidates array. Then you drew the 2d preferences array and everything became way easier. My only advice to people trying to do this without resorting to a walkthrough, you have to definitely do the runoff exercise first. Jumping into Tideman without being able to visualize how the preferences array works is tough. I honestly do not think the Week 3 lecture of CS50 prepares you enough for this problem.
Np. Visualizing def helps! Glad it was useful! The walkthrough videos are also pretty visual and great but yeah I agree. Problem sets can be challenging but keep at it! :)
Perfect perfect perfect. I felt like I was keeping track of four different arrays and lists in my head. Your thought process was the best out of the eight videos i’ve seen for this problem. Thank you you’re the best!
Thanks for the great explanation! Tideman was really challenging and you make it looks much more easy!
Thank you so much! I have been trying to solve tideman, but for some reason I just can't wrap my head around it, but with your explanations, I can. So thank you for not just handing the code to me, but explaining the logic behind it, so I can write the code myself.
Glad I could help!
@Its.rikke So after one year what is your status in cs50, did you finish the course? if yes how was your experience and some advice if you like
Thanks for the breakdown, but I'm still lost on lock_pairs. Two questions:
1. I don't understand the interaction between lock_pairs and hasCycle functions. How is the IF condition below ever supposed to be true?
if (locked[i][winner])
{
found = true;
winner = i;
}
Didn't we set all the elements of the locked[ ][ ] array to 'false' in main? And to assign any of the locked[ ][ ] elements to 'true' we need to first complete hasCycle, which uses (locked[i][winner]) as one of its conditions. So how does this condition get met?
2. How can 'Alice' be stored as loser in your example at 1:40:18? Let's say we're trying to find a cycle here:
Alice -> Bob -> Charlie -> David -> Alice
Wouldn't the original winner/loser pair that's passed into hasCycle be Alice/Bob? But then we keep overwriting the winner in the nested for loop and store 'Bob' as loser. So how can we ever get back to 'Alice'?
Disclaimer: I'm just working through this as well, so take with a boulder of salt. But to address your first question, I believe that the hasCycle function must return false at least once in order for this if statement to be true. In other words, the lock_pairs function must have already locked in at least one pair in order for this to ever be true.
@@sumeursault that makes alot of sense now cause basically the logic would be that its almost impossible for there to be a cycle with just one edge locked. btw look out for the exclamation mark "!" cause it makes more sense once you take that into consideration
but since the locked array is all set to false, wouldn't be the while loop run forever?
At 1:03:30 the condition for the first loop should be i < candidate_count - 1.
I was having problems with visualizing the nuts and bolts of this particular problem(tideman) and I was stuck for a long long time building solution for a problem I had no proper understanding of. You video helped me immensely. I just looked at the notebook visualizations/ explanation and went back to the ide to implement those ideas in code without looking at your code. Hope it doesn't violate the rules of academic honesty.
Excellent Explanation. I love his details. He literally visualize every action with given examples. Love you Man!
1:28:13 Lock pairs function
It's sunday morning and I learned sooooooooo much! You're great!!! Love your style of teaching. You could join the CS50 team!
Greetings from Germany!!1
Wow, thanks for the complement! Means a lot! Guess it's time for me to pack my bags and move to Harvard! :)
Thanks for explaining , I already completed the runoff , I am here learn about only.
All the best
best explanation on Plurality and Runoff...please continue to create videos...love this channel
Glad it helped!
Hey, I think you did an awesome job explaining! Understood everything you said, and it helped clear up some misconceptions I had with the pset. Well done and thank you!
Sure no problem. Good luck Kai
1:04:24 why this ++? Where is this 1 being added? How? I can't understand it, and I an't find any video that explains this. How are we supposed to solve this if the lectures don't give us any clue about the problems?
Thank you so much for your explanation on the lock_pairs.
I use your method to trace back the winner in locked pairs.
I write the function to check the pair if it creates a cycle by calling the function itself.
Thank you so much my friend for making his video. It really has helped me understanding these problems in a clear way.
No problem! Good luck!
You can add a function per time section for tideman
.
I got stuck in the locked array part, this was a amazing solution. Thank you😊
Great video, you really have a way of simplifying complex problems. I would just add on a little tweak as to the selection sort algorithm. It would be better if the first for loop /*for (int i = 0; i < pair_count - 1; i++)*/ has a condition pair_count - 1 so that the last number does not selfswap.
Yes, good observation. You can definitely optimize wherever needed.
in 1:38:00 when back tracing reaches to bob and bob is the loser of the new pair we are finding out whether to create a cycle or not, why would we skip david -> bob pair? I know that it creates a cycle but this cycle does not affect the source of the graph which is alive. I am really confused here since CS50 accepted this algorithm.
thank you so much! You saved me from a headache:))
Sure. Np
thanks ur video made me understand nested for loops
Thanks man, you were able to explain it so I understood it. I watched each section/function and then took to pen and paper to figure it out and wrote all the code myself.
I even used different code that makes more sense to me :)
Glad it helped!
There's not candidate struct in Tideman, so candidates[i].name would be incorrect. It's just candidate[i] compared to name using strcmp.
Just so you know strength of victory is defined as the number of voters who prefer a certain candidate not the difference between the winner and loser so you don't need to find the margin of victory.
Gotcha thanks for pointing that out
@@algorithmsillustrator3313 No problem thanks for doing these! 💯
I don't think your code is totally correct, what if while looping through locked[i][winner] the are two locked pairs which are true and the first one leads to the cycle. Your code skips the first and store the winner after that, which might not necessarily lead to the cycle. For example, if we had 6 candidates {0, 1, 2, 3, 4, 5, 6} and the graph goes like
5 -> 1
3 -> 5
2 -> 5
1 -> 2
" 1 -> 2" creates a cycle but when your code is looping locked[i][winner] in has_cycle function for this, it gets to 2-> 5, makes winner = 2 which is the path that leads to the cycle, but then changes winner = 3 which doesn't lead to the cycle before checking if winner = 2 leads to a cycle. Hope i'm making sense 😅
thanks for the help visualizing the algorithm, man!
sure, np. Glad it helped Daniel.
Hi. Nice and thorough explanation of tideman.c.
I managed to get everything else right in my attempt, but didn't have any ideas on how to check the cycle. I submited tideman.c incomplete (15/18), but I did get 24/24 on runoff, so it's good :).
I have a question about the hasCycle function.
If we have 4 candidates (0, 1, 2, 3) and the following 6 locked pairs, in this order of strength of victory.
1. locked[0][1]
2. locked[0][2]
3. locked[1][2]
4. locked[2][3]
5. locked[0][3]
6. locked[3][1]
The 6th locked pair would create a cycle 1->2->3->1
My understanding is that the hasCycle function will do the following in this situation:
1. We start with winner = 3 and loser = 1
2. On the first iteration, i = 0, we find locked[i][winner] (locked[0][3])
3. The new winner is 0.
4. The iterations in the new for loop will be:
a. locked[0][0] = not found
b. locked[1][0] = not found
c. locked[2][0] = not found
d. locked[3][0] = not found
5. if (!found) then winner = -1
6. winner != loser
7. return false.
Did I get this right? If not, can you please explain the flow for this particular case and when does the function look again in the locked pairs. If it looks again, after locked[0][3], then it will find locked[2][3] that will lead to locked[1][2], that would mean that winner == loser, so hasCycle will return true.
I hope it makes sense. Sorry if it's a silly question, I started CS50 as a complete beginner, so maybe I'm missing something obvious :)
Thanks,
Yes, excellent observation. You are absolutely correct. It's actually a counterexample in my algorithm fails. The test cases aren't comprehensive enough to have a scenario like this so it succeeded in my case.
In my algorithm, I start from the most closest locked pair and trace backwards in this scenario mentioned.
1. We start with winner = 3 and loser = 1
On the first iteration, i = 0, we find locked[i][winner] (locked[0][3])
The new winner is 0.
On the third iteration, i = 2, we find locked[i][winner] (locked[2][3])
The new winner is 2.
Now inner loop ends, next iteration new winner is 2, backtrace from 2
On first iteration , 0 -> 2 yes, new winner = 0
on second iteration, 1 -> 2 yes, new winner = 1
inner loop ends,
winner == loser i.e 1 == 1, so return true saying there is a cycle.
This works, but in the example you gave just interchange 0 and 2 and see that my algorithm fails and returns false, no cycle, when there is indeed a cycle. My guess is that the test cases aren't comprehensive enough to have a scenario like this so it succeeded, but the true correct solution in this situation would be a recursive solution which exhausts all the possibilities from a given candidate.
In other words, the order in which I scan the candidates shouldn't technically matter, but in my code, I have a certain order of scanning candidates and marking as winner, which I get "lucky" in terms of finding the right answer. Good! You found a bug or a flaw in my code :)
@@algorithmsillustrator3313 I understand. Thanks for the quick response.
Great video, this helps a lot to understand
Sure np
You are correct. I was stuck in Tideman from two days.
awesome video. thanks so much!
Hi! Thank you so much for putting in so much time and effort to explain everything so thoroughly and so clearly! I just have one question, though. When you were explaining bool hasCycle at around 1:33:12, you wrote,
"while (winner != -1 ...)...
....
"if (!found) {
winner = -1"
May I ask why you use the number (-1) and what (-1) stands for?
Thank you so much!
-1 is an arbitrary value / or a flag which represents the scenario where you try to backtrace from the winner and it does not find a candidate looping back to any of the previous candidates, indicating there is no cycle. In other words, you have compared and backtraced from all the edges and you find that there isn't a candidate. But this algorithm "almost" works and is not foolproof as pointed out by @Dragos Dobre below.
16:41 I am a bit confused why the variable max is set to -1 and not to 0. Is there any specific reason? I seem to have missed it in the explanation.
No specific reason
ThankYou, you kept me going.
Great!
I am stuck on tideman for almost 2 weeks now. I keep trying to debug my code but I am still getting the wrong results. It stresses me that I haven't been able to solve it for such a long time, should I watch this video to see the explanation or keep trying? Honestly whenever I think about trying to debug it again it's turning me off completely and it gives me a prematurely brain fog if I take action. I watched Lecture 4(memory) and understood everything in it, but tideman still giving me hell. What should I do? Would such a misdeed be forgiven? Really need advice.
Update: I fixed my code completely after I came back from my first day at the gym today. Physical activity is what helped me get it done. Much clearer vision thanks to it, and also more happy. And this was day one.
Two golden steps which work extremely well when you're stuck:
1. Tackle a problem with a fresh mind (which is what you did)
2. Break down the problem into small parts and tackle each one, one at a time. In this case, try to tackle each function separately by writing down and thinking about what it should do.
Yes I know. keep at it and inspiration will strike you
hello, what does the ++ here mean, I know it's incrementing, but why is it there? Thanks
Thank you for such a detailed walkthrough. I am new to CS 50. Your video helps me understand the computer logic so much clearer. Though I am still struggling on the Lock_Pair part. If there are two or more branches in the locked pairs, does hasCycle still cover the condition?
For example, if my current locked pairs are as follows:
Charlie -> David and Alice -> Bob -> David; and the new pair is David -> Alice;
when traceback, will I fall into the Charlie -> David branch, then the hasCycle will return false, though there is a loop in the other branch.
Could you help me clarify this scenario? Really appreciated.
Hey sorry, it has been a while back since I made these videos. Please post in discord group for help.
Great video!! Could you please explain the reason behind incrementing preferences array in record_preferences funtion at line 150 ? I unaware why this is required. Thanks in advance!!
They're building a table of voters preference of candidates vs all other candidates. The ++ acts as a tally for each candidate that a voter prefers over another. So if we have Alice, Bob and Charlie and they prefer Bob, Charlie, Alice, this is stored in ranks array as 1,2,0. So we want to tally once for bob over charlie, once for bob over alice, and once for charlie over alice. That is represented by preferences[1][2]++, preferences[1][0]++ and preferences[2][0]++. Once that gets recorded by the record_preference function, the ranks array is reset and takes the preferences from the next voter.
i understand why in cycles like Bob -> Alice -> Charlie ->Bob are found with this function.
but in case we have something like. 1. Bob -> Alice -> Charlie ->Bob and also 2. Peter -> Susan-> Charlie -> Bob. Why could it not be the case that, the function returns no cycle because if the function goes down the second path and (charlie,susan,peter) it then returns no cycle although there is one?! I would really appreciate your answer.
Man it was tough to visualize but this video helped me understand the question in a much clearer way. I do have prior programming experience, however with the lack of more advanced ds, it does become really difficult. Now I appreciate OOPs!
Great video mate, really helped visualise the problem
I couldn't solve add_pairs() function although my code is the same with your code.
1)what is the difference between (candidates_count) and (candidate.count);
and
2) when im seeing some answers like your answer i found that there somethings that they didnot tell us about it like
break ;
and
3) sometimes i cant make the logic by myself
im studing programing by myself im 16 years
i dont know what i should do
when i studing programing
if you can tell what is the best way to study it
and achieve all the information
>>>>>>>>>>>>>>>>>>>>>>>>>i hope you will answer me !
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>thanks !!
1. Candidate dot count, is a syntax used when you are accessing a field inside a struct. In this case, count represents a field defined in struct candidate.
2. Break is just a keyword to tell to the program, just exit early in the program, no need to loop further.
3. Best way to study is to visualize and solve it by hand, then find out what actions your brain took to get to the answer, then make the computer do exactly that, step by step.
@@algorithmsillustrator3313 thanks alot , but
what if i cant answer some of the psets and i returned and repeat the lesson again and i really understand it really
but when i try to answer one of the sets i stuck on it for about 3 days and cant answer it im really triyng to learn programing
i dont know what should i do but im tring
and thanks again .
:)
I mean i cant make the logic of the program
and im not stupied i have a good brain .
all my family are doctors
so i dont know what to do
??????????????????????????????????????????????????????
@@TheElJoyHunter its all about hard work and consistency.
Thanks for the subtle explanation! Helped a lot!
I am confused about preferences array increment, Will it increment the values inside the array or what? and if it is increment preferences as a whole then how it is helping the vote count to the respective candidate? sorry if this is a silly question, I tried to find the answer, but I felt none have traced the program like you do on paper which is very easy and simple to grasp.
help voting the count for each individual
What's the full code for the insertion sort algorithm? A bit of it is cut off in the video. Thanks in advance!
Pause at 1:28:11
@@algorithmsillustrator3313 check50" reported an error with "sort_pairs", the rest were all green!
Here is the code for the sort_pairs function(insertion sort)
pair temp;
for (int i = 1, j; i < pair_count; i++)
{
temp = pairs[i];
j = i - 1;
for (; j >= 0 && (preferences[pairs[j].winner][pairs[j].loser] - preferences[pairs[j].loser][pairs[j].winner]) < (preferences[temp.winner][temp.loser] - preferences[temp.loser][temp.winner]); j++)
{
pairs[j + 1] = pairs[j];
}
pairs[j + 1] = temp;
}
return;
Please let me know where I have made a mistake.
Edit: I have made the correction. Thanks for the video
Great!! Good luck!
i'm not sure i understand why we use "break" in 31:00
Can someone explain it further?
You found the candidate/ person, no need to loop through the rest. That;s why you break
bro please explain me one thing you used the global variables and use them across different function but how that variable keep on updating its value from one function to another , because when i was doing this i had to use the static function for allowing variable to update its value
I just followed guidelines from the assignment regarding global and local variables.
It was a great video but i want to ask that in Tideman while doing vote function why do we need found_function.After finding the name in candidates string by strcmp can't we just make "ranks[rank] = i" in that 'if function' and then return true.
Hi Aman, are you talking about updating ranks array as soon as it is found and returning true immediately after that? Yes that will also work. It's personal choice. You can write it however you want. :) I looked for a not or false condition and updated accordingly but you could update as soon as you find true for strcmp.
@@algorithmsillustrator3313 thank you so much it helps a lot.
Hi thanks for your video, i stuck in sort for days, your video did a great help! however, i'm still lost on the final part of the function, what does it mean?
pair temp = pairs[max index]
pair[max index] = pairs [i]
pairs[i] = temp
could you explain them one by one please?
{
int min;
for (int i = 0; i < pair_count; i++)
{
for (int j = i + 1; j < pair_count; j++)
{
if (preferences[pairs[i].winner][pairs[i].loser] < preferences[pairs[j].winner][pairs[j]loser])
{
min = pairs[i];
pairs[i] = pairs[j];
pairs[j] = min;
}
}
}
I have a question regarding lock_pairs in tideman. what if in pair[0] we have a->b; pair[1]: c->d and pair[2]: d->b. According to your algorithm there could be a cycle cuz the loser in pair[2] which is b was visited in pair[0], this actually is not a cycle. Your algo is assuming that there are links throughout all pairs which might not be true.
No not exactly, here's what will happen for that scenario,
has_cycle(a, b) -> returns false , no cycle, so far graph looks like this: a->b
has_cycle(c, d) -> returns false, no cycle, so far graph looks like this: a-> b, c -> d
then we come to has_cycle(d, b):
in this case, store loser = b, and backtrack from winner which in this case is d,
who locks onto d?
does 'a' lock onto d-> no
does 'b' lock onto d -> no
does 'c' look onto d -> yes, mark 'c' as new winner and backtrack from c,
who locks onto c?
does 'a' lock onto c-> no
does 'b' lock onto c -> no
does 'c' lock onto c -> no
does 'd' lock onto c -> no
since, no one locks onto 'c' , mark winner as -1, exit out of loop and return false meaning there is no cycle created if you insert this edge, hence there is no cycle.
@@algorithmsillustrator3313 thanks for your explanation, now I understand.
Hello, first of all thank you so much for your help. I really needed. I was doing the first part of runoff and my compiler said preferences[vote][candidate] = found is past the end of the array :( any idea why?
Apologies for the delayed response but I believe it could be because you’re running past the bounds of the array .can you re-check the bounds. If you’re still stuck I recommend asking help on discord
Why can the vote function change the values of "ranks" in main when the function is returning a bool?
because it's deisgned to be mutable as per the programming assignment requirements i htink. I think i just followed the guideleines of the programming assignment.
I tried sorting using merge sort and straight up hit a road block. Have you tried sorting the arrays using merge sort?
No I tried to write simple code without recursion.
thank you!!
Thank you!! this really helped me understand how it works!
this video was very helpful. could you please help me with tabulate function, still confused with it. didn't get how it is working. thanks :-)
Please first check out the walkthrough and Brian's explanation of tabulate function. Then, the only thing you need to figure out are the inputs and outputs and the algorithm. Once you realize the 2d array manipulation and how to put preferences / votes for individuals, that's the essence of tabulate function.
@@algorithmsillustrator3313 Thanks. this was very helpful. One more thing. You initialized the min_votes variable to crazy high value. what if we initialize it to 101, as we have defined the voters to max 100. how it can exceed 100?
@@MKSundaram Oh good observation. Yes you're right, you can probbaly come up with a reasonable upper bound given the problem's constraints. Nice!
Thank you so much!!!
No problem. Glad it helped.
I spent the past 4 hours trying to figure out recordpreferences for tideman with multiple layers of nested for-loops and finally had to come here and see that it's supposed to be done in 3 lines..... What am I doing so wrong?????
haha... same actually. on the bright side we learnt something new :)
I think there is a little mistake in the code for cycle check in tideman. You wrote:
if (locked[i][winner])
{
found = true;
winner = i;
}
But shouldnt there be the i counter reseted to zero if found is true? Like this:
if (locked[i][winner])
{
found = true;
winner = i;
i = 0;
}
If we do that, I think the loop will go on forever potentially since when we find the winner we set i = 0 and the loop condition i < candidate_count will always be true
This is awesome. Thanks so much for your effort in explaining the tideman algorithm in particular. I have a question which is probably a bit silly but it refers to locked pairs
In the hasCycle function you use the following
if (locked[i][winner])
{
found = true;
winner = i;
}
I was wondering what what the 'if statement' was checking for in the locked array? Or if it's not checking anything what function does it perform?
Thanks again
Sorry for the late reply. The if checks whether another candidate is locked on to a particular candidate. This piece of information can be found from the locked 2d matrix
Thanks
with the function hasCycle i don't know how i can understand the coding. it's so trickiest i don't know where from david or locked[i] (: (:
For runoff:
The is_tie section wasn't working for me. That area is overly complicated. Here's what I did for the is_tie section:
bool is_tie(int min)
{
// Determine if tie
for (int i = 0; i < candidate_count; i++)
{
if (!candidates[i].eliminated)
if (candidates[i].votes != min)
return false;
}
return true;
}
Thanks for sharing Marc!
I ended up receiving the answer from chatgpt, as I didn't want to research anything and I was already confused by the explanation... if I had found your channel in time, I would have done it without researching... :( .
(Now I'm going to read and understand what he told me, even if it's cheating, I'm going to research and clear all my doubts and also understand the logic of his video, especially the lock_pairs part, where I was confused and couldn't...) I didn't want to get the answer... sorry.
Would you please give me all the Python Code so i can train with it? Thanks
Sorry I try to avoid posting the code to avoid plagiarism
lol i like the way you talk hahah
Lol that's a weird thing to say, but okay I'll accept it as a compliment! :)
Can you show me the long form of
pairs[pair_count++] = p;
pairs[pair_count] = p;
pair_count++;
@@algorithmsillustrator3313 thanks 😊
Are you Indian?
//I know, it's none of my business, but I kind of felt like you are an Indian and my curiosity has forced me to ask this question😅
printf('Your videos are really very helpful
");
would your view change if I said i am not an indian?
Light bulb!
he/she/they would be the winner ;)
It's [tidiman], not [taidman]
are u indian?
try adding a timestamp where you actualyy start coding
For what? What does the timestamp serve?
you talk fast, like you're nervous. You don't sound like a native English speaker, and some people think speaking faster will make others think they have a good handle of the language. Not only does you English not sound better, but it actually makes the explanations harder to understand. Just because you say something really fast and say it several times, that doesn't make it clearer. However, you're the only one out there on youtube who's explaining CS50 in pseudo-code, so thanks a lot for that.
Well, we all are work in progress aren’t we? :)
Agreed. Try to slow down and not just repeat yourself a bunch of times.
I just can`t follow your explanation, it`s all over the place. Sorry mate.
Its ok. No worries. Thanks for watching nevertheless!