~~~~~~~~~~~~~~~~~~~~~~~
~~~ Data Structures ~~~
~~~~~~~~~~~~~~~~~~~~~~~
Week 1 - Friday, September 7th, 2018:
Class:
Introduction to the course

Week 2 - Monday

Week 3 -

Week 4 - Monday, September 24th, 2018:
Class:
Stacks and Queues
Stack - FILO
Queue - FIFO

Operation								Stack 	Queue
-------------------------------------------------------
add an item								push	enqueue
remove an item							pop		dequeue
access the "next" item to be removed	top		front

Socket Programming

Week 4 - Friday, September 28th, 2018:
Class:
	Lab 4 is bracket checking.
	Make a function that examines a string and determines if all the open brackets get closed.
		- They must also close in the proper order
	Use a stack data structure to push open brackets and pop closing brackets. Upon popping you check if the current one you are
	popping match the current closing bracket character.


	Introduction to HashTables



	Assignment 1 - Priority queue
	Everytime you search something the access count is increased by 1. The node is moved closer to the front such that the access cunt within the
	linked list i

	Part 1 - print 10 sheets of paper, draw on it. - Due monday

	erase(first, last) - it erases starting at first but does not delete the last one

	search(14) - find node that has data 14, increase the access count. Move the node up the list to where it belongs

Week 5 - Monday, October 1st, 2018:
	* Copy constructor vs copy assignment
	* Biggest advantage for hash table - get access to any row given that you know its hash. O(1) operation

	Dealing with collisions
	* Bucketing
		You can make it a two dimensional array in a sense.
		It is very inefficient because there will be lots of wasted space.

		Lambda is the number of entries divided by the number of buckets
		8 entries / 6 buckets = 1.33
		avg search = (4 + 2 * 3 + 3) / 8
		13 / 8 = 1.625

Week 5 - Friday, October 5th, 2018:
	---

Week 6 - Friday, October 12th, 2018:
	Quick Sort
		Pick a value from the array as the pivot

		Let i=front, j= back

		advance i until you find a value arr[i] > pivot

		move j towards front of array until arr[j] < pivot

		swap these arr[i] and arr[j].

		repeat step 3 to 5 until i and j meet

		The meeting point is used to break the array up into two pieces

		QuickSort these two new arrays

	Part 3 is easy to do if you use recursion
		Fill until you reach a different color

		Image height that he was using was something

		7, 4, 3, 6, 1, 2, 5, 8
		^
		Pivot

		Make two arrays:
		Array 1: Everything < than the pivot
		Array 2: Everything > than the pivot



bool fill(PixMap& image, const Pixel& fillColour, unt x, int y, const Pixel& orig)
{
	bool rc = false;
	if(x < 0 || y >= image.height() || x >= image.width() || y < 0)
	{
		rc = false
	}
	else if(image.getPixel(x,y) == orig)
	{
		rc = true;
		image.setPixel(fillColour, x, y);
		fill(image, fillColour, x + 1, y, orig);
		fill(image, fillColour, x-1, y, orig);
		fill(image, fillColou, x, y+ 1, orig);
		fill(image, fillColour, x, y-1, orig);
	}
	return rc;
}

bool fill(PixMap& image, const Pixel& fillColour, int x, int y)
{
	Pixel originColor = image.getPixel(x,y);
	return fill(image, fillColour, x, y, origColour);
}

Week 5 - Monday, October 15th, 2018:
=== Midterm review ===
Q1:
What is the run time of the following functions:

int f1(int n){
    int rc=1; // 1
    for(int i=0;i<5;i++){ // 3
        rc+=1; // 1
    }
    return rc;
}

Does the number of operations depend on n?
No
O(1)

Q2:
int f1(int n){
    int rc=1; // 1
    for(int i=0;i<n;i+=2){ // n * 3
        rc+=1; // n * 1
    }
    return rc;
}
O(n/2)
O(n)

Q3:

Suppose that the function function1(n) has a run time of O(n) and function2(n) has a run time of O(n^2) What is the run time of the following function?

int f1(int n){
    function1(n); // O(n)
    function2(n); // O(n^2)
}

O(n + n^2)
O(n^2)

Q4:

Write the following function recursively:

