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

Question

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

Answer 1

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.

Answer 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

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

Simon Sauter Yes, your right. Every recursion can be solved with loops.

Answer 10

Thanks again Denise Roßberg and sorry if annoyed you

Answer 11

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.

Answer 12

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.

Answer 13

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

Answer 14

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).

Answer 15

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. ;)

Answer 16

Denise Roßberg recursion is one way to implement this. But it can be done without recursion using loops.

Answer 17

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

Answer 18

Justice CS50 is for beginner? Okay. So this task is more an introduction into algorithmic thinking?

Answer 19

Yusof again it is impossible to get stuck. For every possible situation there is an instruction.

Answer 20

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