Python - hello world

 Hello world in python:

print("Hello, world")

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

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

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

(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

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

Structural testing adequacy criteria - line coverage, branch coverage, path coverage

 structural testing adequacy criteria - line coverage, branch coverage, path coverage

unit testing tool - JUnit

 unit testing tool - JUnit

swtest - test possible corner cases ( called boundary testing)

 test possible corner cases - this is called boundary testing 

software testing

source: edx, automated software testing: unit testing, coverage criteria, and design for testability

arrays -> dynamically allocated arrays -> linked lists

 arrays -> dynamically allocated arrarys -> linked lists

chain of thought

succession of logic

logical order of evolution

source: harvard cs50, david malan

Free a linked list in C

 while(list!=NULL)

{

        node *tmp=list->next;

        free(list);

        list=tmp;

}

source: harvard cs50, david malan

Traverse a linked list in C

 for (node *tmp=list; tmp!=NULL; tmp=tmp->next)

{

        printf("%i\n", tmp->number);

}

source: harvard cs50, david malan