Algorithms and Data Structures

Asymptotic Analysis

• measuring the cost or complexity of an algorithm
• Analyzing what happens as the number of inputs becomes very large is referred to as asymptotic analysis

Rate of Growth

• Rate of growth describes how an algorithm’s complexity changes as the input size grows
• represented using Big-O notation
• Big-O notation uses a capital O (“order”) and a formula that expresses the complexity of the algorithm
• The formula may have a variable, n, which represents the size of the input
• Constant – O(1) : complexity is constant regardless of how large the input size is. The point is that the size of the input does not influence the time the operation takes.

public int GetCount(int[] items) { return items.Length; }

• Linear – O(n) : complexity grows linearly with the size of the input.

public long GetSum(int[] items) { long sum = 0; foreach (int i in items) { sum += i; } return sum; }

• Logarithmic – O(log n): complexity is logarithmic to its size. The binary search tree Contains method implements an O(log n) algorithm
• Linearithmic – O(n log n): A linearithmic algorithm, or loglinear, is an algorithm that has a complexity of O(n log n). Merge sort and quick sort.
• Quadratic – O(n2):

Linked-List

• The Node: A node is a container that provides the ability to both store data and connect to other nodes.

public class Node { public int Value { get; set; } public Node Next { get; set; } }

• Starts with the node first and ends with the node last.
• The Next property for the last node points to null which is the end-of-list indicator.

private static void PrintList(Node node) { while (node != null) { Console.WriteLine(node.Value); node = node.Next; } }

Performance: O(1)

Adding an item to a linked list involves three steps

1. Allocate the new LinkedListNode instance
2. Find the last node of the existing list
3. Point the Next property of the last node to the new node

private LinkedListNode<T> _head; private LinkedListNode<T> _tail;

Keep track of the last node (the “tail” node) in the list and when we add the new node we simply access our stored reference directly. This is an O(1) algorithm and therefore the preferred approach.

Doubly Linked List

• LinkedListNode class to have a new property named Previous

Array List

• Direct indexing of array
• default constructor initializing the array to size 0
• Performance: O(n)

Stack

• A stack is a collection that returns objects to the caller in a Last-In-First-Out (LIFO) pattern.
• last object added to the collection will be the first object returned
• The Stack class defines Push, Pop, and Peek methods, a Count property, and uses the LinkedList<T> class to store the values contained in the stack.
• PUSH: performance – O(1)
• Pop: performance – O(1)
• Peek: performance – O(1)
• Count: performance – O(1)

Queue

• Queues are a First-In-First-Out (FIFO) collection
• This means that items are removed from the queue in the same order that they were added
• backed by a LinkedList
• Enqueue (to add items), Dequeue (to remove items), Peek, and Count
• Enqueue : O(1)  ; To the end of queue
• Dequeue : O(1)  ; To the oldest item
• Peek: O(1)  ;  Returns the next item that would be returned if Dequeue were called
• Count: O(1); Returns the number of items currently in the queue. Returns 0 if the queue is empty.

Binary Search Tree

• Binary search trees take the general tree structure
• A tree is a data structure where each node has 0 or more children
• A binary search tree uses the same basic structure
• Each node can have 0, 1, or 2 children
• Any value less than the node’s value goes to the left child (or a child of the left child).
• Any value greater than, or equal to, the node’s value goes to the right child (or a child thereof)

BinaryTree<int> tree = new BinaryTree<int>(); tree.Add(8); tree.Add(4); tree.Add(2); tree.Add(3); tree.Add(10); tree.Add(6); tree.Add(7);

• Node Class
• BinaryTreeNode represents a single node in the tree.
• references to the left and right children (null if there are none)
• node’s value
• CompareTo method which allows comparing the node values
• Binary Search Tree
• Add, Remove, a Contains method
• Count and Clear methods
• To initialize the tree; represents the head (root) node of the tree
• integer that keeps track of how many items are in the tree
• ADD: O(log n) on average; O(n) in the worst case
• Remove: O(log n) on average; O(n) in the worst case
• Contains: O(log n) on average; O(n) in the worst case
• Count: O(1)
• Clear: O(1); head=null; count=0
• Traversal
• allow processing each value in the tree

Sorting Algorithm

• Bubble sort & Quick Sort
• Swap
• swap values in an array by index

void Swap(T[] items, int left, int right) { if (left != right) { T temp = items[left]; items[left] = items[right]; items[right] = temp; } }

• Bubble Sort

Behavior		Sorts the input array using the bubble sort algorithm.
Complexity	Best Case	Average Case	Worst Case
Time	O(n)	O(n2)	O(n2)
Space	O(1)	O(1)	O(1)

• each time moving the largest unsorted value to the right (end) of the array

public void Sort(T[] items) { bool swapped; do { swapped = false; for (int i = 1; i < items.Length; i++) { if (items[i - 1].CompareTo(items[i]) > 0) { Swap(items, i - 1, i); swapped = true; } } } while (swapped != false); }

• Insertion Sort
• Insertion sort works by making a single pass through the array
• inserting the current value into the already sorted (beginning) portion of the array
• The important concept is that insertion sort works by sorting items as they are encountered
• Since it processes the array from left to right
• we know that everything to the left of the current index is sorted
• When the sorting process begins, the sorting algorithm starts at index 0
• Now, array indexes 0–1 are known to be sorted, and 2–n are in an unknown state
• Now, array from index 0 to 2 is now known to be sorted
•  
• Merge Sort
• Divide and Conquer: algorithms operate by breaking down large problems into smaller, more easily solvable problems
• example, we use a divide and conquer algorithm when searching a phone book
• Merge sort operates by cutting the array in half over and over again until each piece is only 1 item long
• A way to split the arrays recursively
• A way to merge the items together in sort-order
• Quick sort
• divide and conquer sorting algorithm
• works by recursively performing the algorithm
• Pick a pivot index and partition the array into two arrays ; using a random number in the sample code
• Put all values less than the pivot value to the left of the pivot point and the values above the pivot value to the right