Showing posts with label cs50. Show all posts
Showing posts with label cs50. Show all posts

Thursday, March 11, 2021

compiling

 compiling is the process of converting source code to machine code

but it actually consists of the following steps:

pre-processing

compiling

assembling

linking

(when we say compile, we are actually referring to these four steps, but we wont dwell on such low-level details)


pre-processing - looks for "#" , and then finds-and-replaces, copy-and-pastes



cs50 week 2 video 12:40

source: cs50



-lcs50 ---- argument for linking binaries

 clang -o hello hello.c -lcs50



this argument tells the compiler to link the cs50 library binaries


-lm   ....... links a math library

-lcrypt   ......... links to a cryptography or encryption library



make automates the work of manually typing in a whole bunch of command line argument when compiling



cs50 week 2 video 9:30 , 10:42


source: cs50



Wednesday, March 10, 2021

hash table - array of linked lists

 


source: cs50 

trie (comes from the word "retrieve") - actually a tree made up of arrays

 

a tree whose nodes are each arrays


and each of those arrays are arrays of pointers to other nodes


constant time lookups and insertions


if someone's name has 200 letters , lookup time would be  big O of (200)


it doesnt matter how many names are in the trie data structure (1 billion, 2 billion, 3 billion), lookup time only depends on number of letters in name


tries give you the holy grail of constant time





source: cs50. 



what is the running time for looking up a hash table

big O of (n)




source: cs50

Tuesday, March 9, 2021

String name = get_string("What is your name: ");

 using cs50's get_string function:


#include <cs50.h>

#inlcude <stdio.h>


int main(void)

{

        String name = get_string("What is your name: \n");

        printf("Hi %s\n" , name);

}


source: cs50


clang -o hello hello.c. (command line arguments - inputs. to the command)

 configures clang to name the resulting output file "hello" instead of a.out


source: cs50



a.out - stands for "assembly output".

 a.out is the default file name for the file obtained after compiling using  clang



source: cs50

clang - a compiler (a program that converts source code to machine code)

 



source: cs50



make -

 if you type command : "make hello"

the make program will automatically look for a file called "hello.c" to compile

and will produce a file called "hello" that you can execute



source: cs50



Monday, March 8, 2021

(trees) vs (binary trees) vs (binary search trees) in computer science

 not completely the same




avl trees , red black trees - built-in balancing mechanisms

 

algorithms for shifting while inserting or deleting built in to keep binary tree  "logarithmic in height"  rather than  "linear in height"


inserting into a balanced binary tree is indeed big O of logn , but that depends on the prerequisite of you keeping the binary search tree balanced



source: cs50



sorting algorithms - bubble sort, insertion sort, selection sort, merge sort

  source: harvard cs50 

Data structures comparison - arrays, linked lists, hash tables, tries

 

Arrays:

- insertion is bad - lots of shifting to fit an element in the middle (except for inserting at the end of the array, anywhere other than the end of the array is not so great)

- deletion is bad - lots of shifting after removing an element (except for deleting from the end of the array, unless we don't care about leaving empty gaps, which we usually don't want)

- lookup is great - random access, constant time 

- relatively easy to sort

- relatively small size-wise

- stuck with a fixed size, no flexibility



Linked lists:

- insertion is easy - just tack onto the front

- deletion is easy - once you find the element

- lookup is bad - have to rely on linear search

- relatively difficult to sort - unless you are willing to compromise on super-fast insertion and instead sort as you construct

- relatively small size-wise



Hash tables:

- insertion is a two-step process - hash, and then add

- deletion is easy - once you find the element

- lookup is on average better than with linked lists because you have the benefit of a real-world constant factor

- not an ideal data structure if sorting is the goal - just use an array

- can run the gamut of size




 



source: harvard cs50 david malan



linked list - big O of n

 


source: harvard cs50, david malan

what is the running time of inserting into a binary search tree?

 big O of  logn


things related to binary search are often  big O of logn


if you have a well-balanced binary tree, if it has a total of n nodes, then  log-based-2-of-n will be the height of the tree


source: harvard, cs50, david malan



Sunday, March 7, 2021

code for searching binary search tree (BST)

 bool  search (node *tree, int number)

{

//always check for NULL when dealing with pointers

//this is also the base case

        if (tree==NULL)

        {

                return false;

        }

//

        elseif (number < tree->number)

        {

                return search (tree->left, number);

        }

        elseif (number > tree->number)

        {

                return search (tree->right, number);

        }

        elseif (number == tree->number)

        {

                true;

        }


}



video location: lecture 5.  1:20:00 ~ 1:30:00

source: harvard cs50, david malan


]

code for creating node for binary search tree (BST)

 typedef struct node

{

        int number;

        struct node *left;

        struct node *right;

}node;



source: harvard cs50, david malan



code for creating a node for a linked list

 typedef struct node

{

        int number;

        struct node *next;

}node;



source: harvard cs50, david malan

binary search tree (BST)

 requires array in sorted order

requires random access of arrays

very powerful because big O of logn


location in week 5 video: 1:20:00

source: harvard cs50, david malan