bool isPalindrome(const char* s)

s is a null terminated character string. This function returns true if s is a palindrome.
A palindrome is a string that reads the same forwards and backwards.
Thus: noon, mom, dad are all palindromes. table, texture, glass are not palindromes.

the above function can be a wrapper to a function that actually does the work

Try to write the function to O(n) run time where n is the length of s.

//BAD
bool isPalindrome(const char* s){
	for(i=0; i < strlen(s); i++)
		if(s[i] != s[strlen(s)-i])
			return false;
	return true;
}
//

bool isPalindrome(const char* s){
	int len = strlen(s);
	return isPalindrome(s, len);
}

bool isPalindrome(char* str, int len){
	bool res = false;
	if(len == 0 || len == 1)
		res = true;
	else
		if((str[0] == str[len - 1]) && (isPalindrome(&str[1], len - 2)))
			res = true;
		else
			res = false;
	return res;
}

O(n)

Q5:

Given the following:

class Stack{
   ...
public:
   void push(int v);
   void pop();
   int top();
   bool isEmpty();
};

and

class Queue{
   ...
 public:
   void enqueue(int v);
   void dequeue();
   int front();
   bool isEmpty();

};

Write the function:

void ReOrder(int newarr[], int arr[],int size);

This function creates newarr from the values in arr using the following rules:

size is length of arr
The value 0 separates arr into "chunks"
Each "chunk" can hold both positive and negative values in any order

When creating newarr, each chunk must satisfy the following rules

All negative values go before all positive values
All negative values are added in the same order as their original order.
All positive values are added opposite to their original order
The 0 that was used to separate each chunk is not added to newarr.

Example:

Suppose arr={-3,2,-1,5,1,-4,0,11,12,13,-11,-12};
then when you create newarr, newarr should have the following:
{-3,-1,-4,1,5,2,-11,-12,13,12,11}

Week 7? - Monday, October 29th, 2018:

Lab 5 is basically quick sort.
Given lab5.cpp and timer.cpp and timer.h

rand() generates a random unsigned integer.
srand() seeds the random values

void generateRandom(int array[], int sz)
{
	for(int i = 0; i < sz; i++)
	{
		array[i] = rand();
	}
}

Change position of the pivot point to see if the position of the pivot matters
(Beginning, middle, end, random pivot)

--- Assignment 2 --- Due November 14th, 2018 (or 2 weeks, 2 days from now)

Assignment is about hashing
You are given a table class
Use linear probing as its collision method

Determine the runtime of the functions. Functions are not implemented in the best way possible.
So we have to make them more efficient.
Part A - Determine runtime
Part B - Suggest 3 improvements (Do it in code and comment - Probably should use a Wiki)
Part C - Hash table organizes
Part D - Measure performance

Load factor:
You have 100 available slots but only have 5 items. The load factor is 5%
If the load factor is very low youll expect few or no collisions (Good)
If you have a load factor of 90% you should expect many collisions (Bad)

---------------------------------------------------------------

=== Heap and Heap Sort ===
The binary heap is an implementation of a Priority Queue.

Basic operations on the binary Heap include:
insert - add an item to the binary heap O(n log n)
delete - removed the item with the highest priority in the binary heap O(n log n)

sort - O(n log n)

Everytime you insert something into this heap you must re-organize it.

Week 8 - Monday, November 5th, 2018
Binary trees

A binary tree is where every node has a left and right child.

A sub tree is a tree within itself


inOrder(left, root, right);
1. Traverse the lft subtree in inOrder
2. Process the root
3. Traverse the right subtree in inOrder

---------------------------------------------------------------

Week 8 - Friday, November 9th, 2018

AVL Trees
The principle behind AVL trees is that the depth of the nodes on the left and right should not be off more than 1
If their depths are off by a depth of more than 1 then it's unbalanced.
Search time of a perfectly balanced tree is O(log n)
Insert and delete can also be done in O(log n)

Height balance = height of right - height of left
of node          subtree           subtree

if Height balance is positive then rotate left
if Height balance is negative then rotate right

---------===========---------==========------------==========

Final Exam Review

No sorting
Recursion
Order of magnitude analysis
No linear probing
Heaps
All the trees
Graphs
P vs NP problem