Quicksort

Complexity: O(N * logN)
Quicksort (Wikipedia)

Merge Sort

Merge sort (Wikipedia)

Insertion Sort

Complexity: O(N^2)
Insertion sort - Wikipedia

Bubble Sort

Algorithm:
1: start from the beginning of an array
2: compare current and the next element; if current is bigger than the next one, swap them
3: move one place to the right
4: repeat step 2 till you get to the last element (or, more efficiently till you get to the last highest set in its final location; )
5: goto 1

Complexity: O(N^2)
Bubble sort - Wikipedia

Singly Linked List

- Unordered array has fast insertion and slow search and deletion; ordered array has fast search and slow insertion and deletion; arrays have constant size;

Linked lists:
- have fast insertion and deletion
- can be sorted and unsorted
- can be singly or doubly linked
- are memory efficient: they use as much memory as needed, not more, not less;

Element of a singly linked list is usually called node and it has two parts: data and pointer to the next element.
Head is a pointer that points to the first node.
Tail is a pointer that points to the last node.

Unordered (unsorted) Singly Linked List

Operations:

Insertion to the front (push_front):

- Algorithm: item is added at the front of the list
- Complexity: O(1)

Insertion to the back (push_back):

- Algorithm: item is added at the  back  of the list
- Complexity: O(1) if tail pointer is maintained; O(N) if not because we need to go through all nodes in order to get to the last one - the more nodes - the more steps;

Removal from the front (pop_front):

- Algorithm: remove the item from the front of the list
- Complexity: O(1)

Removal from the end (pop_back):

- Algorithm: remove the item from the  back of the list
- Complexity: O(N) - even if we maintain (use) tail pointer - it is not of a help here as we cannot access to the node which precedes the last node through it in the case of  singly linked list (if we had doubly linked list that would be possible); we need to go through all nodes in order to get to the last one - the more nodes - the more steps;

Search for the item with specific value (key):

- Algorithm: go from the first node and traverse through the list until the item with the specified value is found
- Complexity: O(N)

Ordered (sorted) Singly Linked List

Operations:

// TBD

Circular Queue (Ring Buffer)

Priority Queue

- has front and rear and items are inserted in the rear and removed from the front
- items are ordered by key value, so that the item with the lowest key (or the highest key) is always at the front; items are inserted in the proper position to maintain the order

Deque

Deque is Double Ended Queue: items can be added/removed from the either end of the queue.

Operations:

Insertion to the front (push_front):

- Algorithm: item is added at the front of the queue
- Complexity: O(1)

Insertion to the back (push_back):

- Algorithm: item is added at the  back  of the queue
- Complexity: O(1)

Peek at the front:

- Algorithm: return a value of the item from the front of the queue
- Complexity: O(1)

Peek at the back:

- Algorithm: return a value of the item from the back of the queue
- Complexity: O(1)

Removal from the front (pop_front):

- Algorithm: remove the item from the front of the queue
- Complexity: O(1)

Removal from the end (pop_back):

- Algorithm: remove the item from the  back of the queue
- Complexity: O(1)

Queue

- FIFO concept - First In First Out
- opposite to arrays, only one item can be read or removed at a given time - the oldest item inserted
- its size is predefined: only limited number of items can be added (pushed)
- underlying data structure can be array, vector, linked list

Usage:
- e.g. when performing tasks is slower than the rate tasks are received we want to save tasks in the same order they are received and we want first to execute the oldest tasks: we will put them in the queue

Operations:

Insertion (enqueue):

- Algorithm: item is added at the end (rear) of the queue
- Complexity: O(1)

Peek:

- Algorithm: return a value of the item from the front of the queue (the oldest item in the queue)
- Complexity: O(1)

Removal (dequeue):

- Algorithm: remove the item from the front of the queue (the oldest item in the queue)
- Complexity: O(1)

Stack

- LIFO concept - Last In First Out
- opposite to arrays, only one item can be read or removed at a given time - the last item inserted
- its size is predefined: only limited number of items can be added (pushed)
- stack overflow occurs when a new item is being added but underlying buffer is full
- underlying data structure can be array, vector, linked list

Usage:
- to check whether parentheses ({ }), braces ([ ]) and brackets (( )) are balanced
- to parse arithmetic expressions
- in algorithms applied for other data structures (e.g. traversing binary trees)

Operations:

Insertion (push):

