Finished CS50 Week 3 lectures. Talked a bit about recursion, different sort algorithms… pretty interesting.

Very interesting concept of understanding how long it takes an algorythm to finish depending on show it-s built and the number of values to sort We say, to the order of x. So for example O(n^2) or O(n) or nLog(n).

Seems that divide an conquer is def. better than other sorts because it is Onlog(n) and not n squared, so the bigger n grows, it doesn’t slow down as much as the others (like bubble sort, linear sort or whatever).

Different sort algorithms

Selection sort: Search smallest value on whole array and puts it on first position… etc… takes n^2 worst case. / And in the best case scenario? The same! n^2 !

Bubble sort: Lower value elements shift towards left, higher to the right. Check each pair, and smallest needs to be left, if not swap… after first pass the highest will be on right. You know it is sorted when no swaps happen.  In worst case n^2, in best case n!

Insertion sort: First element declare sorted. Then take 1 more, and look at next unsorted element and insert into array sorted.   Worst case scenario is n^2, best case is n.

Merge sort: Uses recursion, and basically divides and sorts left side, then right side then merges. Worst case scenario is n*log(n), and best case scenario is n*log(n)?

Different search algorithms

Linear Search: Worst case scenario is n, and best case is 1

Binary search (for a sorted array): Divide and conquer version of search. Worst case scenario log (n). best case is 1

This binary search tree business is pretty heavy. For the moment I think its good enough that I know that it exists, although I would like to understand how it is used and if it is relevant or not… anyway at any point I can go deeper into them,

GDB debugger

Interesting, have not really used it but seems quite helpful to debug. You need to call the environment and then use commands to do different stuff. What I found most interesting is that you might for instance have a program for which the .c file (source code) is missing, and it’s crashing. GDB allows you to investigate, move through the program and still find out what is wrong (in some cases I guess), even if you are not able to really see the source code. 

Vigenere cypher finished:

I am pretty happy with my development so far, and happy to see I can code basic things in C.  It really is interesting to see how basic thigns do become hard, in terms of for example making a tring all to lower case, and having to constantly keep track of each variable and its type.

Now, I feel I am starting to be able to do stuff… but it is true that I don’t feel fully under control. I mean that, I am not 100% sure that I am using everythign in the most efficient way, and that every variable is named in the right way etc.

Will def. take me more time to get used to all of that.

In the meantime… enjoy my code :D!

 

#include stdio.h
#include cs50.h
#include string.h
#include stdlib.h
#include ctype.h

bool Check_If_Alpha ();
string All_Tolower ();

int main (int argc, string argv[])
{
    // Below I check if input is only alphabetical characters
    if (argc != 2 || Check_If_Alpha(argv[1]) == 0)
    {
       printf("Baad!! I expect only a string of alphab characters\n");
       return 1;
    }
    
    string plaintext = GetString();
    //Here I make key string all lower case just to simplify later
    string kstring = All_Tolower(argv[1]);
    
    for (int i = 0, n = strlen(plaintext), j = 0; i < n; i++)
    {
        int length_key = strlen(kstring);
        // c is current character
        int c = plaintext[i];
        // As k is only lower, its easy to convert to 0-25 index by doing -97
        // This means that "a" won't be 97, it will be 0 etc.
        int k = kstring[j] - 97;

        if (isalpha(c))
        {
            // if current char is alphab, then it proceeds to the conversion
            if (isupper(c))
            {
                int dec_upper = ((c - 65) + k) % 26;
                int ascii_upper = dec_upper + 65;
                printf("%c", ascii_upper);
                j = ((j + 1) % length_key);
            }
            else
            {
                int dec_lower = ((c - 97) + k) % 26;
                int ascii_lower = dec_lower + 97;
                printf("%c", ascii_lower);
                j = ((j + 1) % length_key);
            }
        }
        else 
        {
            printf("%c", c);
        }
        
    }
    printf("\n"); 
    return 0;  
}
   

// This function checks if the input is a positive integer
bool Check_If_Alpha (string a)
{
    for (int i = 0, n = strlen(a); i < n; i++ )
    {
        // if the character is not an alphabetical one
        if (isalpha(a[i]) == 0)
        {
            return 0;
        }
    }
    return 1;
}

// This function turns a string all to lower case
string All_Tolower (string a)
{
    for(int i = 0; a[i]; i++)
    {
         a[i] = tolower(a[i]);
    }
    return a;
}

 

 

Careful not to mix up Strings with Chars:

‘A’ is the char A, but “A” is a string with one char inside! 🙂

Starting Pset2 CAESAR (Creating a ROT(n) encrypter and decrypter):

I am really liking this PSET. Basically so far I am learning how to properly handle command line arguments and I have created my first program with a proper function inside. I hope that I didn’t do an overkill and wrote too much for something that I could have checked in a much more simple way!

Its crazy how something simple like “Checking if an input is a positive integer” actually does require some lines of code on C to make it work. I feel that I am starting to better understand the counter-intuitive things that C requires in order to make things work… due to computers being quite stupid at their core! And I also value a lot higher level languages that allow easier ways to do those checks and stuff.

Had quite a laugh with the article ROT13 on wikipedia. Check it out!

Finalizing Pset1 of cs50

Pretty happy with how easily I am getting used to C and how my program to print a pyramid of ### worked. I did it without looking at the walk through. I am sure it is not optimal, but works fine! Will refine it a bit with comments.

Note: After looking at walk through I see that for input instead of a while loop I can use a DO, while loop like below.

I also finished the Change problem in a way that I like a lot without using loops, just modulo: