*************
PRE-QUIZ SUMMARY
*************

An algorithm is a set of steps taken to solve a problem; algorithms have several characteristics, including:
=>space complexity (how much memory/storage does it take?)
=>time complexity (how much time will it take, how efficient is the algorithm relative to the input source?)
=>inputs 
=>output
=>classification (serial, ie. works on dataset in sequential manner, or parallel, ie. breaks dataset into smaller pieces to work on; exact, approximate, deterministic/nondeterministic..)

Common algorithms include SEARCH, SORT, COMPUTATIONAL (calculating some data based on inputs), and COLLECTION algos (count, filter data, etc.)

We use Big O notation to denote how efficient an algorithm is in relation to the size of a dataset; does its performance time increase linearly with an increase in dataset size, or logarithmically, or exponentially? or not at all?

***********************************


Example: Euclid's algorithm

*To find the greatest common denominator of two integers, where a > b, divide a/b ; if there's a remainder, set a to b, and set b to the remainder number, and repeat (divide a/b again) until there is no remainder;  the last denominator used is your GCD*

-->consider this code:

def gcd(a, b)
  while (b != 0)
     t = a
    a = b
    b = t % b
  return a

This function contains a while loop that will run until variable b is equal to zero.

On each iteration of the loop, we store the value of a in a temporary variable, t, so that we can then set a to b; we then get the remainder value from dividing the initial value of a by b; the loop will repeat if there is any remainder 



Euclid's algo, example:

Imagine we run the previous function as shown here: 

gcd(20, 8)

Here, the function would check the remainder value of 20 / 8 ; it would then set variable a to the value of b, which is 8, and set variable b to the remainder value; we would then divide 8/4; this would have no remainder, which means that the GCD in this case is 4

We measure algorithm performance using Big O notation; this classifies the algorithm's performance as input size grows.

The O stands for order of operations.

Common big O classifications include:

0(1)  --- constant time --- this means that performance doesn't depend on the dataset's size

0(log n) --- logarithmic time complexity --- this means that time requirements increase at around half the rate of a dataset's size increases

0 (n) --- linear time complexity --- this means that time requirements increase at around the same rate as a dataset's size increases 

0 (n log n) --- log linear time complexity --- this is  less efficient than linear time complexity

0 (n^2) --- quadratic time complexity  --- this is the least efficient of the common big O notations; time requirements increase in an exponential manner relative to datsaset size increases

****************
DATA STRUCTURES
****************

Review:

There are several types of data structures in programming; important structures include: arrays, linked lists, stacks, queues trees, and dictionaries.



An array is a collection of elements that are identified by an index or key; when an item in an array is removed/inserted, everything after that index must be moved.

The time required to calculate an item's index is not dependent on dataset size ; it has a big O value of O(1) .

Typically, inserting an item at the end of an array also has a big O value of O(1), but inserting at the beginning or middle has a value of O(n), meaning linear time complexity


Consider this code:

arr[2, 1]

In python, selecting an item like this indicates that arr is a 2-dimensional array; that is, an array where each element is another array.


A linked list is a linear collection of data elements, or nodes; each node contains a reference to the next node in the list.

A singly-linked list's nodes only have one reference, to the neighbor that follows them; a doubly-linked list's nodes have references to their neighbors on both sides.

Items in linked lists are not stored contiguously, unlike arrays ; the advantage here is that when you insert or remove elements from a linked list, the underlying memory for the other elements in the list doesn't need to reorganize, for the most part

The disadvantage of linked lists is that looking up an item is slower; the program must start at the head - the first item in a linked list - and work its way down through each node, until the target is found; this has a big O value of linear time complexity, or O(n)

A stack is a series of data elements; it has two main operations, push and pop; it's operations are LIFO, meaning last in first out; this means that new items are added at the end of the list, and the first items to be removed are those at the end of the list ;

An example of a stack is the browser history stack, or the call stack in javascript

A quiz companion to Joe Marini's LinkedIn course