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
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
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.
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
configures clang to name the resulting output file "hello" instead of a.out
source: cs50
a.out is the default file name for the file obtained after compiling using clang
source: cs50
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
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
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
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
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
]
typedef struct node
{
int number;
struct node *left;
struct node *right;
}node;
source: harvard cs50, david malan
typedef struct node
{
int number;
struct node *next;
}node;
source: harvard cs50, david malan
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
