CS50 PSET5 Speller Solution

Поделиться
HTML-код
  • Опубликовано: 12 янв 2025

Комментарии • 121

  • @algorithmsillustrator3313
    @algorithmsillustrator3313  4 года назад +6

    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!

    • @rishikesshbalaji3765
      @rishikesshbalaji3765 4 года назад

      Hey just a small question
      at 4:17 why did u put "r' " and how did it work

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      @@rishikesshbalaji3765 It stands for read mode. The apostrophe is a typo

  • @rperry931
    @rperry931 4 года назад +4

    This helped me fix all the problems I was having. Thank You so much please continue to make more like these!!!

  • @sudarshansingh5806
    @sudarshansingh5806 4 года назад +3

    Extremely well put out and very well explained! Thank you so much! This really helped me out a lot. The way you explain concepts and their implementation is the best I've ever seen. Can't thank you enough. Keep up the good work and good luck for whatever it is you pursue! Cheers!

  • @enigmaticminx
    @enigmaticminx 4 года назад +1

    Thank you so much for this. My code was nearly identical to yours aside from the hash function, but I kept getting a leak error from not closes the file. So simple! I was also having an issue with my hash function, and I had a feeling it had to do with the string case because of the output I was getting. I didn't even consider something as simple as using tolower(). But you're right, they gave away so much on this problem set, but a part of me is glad they did. It took me a bit to start this problem set because I was intimidated by it, but with the walkthrough and the shorts (and your video), I feel like I have a pretty good grasp of this stuff now. Thanks again!

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Glad it helped! Good luck!!

    • @adelshousha5437
      @adelshousha5437 2 года назад

      I just want to say that I'm here a year later having the same leak from not closing the file and I just saw this comment and I just can't express how thankful I'm right now.
      thank you so much I hope you have a wonderful lifetime .

  • @ashleywong7842
    @ashleywong7842 4 года назад +1

    Your tutorial is very helpful! I like the way you teach.
    It is very clear and smooth. It is greatly appreciated.

  • @rossanobr
    @rossanobr 4 года назад +3

    very nice.
    It was very challenge for me to doing this pset.
    your video helped me a lot
    trying to learn how to code it not easy task, but you did a nice job teaching it
    thanks

  • @inthecure
    @inthecure 2 года назад +1

    Do we need the if part of the if/else statement for the code at 12:25?
    Can't we just replace this code:
    if (table[index] == NULL)
    {
    table[index] = new_node;
    }
    else
    {
    new_node->next = table[index];
    table[index] = new_node;
    }
    With the code below and achieve the same result?
    new_node->next = table[index];
    table[index] = new_node;

    • @ozzyosbourne3678
      @ozzyosbourne3678 2 года назад

      We need to check if table[index] has an existing node or not. The latter part basically takes care of an occupied slot.

  • @dhashennaidu6116
    @dhashennaidu6116 4 года назад +1

    Really great step by step run through of the problem.

  • @marchmellow2728
    @marchmellow2728 3 года назад

    12:27 It's not clear to me why we go
    n->next = table[index];
    table[index]-= n;
    instead of
    n->next = table[index+1];
    table[index]->next = n;
    or even just
    n->next = table[index+1];
    table[index]= n;
    It would seem to me that we want our new node to point to the next index, not the current one.
    So if the hash gives me value 1, I want the NEXT value in the chain to be 2.
    So first I connect my new_node to the next link in the chain, then I connect the previous link t new_node, at the correct index.
    Maybe I'm missing something thanks for any help!

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  3 года назад

      Hey sorry, I don't remember since I made these videos a while back, please post in discord for help. If I were to remmeber, I would say index is always 0 indexed , so you would place it there and then incremenet / decrement it. index + 1 would offset it by 1 and there could be some potential "holes" or gaps in the data structure. So you fill the current spot and move on.

  • @gabrielcandidopereiramarin8284
    @gabrielcandidopereiramarin8284 2 года назад

    Thank you so much for this video, you really helped me a lot

  • @BruceNJeffAreMyFlies
    @BruceNJeffAreMyFlies 2 года назад

    How do you fit more than two elements into a bucket, with those lines?
    else{
    new_node -> next = table[index]
    }
    implies that if the location is full, then it point to that location. Does that not mean that the second location will be replaced, if the second location is already full? I feel like the check needs to iterate over until it finds a null, rather than simply assuming the next location is already free?

  • @nonamedlish
    @nonamedlish 4 года назад

    thanks for helping us to gain a deeper understanding

  • @TheElJoyHunter
    @TheElJoyHunter 4 года назад +2

    i know that if we said int something so it should be like that
    >>>>>>int x = 5;
    so why we said
    >>>>> int index = hach(word);
    and when should i use these way

  • @zavekhan9031
    @zavekhan9031 4 года назад +1

    when i run this in terminal
    ./speller texts/lalaland.txt
    in the end terminal says:
    Could not unload dictionaries/large.
    please help

  • @NgocNguyen-zl5oj
    @NgocNguyen-zl5oj 4 года назад +1

    At the row 76 of the load function, why is it that "new_node -> next = table[index]", but not "new_node = table[index]"?

    • @rishideychowdhury5856
      @rishideychowdhury5856 4 года назад

      Cause the new_node's next field points to the next node of the linked list.
      If you do new_node = table[index], you are basically making new_node's word field and next field = NULL or something else whichever might be present there..Hence, by doing that we are losing the new_word's next and word field.

  • @saadkhattak7258
    @saadkhattak7258 3 года назад +1

    I am getting the error in check function --->"error: use of undeclared identifier 'cursor'" ..what to do ??

    • @legendarylightning676
      @legendarylightning676 3 года назад +1

      check that you defined cursor (i guess watch it again)
      also I'm twelve what am I doing here

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  3 года назад

      Thank you Legendary Lightning for helping out. Also are you a cousin of Flash because you possess Legendary Lightning :)

  • @hamdyramzy4350
    @hamdyramzy4350 4 года назад

    8:24 how can you " hash(word) " before declare the hash function ?

  • @Sensei-cm8fx
    @Sensei-cm8fx 2 года назад

    hey man, I need help :/
    I'm stuck at this exercise.. I've done this exercise by myself, without browsing for videos.. and it worked very well, all my results were the same of the staff. even valgrind didnt return any leak of memory to me. but when I use check50, I just can't pass on the last check.. it says that my code isnt free of memory errors, and the output is the next one:
    :( program is free of memory errors
    expected "MISSPELLED WOR...", not "### unhandled ..."
    I did and remade my code, over and over again, I saw lot of videos to try to find out what was my mistake.. and after seeing your video I thought my problem would be done, I did exactly what you did, and the error persists.. what do I do?... please, I don't like to see errors in my code :b
    obs: my code is almost the same of yours but the hash function, i used a simples one that calculates the index of the letter in the alphabet..

    • @Sensei-cm8fx
      @Sensei-cm8fx 2 года назад

      edit: I've copied your code word after word, and the error persists.. so.. I guess the problem isn't in my code, but in the check50's compiler.
      one observation, I've done a change on N. N as const unsigned int was not even compiling in check50, so I browsed a solution and I used #define N (value), and it compiles in check50.
      I dont know if there are new features or changes since the course content has been made, so here I am reporting this.

  • @sayori3939
    @sayori3939 2 года назад

    i don`t know what the actual hell is going on with my code but my hastable magically becomes NULL inside the check function, if i print its contents right before the return in load function it`s all in there but then if i print it in the 1st line of the check function it`s null!!!
    OBS: only when using the small dictionary

    • @sayori3939
      @sayori3939 2 года назад

      so apparently that had nothing to do with the problem, and the problem was at my unload function, and for god knows reason it wouldn`t print anything on the 1st so because of that i thought the problem was at the check function, i hate C

  • @organizedchaos4559
    @organizedchaos4559 4 года назад

    Your videos are great, you explain it really well and I think it a great resource to check my work. Just asking will you be making videos for the new content on the cs50 course like the new content for week 8, 9 and 10?

  • @winnieip9851
    @winnieip9851 4 года назад

    Thanks for the clear explanations. Just would like to know in the bool check(const char *word), where are the codes that check apostrophes & sub-strings ?

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад +1

      I don't think we need to worry about that or atleast if we need to do is taken care by the files provided by the staff

    • @codedprofessor
      @codedprofessor 4 года назад +1

      I think a word with apostrophe would give a different hash function than that same word without. Hence, you won't find that word in the table where it's meant to be.

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      @@codedprofessor Yup that's correct

  • @doloreschu7077
    @doloreschu7077 3 года назад

    For the has function- I don't understand how we could have ended up with a sum greater than N? How is that possible if we had already defined N as big as the word's ASCII value can get?

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  3 года назад

      if you have a really long word, the sum of the ascii values will of couse be greater than the amount of buckets. For instance, if you only had 3 buckets, and your word was "cat", you would have already exceeded N which is 3.

  • @haxlwaxl997
    @haxlwaxl997 4 года назад

    I know inefficient. But could sb. tell me why my code is not working. ```
    bool check(const char *word)
    {
    int hashvalue = hash(word);
    node *cursor = table[hashvalue];
    if(strcasecmp(cursor->word, word) == 0)
    {
    return true;
    }
    while(strcasecmp(cursor->word, word) != 0)
    {
    cursor = cursor->next;
    if (strcasecmp(cursor->word, word) == 0)
    {
    return true;
    }
    else if(cursor->next == NULL)
    {
    break;
    }
    }
    return false;
    }

  • @HamiltonGJr
    @HamiltonGJr 4 года назад

    Really good. But check50/valgrind found an error not pointed for It in your video: we do not close file at end of load(). The file is closed when some is wrong, but not in a successfull loading.

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад +1

      As a rule of thumb, you have to close the file whenever you open it. I included that part later in the video, since valgrind reported some memory errors.

  • @antotot04
    @antotot04 Год назад

    I don't know what to do!
    I've finished this pset on my own two days ago, i'm sure 110% that my code is working (i've compared it in all the possible ways with the solutions of the staff) but as soon as i run the CS50 check in the terminal all allerts are red!
    I'm sure my code is fine. What can i do? at this point how can i contact cs50 in order to solve this technical problem? i don't want to submit it becuase, with this technical error (which is not mine) I could compromise my total score in the course so far.

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  Год назад

      please get help in the cs50 discord channel (link in descirption). there you can find some helpful hints.

  • @zxcfresh2200
    @zxcfresh2200 4 года назад

    it give's me this error (linker command failed with exit code 1 (use -v to see invocation)). pls help

  • @andrewliao1140
    @andrewliao1140 4 года назад

    Question about the hash function: If you have two words that contain the same letters but in different orders won't it be a problem? e.g. bat and tab

    • @rishideychowdhury5856
      @rishideychowdhury5856 4 года назад

      No.. Since we are hashing it the way we like.. We are not hashing our table in the alphabetical order.
      Think of it like this that...
      The HASH TABLE's buckets are numbered as 0,1,2,3,4,.......,3299, ....., N
      And now the words are hashed in a particular array position based on the hashing index obtained.
      So, anybody coming to search for the word will hash it and go to that position may it be be bat, tab, abt

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      To add to what Rishi has mentioned above. If two words hash into the same location, that's actually not a problem, since we resolve it by chaining. In fact, assume that we just had one bucket and all words hashed into that location, there is technically nothing wrong with it, it's just that it won't be very efficient, it will just be one long linked list, but it will still work because we know how and where to find the word :)

  • @melancolique9835
    @melancolique9835 4 года назад +2

    for (int i = 0; i < N; i++)
    {
    while (table[i] != NULL)
    {
    node *tmp = table[i]->next; //from lecture
    free(table[i]);
    table[i] = tmp;
    }
    }
    you can use this to unload memory too, it was given in the lecture

  • @green-coder
    @green-coder 4 года назад

    you are awesome now i understood what should i do thanks 🙏

  • @alexanderaguila6657
    @alexanderaguila6657 4 года назад

    thank you for the video it was a tremendous help. i found that everything i was doing was ten extra steps. And i tried to malloc more than i should have in an attempt to understand it. my question is this.
    In line 72 you malloc'd new_node, but i dont see a point where you free() it. as the checker said you didnt leak memory, is it then not the case that you have to free() everything you malloc?

    • @alexanderaguila6657
      @alexanderaguila6657 4 года назад

      wait. let me know if im wrong.
      you do free the new_node, but as you iterate through the dictionary, new_node is setting aside different addresses of space for the incoming words and then passing them to table[index]. so when you free the hash table you also free any memory new_node malloc'd.

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      I free all the nodes in unload function. You do this by iterating through all buckets, all nodes and free each one of then.

  • @sodajoyjoyjoy
    @sodajoyjoyjoy 4 года назад +1

    thank you so much for this video! And a few questions here: Is it essential to set new_node->next to NULL?And why don't we need to free the node pointers(as it also uses malloc function)? Thanks again!

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад +2

      1. No, I believe the new_node->next = NULL is not really needed since it's defaulted to NULL. Just copied from walkthrough which is why it looks like the way it is.
      2. We indeed do free the node pointers in the unload function. Basically, pointers are memory addresses, and you allocate certain objects or data in the memory using malloc. Malloc gives you that memory address of where the objects are located. To free the objects, you would need to call free(pointer), where you need to pass in the pointer or the memory address to be freed. In this case, we already know where exactly our memory addresses are since we store them in our table array data structure. So we loop over them and free each of the objects in memory in the unload function. Hopefully that makes sense.

    • @mikemaer
      @mikemaer 4 года назад +1

      @@algorithmsillustrator3313 I wasn't putting newnode->next = NULL and was getting an error in Valgrind but in the unload function...saying that my cursor variable was uninitialized. After some troubleshooting I realized that I hadn't set newnode->next to anything and voila it removed the issue.

  • @marwahmaher8574
    @marwahmaher8574 4 года назад

    2:50 what does this command mean (ls -l)

    • @forest3064
      @forest3064 4 года назад

      when unsure, look at the man page man7.org/linux/man-pages/man1/ls.1.html you can see the '-l' means list the author and other information

  • @ghammemyoussef3270
    @ghammemyoussef3270 4 года назад

    how can we put a string in a char array? i didn't understand it in load function we put a string in a char array (word[]) . can u explain it please

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      The string is a char array by definition. Whenever we are reading words, we have to store it somewhere so we store it in a buffer or a temporary array.

  • @ChlorineSpot
    @ChlorineSpot 4 года назад

    why we created buffer? what is the use of it?

  • @yt-1161
    @yt-1161 3 года назад

    @25:46 no need to tell the filename ? just make is enough since it's the only c file ?

  • @amnaalhassan8081
    @amnaalhassan8081 4 года назад

    Thank you sooo much you really help me

  • @premanshpareek2905
    @premanshpareek2905 4 года назад

    i tried to follow you but when i execute the program it only displays "misspelled words" and nothing else until i terminate it.

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Maybe your hashing algorithm or some part of your code doesn't work hard to say. Can you try asking in cs50 discord for help? Soemone might have faced similar issues.

    • @premanshpareek2905
      @premanshpareek2905 4 года назад

      @@algorithmsillustrator3313 why does the code not work when you declare the new_node outside the fscanf while loop but it works when you declare it inside the loop?

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Because the inner loop is where all the words are constructed and the words from the file is read only inside the loop

  • @SakanaKuKuRu
    @SakanaKuKuRu 3 года назад

    is it normal for valgrind to show that I have 160 000 + bytes still reachable?

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  3 года назад

      not sure but probabbly not I guess. Sorry, please reach out to discord group for help

  • @dixonnn404
    @dixonnn404 4 года назад

    what is int index = hash(word) on line 62?

    • @dixonnn404
      @dixonnn404 4 года назад

      and also return (sum % n)

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      1. Gets integer value returned from hashing function
      2. To make sure you hash into a valid bucket i use modulus operator

  • @TheElJoyHunter
    @TheElJoyHunter 4 года назад

    hi i cant understand
    something like
    node *new_node = .............
    how did we define it
    i mean when we says
    a name
    we says string name = ............
    but here you said FILE * file = ............
    and after that you said node * new_node =..............
    i think you understand what i'm saying
    can you explain that to me
    and thanks !

    • @hasanaslan2688
      @hasanaslan2688 4 года назад

      If I got you right, you should look for structs in C. It will help you to understand.

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Please watch the lecture. Mr.Malan has done an excellent job covering it

  • @santiagojosehoyossanabria62
    @santiagojosehoyossanabria62 4 года назад

    Is that all the hash function needs?

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      You can have any hash function you want. You can make it as simple or complex as you want. I have a simple but inefficient hashing algorithm in this case.

  • @abdulelrahmana.bahget1441
    @abdulelrahmana.bahget1441 3 года назад

    Thanks man❤❤

  • @nicolasgrisalesceballos3535
    @nicolasgrisalesceballos3535 4 года назад

    Why do you set that "N" value?As I understood the problem it is only necessary to set that value at 26, the number of letters of the alphabet, and still works but it takes longer to execute. Why is this happening?
    PD: Thanks for the video, it helps me understand a lot.

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад +5

      N is basically the number of buckets you want to allocate. It depends on your hash function. If you set your buckets to 26 for instnace, then you are going to have a lot of collisions since there is only 26 buckets, and will have to chain everything to together in case of collisions, which results in longer execution time. Say your hash function was taking first lowercase letter, in that case, if I gave you all words starting with the letter 'a', then it would chain eveyrthing together and it would be one lengthly linked list, which would lead to bad performance. However, if you allocate more buckets and your hash function distributes words evenly, then you have fewer collisions, and you don't have to spend a lot of time searching for the word in the bucket (since there are very few collisions).
      Regarding your first question, it was a rough upperbound, my hash function was summing ascii values. So the max value this can take on is the maximum size of a word (45 letters * highest ascii value which is lowercase z in this case). those will be my total number of buckets I allocate. I could have probably reduced my buckets but it was a rough estimate. The key is to also not make too many buckets like 100,000 because then you run out of memory and your data is really sparse , so lots of memory is wasted. Hopefully that makes sense!

  • @edwinma6236
    @edwinma6236 4 года назад

    Couldn't find any cs50 discords:(

  • @meetpurandare1163
    @meetpurandare1163 4 года назад

    I am getting could not load dictionary/large error

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Check the boolean values / return types of the functions and make sure you load returns true upon successful load.

    • @meetpurandare1163
      @meetpurandare1163 4 года назад

      Thanks sir it worked

  • @melancolique9835
    @melancolique9835 4 года назад

    i dont understand whats "r'" in fopen?

  • @TheElJoyHunter
    @TheElJoyHunter 4 года назад +1

    when does we use this method something[something]
    like
    >>> table[index]

    • @damarcusl02
      @damarcusl02 4 года назад

      it's basically just creating an array variable. "table" is the variable name and "[index]" is the size of the array.

  • @JanFieber
    @JanFieber 4 года назад

    It says "could not load dictionaries/large"
    The file clearly downloaded but it just doesnt seem to work. Would highly appreciate any help

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Check the boolean values / return types of the functions and make sure you load returns true upon successful load.

  • @haamidfarhaan1681
    @haamidfarhaan1681 4 года назад

    So many errors are coming. They are saying total words is not defined

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Make sure you define your variables. If you're stuck ask in cs50 discord, you will almost immediately get help

  • @TheElJoyHunter
    @TheElJoyHunter 4 года назад +1

    what is the meaning of "->" and when can i use it

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Please watch the lecture for this. It's basically a shorthand way to get access to struct's fields

  • @anony-mous8881
    @anony-mous8881 4 года назад

    can i ask ... do you actually learn all the technical coding stuff before hand? or you just pick up from the walkthrough.... u speak like it is super easy... what's the secret?

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад +4

      No secret. I actually have a comp sci degree from a university and I have been coding for about 6 years now. I like explaining concepts and helping others understand :)

  • @karlasdzonsonas2993
    @karlasdzonsonas2993 Год назад

    Doesn't work

  • @Gustavo_Rojas
    @Gustavo_Rojas 4 года назад

    you forgot to close the file

    • @Gustavo_Rojas
      @Gustavo_Rojas 4 года назад

      I just noticed you closed it.

    • @algorithmsillustrator3313
      @algorithmsillustrator3313  4 года назад

      Thank you Gustavo. Yes initially I had forgotten to close it but I did it towards the end of the video.

  • @hessaalresei7084
    @hessaalresei7084 3 года назад

    Hi

  • @videoeditor3045
    @videoeditor3045 2 года назад

    geat