Data Structure & Algorithm is the fundamental knowledge of programming. Learning how to store, organize, sort, search data allow us to code more efficiently and concisely.

Learning outcome

Apply structural programming approach to solve more complex computation problems.
Demonstrate applications of standard data structures such as linked list, stack, queue and tree.
Solve computation problems using recursion where appropriate.
Understand different sorting and searching algorithms.

Chapter 1 - Basic Concepts of C++

Terminology

Abstract Data Type (ADT)

Common Standard Library Header

<cstdio>
Support Standard I/O functions: printf(), scanf(), getchar(), fopen(), fclose(), etc..
<cstdlib>
Support Standard utility functions: malloc(), free(), rand(), etc..
<cstring>
Support String functions: strcpy(), strcmp(), memset(), etc..
<iostream>
Perform both input and output operations with the stream objects : cin and cout

Comments

1
2
3
4
5
6
7
8 /* Block Comment */
 
/*
*  Block comment
*/
 
// Single line comment

Primitive Data types

Data type	Size (byte)	Representation	Range of values
bool	1	Boolean	$\textnormal{false / true}$
char	1	Signed number (2's complement)	$\textnormal{-128 to 127}$
unsigned char	1	Unsigned number	$\textnormal{0 to 255}$
int	4	Signed number (2's complement)	$-2^{31} \space \textnormal{to} \space 2^{31}-1$
unsigned int	4	Unsigned number	$\textnormal{0 to } 2^{32}-1$
short	2	Signed number (2's complement)	$-2^{15} \space \textnormal{to} \space 2^{15}-1$
unsigned short	2	Unsigned number	$\textnormal{0 to } 2^{16}-1$
long	4	Signed number (2's complement)	$-2^{31} \space \textnormal{to} \space 2^{31}-1$
unsigned long	4	Unsigned number	$\textnormal{0 to } 2^{32}-1 $
long long	8	Signed number (2's complement)	$-2^{63} \space \textnormal{to} \space 2^{63}-1$
unsigned long long	8	Unsigned number	$\textnormal{0 to } 2^{64}-1 $
float	4	IEEE 32-bit floating point number	$\pm 1.410^{-45} \textnormal{ to } \pm3.410^{38}$
double	8	IEEE 64-bit floating point number	$\pm 510^{-324} \textnormal{ to } \pm1.79810^{308}$
pointer	4	Memory address	$\textnormal{0 to } 2^{32}-1$

C++ File Structure

Header file (.h) Program file (.cpp)
Functions Declaration Functions Implementation

Chapter 2 - Computation Complexity (Big-O)

There are two types of complexity

Time Complexity (Time spent)
Space Complexity (Memory space spent)

They both use three asymptotic notation to descript the complexity

$\textnormal{Big-O (O)}$
$\textnormal{Big-Omega }(\Omega)$
$\textnormal{Big-Theta }(\Theta)$

Big-O

Upper bound of the complexity

$f(n) = \textnormal{O}(g(n))$

Big-Omega

Lower bound of the complexity

$f(n) = \Omega(g(n))$

Big-Theta

Exact bound of the complexity

$f(n) = \Theta(g(n))$

Common Complexity Classes

Constant time - $O(1)$
Logarithmic time - $O(\log_2 n)$
Linear time - $O(n)$
Log-linear time - $O(n\log_2 n)$
Quadratic time - $O(n^2)$
Cubic time - $O(n^3)$
Polynomial time - $O(n^k)$
Exponential time - $O(2^n)$
Factorial time - $O(n!)$

Slope of Complexity Classes

Complexity Classes

TIme Complexity

Simple operations such as

declaration, assignment
cin, cout
function call
return

take constant amount of time
The overall time complexity = O(Constant),
and constant time costs almost zero influence no matter the size.
Therefore the overall time complexity is

$O(1)$

Only looping will cost longer time complexity
Single nested loop usually takes constant time * size of loop as the operations C inside the loop will run n times.

$C * n$

1
2
3 for (int i = 0; i < n; i++)
    sum += i;

The overall time complexity is

$O(n)$

While for more than one nested loop usually takes constant time * (n ^ depth of nest) as the operations C inside the loop will run n * n * ... times.

$C * n^2$

1
2
3
4 for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        sum += i + j;

The overall time complexity is

$O(n^2)$

Best case

To be added..

Average case

To be added..

Worst case

To be added..

Space Complexity

To be added..
O()

Chapter 3 - Linked Lists

A linked list is an object that only contains head node of the list.
Each node is created with parameter [next] linked to next node or necessaryly [prev] linked to previous node.

Terminology

Predecessor
Successor

Josephus Problem

People are standing in a circle waiting to be executed.
Counting begins at a specified point in the circle and
proceeds around the circle in a specified direction. After
a specified number of people are skipped, the next
person is executed. The procedure is repeated with the
remaining people, starting with the next person, going in
the same direction and skipping the same number of
people, until only one person remains, and is freed

The problem — given the number of people (n), starting
point, direction, and number to be skipped (k) — is to
choose the position in the initial circle to avoid execution.
(guessing who is the survivor)

Linear List

Unordered / Random List

Ordered List

General List

Restricted List

Common Operations

Find length of linked list

1
2
3
4
5
6
7
8 int len = 0;
node *cur = head; //traverse the list using cur
 
while (cur != NULL) { // cur points to a valid node
	len++;
	cur = cur->link; //move to the next node
}

Search element x from the beginning of list

1
2
3
4
5
6 node *cur = head;
while (cur != NULL && cur->info != x) { // search x
	cur = cur->link;
}
// cur now points to target x or is NULL (x not exist)

Insert new element x at the front of list

1
2
3
4
5
6 node *p = new node; // create the node dynamically for storing x
p->info = x;
 
p->link = head; // step 1
head = p; // step 2

Remove the first element x found in the list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 node *cur = head;
node *prev = NULL; // prev points to the predecessor of cur
 
while (cur != NULL && cur->info != x) { // search x
	prev = cur;
	cur = cur->link;
}
// if cur == NULL, x is not found in the linked list
if (cur != NULL) { // cur->info == x
	if (prev != NULL) // why checking this?
		prev->link = cur->link; // skip cur node
	else // cur is the first node in the list
		head = cur->link; // x is the first node
	delete cur; //free the storage of the removed node
}

Insert new element x in an ordered list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 node *p = new node;
p->info = x;
 
if (head == NULL || x <= head->info) {
	p->link = head; //insert at front
	head = p;
} else { //head != NULL && x > head->info
	node *prev = head; // x to be inserted between prev and cur
	node *cur = head->link; // i.e. prev->info < x <= cur->info
	
	while (cur != NULL && x > cur->info) { // search position
		prev = cur;
		cur = cur->link;
	}
	
	// end-of-list OR x <= cur->info, so insert node p after node prev
	p->link = prev->link;
	prev->link = p;
}

Common Issues

Null-pointer exception
Memory leak

Variants of Lists

Singly Linked List with Header Node

Sentinel node

Circularly Linked List

Last node points back to first node

Doubly Linked List

Each node has next and back pointers

Circular Doubly Linked List

Boundary-tag method

Orthogonal List

Chapter 4 - Stacks and Queues

To be added..

Terminology

To be added..

Stack

Last In First Out (LIFO)

Queues (FIFO)

First In First Out (FIFO)

Chapter 5 - Recursion

To be added..

Terminology

To be added..

Chapter 6 - Binary Trees

To be added..

Terminology

To be added..

Chapter 7 - Sorting and Searching Algorithms

To be added..

Terminology

To be added..

Chapter 8 - Hashing

Terminology

Indexing
Perfect Hashing
Minimal Perfect Hashing
Hash Collision
Open Addressing
Closed Addressing
Design of Hash function

Introduction of Hashing

Hashing is generally [ Indexing ].

If you have learnt what [ index ] is, you may understand it as positioning or classifying objects with duplicated meaning for a smaller size of data and better searching.

Steps for Indexing

Define an array with a specific purpose.
Define meaning for each index in the array.
Classify the input and determine the size of the array.
Map the input to the array.

Example of Indexing (Minimal Perfect Hashing)

Given A string [foo] = "abacbdef".
Precondition: there will only be alphabets inside the string.
If you want to find how many 'a' occured inside the string, you may use Indexing.

Define an array for storing the occurrence of letters.
Each index represents an alphebet.
There are a total of 26 alphabets as potential input, so the size of array will be 26.
Similar to the ASCII table, we can take index [0] representing the occurrence of 'a', index [1] representing the occurrence of 'b', and so on...
Loop over the string and map the character to corresponding index.

However, there are still some differences between Hashing and Indexing.
In Hashing, we convert ASCII char to key directly with array[i] - 'a' so that 'a' = 0, 'b' = 1, and so on...
which allows us to map the data easier and faster.

Hash function

A function f(k) is known as defined with specific formula,
it can be either One-to-one, or Many-to-one,
Under this property,
it can convert a large variable-sized amount of data into a small datum by transforming data into keys.

A Hash table arr[ ] is an array that will be created to hold the keys after conversion.

A Hash value is usually an integer that may serve as an index to an array.

Example of Hash function

Hashing Student ID k using Modulo, where h is the function, h(k) is the hash value of k, n is an arbitrary key.

$h(k) = k \bmod n$

The size of the array will be reduced significantly due to the limited range of the modulus [0 to n-1].

Take k = 5000, n = 5, the function will be

$h(k) = k \bmod 5$

In Hash table, the value k will be updated to the index of hash value, arr[h(k)] = k

$h(5000) = 5000 \bmod 5 = 0$

arr[0] = 5000, arr[1] = 5081, arr[2] = 5072, arr[3] = 5023, arr[4] = 5014

You may now be thinking of what if the index collides, it should happen frequently as the function is many-to-one.

Yes, and therefore, I am going to introduce the solution against collision.

Hash Collision

Collision occurs when two distinct data own the same hash value.
Collisions are usually unavoidable when a large set of data is mapped into small datum.
It will increase the average cost of lookup operations.

Solutions to Hash Collision

Open Addressing
Closed Addressing

Load factor represents the length of data in each index,
larger load factor brings lower performance

Open Addressing

Place the key in other free slot when collisions occured.

An index only maps to 1 key.
Theoretical max load factor = 1

Advantages

No size overhead apart from the hash table array
Better memory locality and cache performance. Memory allocation is laid out linearly
Performs better when the number of keys is known in advance and the churn is low.

Example of Open Addressing:

Linear Probing
Quadratic Probing
Double Hashing
Hopscotch hashing
Robin Hood hashing
Cuckoo hashing
2-Choice hashing

Linear Probing

To be added..

Quadratic Probing

To be added..

Double Hashing

To be added..

Closed Addressing

Place the key in the same slot even when collisions occured.

An index can map to multiple keys.
Theoretical max load factor = depends

To achieve placing multiple keys in same slot

Separate chaining using linked lists
Separate chaining using dynamic arrays
Using self-balancing binary search trees

Advantages

Easier removal
Assign quicker with high load factor
No issues with Clustering

Example of Closed Addressing:

Chaining Buckets

Chaining Buckets

To be added..

After dealing with collision, there will be two general types of Hashing.

Minimal Perfect Hashing (Best)

A hash function that maps each valid input to a different hash value.
Every index is taken in the hash table.

Perfect Hashing

A hash funciton that maps n input keys to n consecutive hash values.
But not every index is taken in the hash table.

Designing Hash Functions

Ideal properties

Low Cost
- Easier and faster to compute the result
Variable Range
- Able to transform [words], [symbols] into [numbers]
Uniformity
- Distribute the keys evenly
- Minimize the chance of collisions

Common types of Hash Functions

Division
Mid-Square
Folding
Radix Transformation

Division

hashValue = key % tableSize
Try to use prime number as the hash table size to reduce collisions

For non integer keys, transform them into integer with ASCII code

1
2
3
4
5
6
7
8 int hash(char key[size]){
	int k = 0;
	for (int i = size; i > 0; i--)
		k += key[i];   // Sum of the ASCII
	// or k ^= key[i];  // XOR of ASCII
	return k % tablesize;
}

Mid-Square

Transform keys into integer
Sqaure the number
Pick some digits from the middle to hash

Take tableSize = 5

$\textnormal{key}$	$\textnormal{key}^2$	$\textnormal{new key}$	$\textnormal{hashValue}$
99	9801	80	80 % 5 = 0
145	21025	102	102 % 5 = 2
342	116964	69	69 % 5 = 4

Folding

Split key into 3 parts [ Left, Middle, Right ] as you wish,
left and right should have the same size
Fold keys and sum the keys

Shift-folding

Sum the splitted keys directly

Take tableSize = 5

$\textnormal{key}$	$\textnormal{split}$	$\textnormal{new key}$	$\textnormal{hashValue}$
5829	58-29	58 + 29 = 87	87 % 5 = 2
452642	45-26-42	45 + 26 + 42 = 113	113 % 5 = 3
1234567	123-4-567	123 + 4 + 567 = 694	694 % 5 = 4

Boundary-folding

Invert the left and right part of each splitted part except middle one
Then sum the keys

Take tableSize = 5

$\textnormal{key}$	$\textnormal{split}$	$\textnormal{new key}$	$\textnormal{hashValue}$
5829	58-29	85 + 92 = 177	177 % 5 = 2
452642	45-26-42	54 + 62 + 24 = 140	140 % 5 = 0
1234567	12-345-67	21 + 345 + 76 = 442	442 % 5 = 2

Radix Transformation

Define same key with new radix then convert back to original radix

Given $ k = 358345_{10} $
Define $ k_2 = 358345_{9} $\$ h(k) = k_2 \space mod \space tableSize $\$ k_2 = 358345_{9} = 216068_{10} $\$ h(k) = 216068_{10} \space mod \space tableSize $

Useful shortcut

Convenient Mathematics formulas for programming

Gauss Summation

$\frac{n(n+1)}{2}$

Calculate the sum of integers from 1 to n inclusively

$\frac{(a+b)(b-a+1)}{2}$

Calculate the sum of natural numbers from a to b inclusively

To be added..