- Algorithm: item is added on the top of the stack
- Complexity: O(1)

Peek:

- Algorithm: return a value of the item from the top of the stack (item that has been added last)
- Complexity: O(1)

Removal:

- Algorithm: remove the item from the top of the stack (item that has been added last)
- Complexity: O(1)

Ordered (sorted) array

- data is ordered (sorted) in ascending (or descending) key order which enables fast search algorithm - binary search (this is the main reason why we want to keep data sorted)
- can be searched with linear search as well

Binary Search Algorithm

Take the idem from the middle of the range (array of sorted elements). If its value is smaller than the searched value then take right sub-array as a new range and repeat this step.

The range will eventually drop to only one member and if its value matches the searched one - item is found.

As in each new iteration range size is halved, the complexity of the algorithm is O(logN). If we double the number of elements, we would need only one extra iteration.

Operations

Insertion:

- Algorithm: linear search is needed to find the first element smaller than the one to be inserted; item is inserted after it and all bigger items are shifted one place towards the end

- Complexity: O(N) (linear search) + O(N) (shifting) = 2 * O(N) ~ O(N)

Search:

- Algorithm: binary search

- Complexity: O(logN) 

Deletion:

- Algorithm: binary search to find the element; once it's found it is removed and all subsequent elements are shifted towards the array beginning

- Complexity: O(logN)(binary search) + O(N) (shifting) ~ O(N)

Unordered (unsorted) array

Array:
-  is a collection of data items (its elements) of the same type arranged contiguously in memory
- can be sorted or unsorted
- can accept or not duplicate values

Array is created with predefined size =>
   - if there are less elements than the array size is => memory waste
   - if there are more elements that the array size is => program fails

Implementations:
- C-style array
- std::vector

Unordered arrays with no duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position); it must be checked whether item already exists in the array - a search is performed
- Complexity: O(N) (because of the search)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)

Unordered arrays with duplicates

Operations:

Insertion

- Algorithm: always at the end (at the first vacant position)
- Complexity: O(1)

Search for a given item (lookup)

- Algorithm: linear search - starts at the beginning and goes through all items till item is found
- Complexity: O(N)

Deletion of a given item

- Algorithm: item must be found first; once its found and removed, all subsequent elements must be shifted down one position (towards the beginning of the array) in order to fill the gap and maintain contiguity of elements in memory
- Complexity: O(N) for search + O(N) for shifting = 2 * O(N) ~ O(N)

Write a function which reverses words in a sentence

Algorithm: reverse all characters in the entire sentence and then reverse characters in each word.

Write a function which reverses a string

Algorithm: maintain two pointers - one that goes from the beginning towards the end of the string and another which is going the other way round; each time they move, swap characters at their positions; stop when pointers try to swap their sides;

We can use helper pointer:



Alternatively, we can use just index:

main.cpp:


Output:

Before reversing: ""
After reversing: ""
Before reversing: "a"
After reversing: "a"
Before reversing: "ab"
After reversing: "ba"
Before reversing: "abc"
After reversing: "cba"
Before reversing: "abcdefg"
After reversing: "gfedcba"

Reversing a string can be achieved by using a helper data structure - stack. Algorithm pushes all characters to the stack and then pops them into the new string which has all characters from an original string reversed.

Write a function which returns a length of a given string

Algorithm: find the last character and return the distance between it and the first one.

We can use helper pointer:



Alternatively, we can use just index:

main.cpp:


Output:

String: ""
Length: 0
String: "a"
Length: 1
String: "ab"
Length: 2
String: "abc"
Length: 3
String: "abcdefg"
Length: 7

What is the problem with this code...?

And why does this work?:

What's correct way to declare two variables that are of type pointer to type Node:1) Node *p1, *p2;2)Node* p1, p2;

Write a code that allocates and then frees an array of seven pointers to functions that return integers.

int (**p) () = new (int (*[7]) ());
delete *p;

http://msdn.microsoft.com/en-us/library/kewsb8ba.aspx

Explain class templates

- Non-type parameters for templates: templates can also have regular typed parameters, similar to those found in functions

- it is possible to set default values or types for class template parameters

- we can create algorithms which evaluate at compile time (factoriel)

Template (C++) (Wikipedia)

Parse the following declaration:char (*(*a[4])())[5]

what does this mean char (*(*a[4])())[5]?

The Clockwise/Spiral Rule

cdecl.org