+ 3

# Hi , everyone there is a thing that I do not understand .

in pseudocode of algorithm of phone book problem from CS50 course the pseudocode is: 1-pick up phone book 2-open to the middle of phone book 3-look at page 4-If person is on page 5- call person 6-else if person is earlier in book 7- Open to middle of left half of book 8 Go back to line 3 9 Else if person is later in book 10 Open to middle of right half of book 11 Go back to line 3 12 Else 13 Quit Now for instance if the person is earlier in the book that means I tear the problem in half now if the person is in later of that left half of the phone book the programme will stop because I did not give it instructions what he will do in that case

19th May 2022, 3:57 PM
Yusof Hani
21 Réponses
+ 3
Yusof the algorithm is guaranteed to find the entry if it exists and prove that it doesn't exist otherwise. If it is properly applied there can never be a situation where there are not enough instructions.
19th May 2022, 5:07 PM
Simon Sauter
+ 2
Denise Roßberg Yeah, I agree with Simon Sauter . Binary Search is a way to do so. And again, this is a beginner course. As someone who has taken it, I can assure you that you're going to advanced too try to get him to understand recursion. You don't want to give a saw to someone who doesn't even know how to hold a knife. /genuine
19th May 2022, 5:16 PM
Justice
+ 2
Yusof Try watching this short (make sure you're watching all shorts for the weeks BTW) You don't have to know this yet but it may help is a more practical example with actual coding https://youtu.be/T98PIp4omUA
19th May 2022, 5:20 PM
Justice
+ 2
Denise Roßberg Yes, the name of the course is called "Introduction to Computer Science". He's just starting. I do recommend the course for even experienced programmers, but because of the specific question, I know that he's beginner.
19th May 2022, 5:22 PM
Justice
+ 2
Yusof Let's keep to your example: Peter, phone book has 1000 pages 2 open the middle -> page 500 3 look at page 500 (we assume section m) 4 peter is not on the page 6 peter is not earlier 9 peter is later (p > m) 10 open the middle of right half (the book has now 500 pages, so we open page 250 of this side (should be page 750) 11 goto 3 3 we look at page 750 and so on You can't get stuck, because of the if else constructions which tells you where to jump or when to quit.
19th May 2022, 5:29 PM
Denise Roßberg
+ 2
Denise Roßberg gave a great example but I also recommend that Yusof join the direct discord for CS50. The Harvard staff are on there and there a lot of other great classmates who have taken the course that can help you along. I wouldn't have made it through without them, so it's really beneficial, especially since we're all learning the same things and facing the same problems and projects.
19th May 2022, 5:35 PM
Justice
+ 1
Hello Yusof Hani Sounds like you need to learn recursion and divide and conquer algorithm: https://en.m.wikipedia.org/wiki/Divide-and-conquer_algorithm Imagine the phone book as a list. [.........] Now you divide this list into two halfes: [...] [...] You can continue this until you find the person. [.....] / \ [...] [...] / \ /\ The trick is to threat each list part as a new phone book. As Justice mentioned the phone book is alphabetically sorted. Lets say we split the book into theese two halfes: [A-Z] [A-N] [O-Z] You are searching Peter. Peter -> P > O -> search on the right side [O-Z] / \ [O-T] [U-Z] P < U -> search on the left side [O-T] / \ [...] [...] ... and so on In the end you will get a list [P] where you find Peter.
19th May 2022, 4:59 PM
Denise Roßberg
+ 1
Denise Roßberg The week he is on in that course is the 1st or second week. Those weeks are really only for learning the very basic of compsci such as what variables, functions and data types are. Recursion is too advanced for his current level.
19th May 2022, 5:08 PM
Justice
+ 1
Simon Sauter Yes, your right. Every recursion can be solved with loops.
19th May 2022, 5:16 PM
Denise Roßberg
+ 1
Thanks again Denise Roßberg and sorry if annoyed you
19th May 2022, 8:22 PM
Yusof
0
I'm not really understanding what you mean. It sounds like the person has jumped to another page which isn't possible. Phonebooks are in alphabetical order. So a person who's name start with B can't be suddenly moved to section Z, hence why it was okay to rip the book in half, because you have no use for M-Z.
19th May 2022, 4:00 PM
Justice
0
Lines 8 and 11 make sure that you keep narrowing it down until you either find the person or show that the person is not in the book.
19th May 2022, 4:40 PM
Simon Sauter
0
Hi Justice to understand what I mean let's explain to you what exact the pseudocode is. In fact this is a solution for a problem of phone book the problem is I want to find someone's name to call him and I have a phone book alphabetically arranged and its pages 1000 pages let's say the first litter of his name is w and to slove this problem quickly with correct solution . We need to open the middle of book and for instance I found myself at m section that means I don't need the left half of the phone book now and now I have 500 pages I will repeat that over and over until I get the name that I want.and now my question is if we open the middle of the phone book and found ourselves in d section for instance that means we don't need the left half now if I repeat that again and found ourselves in x section the programme will stop because we didn't give it enough instructions what should he does in this case
19th May 2022, 5:02 PM
Yusof
0
Yusof If the person comes later in the book -> open to middle of right half line 10-> line 11-> line 3 You only quit when you found the person or you don't find the person (person is not in the book).
19th May 2022, 5:08 PM
Denise Roßberg
0
Justice Maybe, but otherwise you will not understand this problem. If you understand the divide and conquer algorithm then this pseudo code makes many sense. ;)
19th May 2022, 5:10 PM
Denise Roßberg
0
Denise Roßberg recursion is one way to implement this. But it can be done without recursion using loops.
19th May 2022, 5:12 PM
Simon Sauter
0
HiSimon Sauter I understand that but i still don't understand this pseudocode let's say the phone book has 1000 pages and as you said we are looking for peter if opened the middle of the phone book and I found myself at m section that means we do not the left half of the phone book and now we have 500pages if I repeat that again and this time I found myself x section that means we don't need the right half this time. The programme now may stop because I didn't give it enough instructions to tell him what he should in that I only told if the person in left half go back to line3 and it didn't read what it should do because it read step by step
19th May 2022, 5:17 PM
Yusof
0
Justice CS50 is for beginner? Okay. So this task is more an introduction into algorithmic thinking?
19th May 2022, 5:20 PM
Denise Roßberg
0
Yusof again it is impossible to get stuck. For every possible situation there is an instruction.
19th May 2022, 5:21 PM
Simon Sauter
0
Thanks Justice Denise Roßberg Simon Sauter now I understand what this pseudocode is . But sorry if annoyed you I only want to make sure of my understanding let me tell you what I understand knowing that we are looking for someone's name which starts with q for instance At first step we open the middle of the phone book and consider we found ourselves in d section that means we do not need the left half of the phone book and we treat with the new half of the phone book (right half)as a new phone book we opened the middle of the new phone book (right half )and go back again to line 3 we looked at the page and we didn't find the name that we are looking for we found ourselves in x section that means the name that we are looking for in the left half of the phone book that leads to we will be back again to line 3 and treat with the new half of the phone book and follow the instructions step by step again until I fiund the name that I am looking for or I realize that the is not exist originally
19th May 2022, 6:43 PM
Yusof
Aujourd'hui en vedette