Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data Structure & Algorithm (Recursion (Rules (Know how to take one…
Data Structure & Algorithm
Linked List
: A linear data structure composed of nodes, each node holding some information and a reference to another node in the list
Singly Linked List
Data/info and a pointer points to next node
Head and tail contain data
Methods: addFirst(), addLast(), addPos(p, index),
getFirst(), getLast(), get(index), set(p, index),
removeFirst(), removeLast(), removeAll(),
search(p), size(), isEmpty()
Doubly Linked List
Data/info
2 pointers: prev and next
Header and trailer don't contain data
Methods: ...(same as singly), getPrev(p),
getNext(p), removeNext(p), removePrev(p)
Circular Linked List
Data/info and a pointer points to next node
Head and no tail
Methods: similar to singly and have an rotate() method
Application: Round-Robin Scheduling: Managing processes in an operating system
Self-referential:
an object whose elements is a reference to
another object of its own type
Linked structure:
A collection of nodes storing data and links to other nodes
Queue
A waiting line that grows by adding elements to its end and shrinks by taking elements from its front
FIFO structure: First In/First Out
Methods: clear(), isEmpty(), enqueue(), dequeue(), front(), rear(), size()
Applications
Waiting lists, bureaucracy
Access to shared resources (e.g., printer)
Multiprogramming
Auxiliary data structure for algorithms
Component of other data structures
Circular Queue
(Applications)
Round-Robin Scheduling
Multiplayer, turn-based games
Double-ended queue (deque)
Supports insertion and deletion at both the front and the back of the queue
Methods: addFirst(el), addLast(el), removeFirst(), removeLast(), first(), last(), size(), isEmpty()
Complexity: O(1)
Priority Queue
Can be assigned to enable a particular process, or event, to be executed out of sequence without affecting overall system operation
Elements are dequeued according to their priority and their current queue position
Unsorted List:
Methods: size(), isEmpty(), insert(el) (Complexity: O(1))
Methods: min(), removeMin() (Complexity: O(n))
Sorted List:
Methods: size(), isEmpty(), min(), removeMin() (Complexity: O(1))
Method: insert(el) (Complexity: O(n))
Recursion
A base case (anchor or the ground case) that does not contain a reference to its own type
An inductive case that does contain a reference to its own type
For example: Define the set of natural numbers
A recursive program/algorithm is one that calls itself again
Rules
Know how to take one step
Break each problem down into one step plus a smaller problem
Know how and when to stop
Types of recursion
Linear recursion:
Only 1 recursive call (to itself) in side the recursive function (e.g. binary search)
Binary recursion:
There exactly 2 recursive calls (to itself) inside the recursive function (e.g. Fibonacci number)
Multiple recursion:
There are 3 or more recursive calls (to itself) inside the recursive function
Tail-recursion:
There is only one recursive call at the very end of a method implementation
Non-tail recursion:
The recursive call is not at the very end of a method implementation
If f() calls itself, it is
direct recursive
If f() calls g(), and g() calls f(). It is
indirect recursion
Serve two purposes:
Generating new elements
Testing whether an element belongs to a set
Examples:
The Tower of Hanoi
Drawing fractals
Von Knoch snowflakes
Tree
Definition
Empty structure is an empty tree
Non-empty tree consists of a root and its children, where these children are also trees
Applications
Organization charts
File systems
Programming environments
Terminology
Root:
unique node without a parent
Internal node:
node with at least one child
External (leaf) node:
node without children
Ancestors
of a node: parent, grandparent, great-grandparent,…
Descendants
of a node: child, grandchild, great-grandchild, etc.
Level
of a node (depth): The level of the root is 1. If a father has level i then its children has level i+1
Sub-tree:
tree consisting of a node and its descendants
Height of a tree:
maximum level
in a tree, thus
a single node is a tree of height 1
. The height of an empty tree is 0
Height of a node
p is the height of the sub-tree with root p
Degree (order)
of a node: number of its non-empty childrens
Each node has to be reachable from the root through a unique sequence of arcs (edges), called a
path
The number of arcs in a path is called the
length of the path
Depth-first Traversal
Pre-order:
root, left, right
Application: print a structured document
Post-order:
left, right, root
Application: compute space used by files in a directory and its subdirectories
In-order:
left, root, right
Application: Computing a graphical layout
of a binary tree
Breadth-first Traversal
(Level-order Traversal)
In a breadth-firth traversal, a node is visited first, then all its' children, then all its grandchildren,...
Application: visit family tree by generations
Binary Tree
Definition: A tree in which each node has at most two children. (Thus an empty tree is an binary tree)
Types:
Proper binary tree
(sometimes
full binary tree
or
2-tree
), every node other than the leaves has two children
Complete binary tree
, all non-terminal nodes have both their children, and all leaves are at the same level
Binary Search Tree
: A node based binary tree data structure
The
left subtree
of a node contains only nodes with keys
less than the node's key
The
right subtree
of a node contains only nodes with keys
greater than the node's key
Both the left and right subtrees must also be binary search trees
Each node (item in the tree) has a distinct key
Delete
Merging:
Making one tree out of the two subtrees of the node and then attaching it to the node’s parent
Copying:
Replace the key being deleted with its immediate predecessor (or successor)
A key’s predecessor is the key in the rightmost node in the left subtree
Balanced Binary Tree
A binary tree is
height-balanced
if for every internal node p of T, the heights of the children of p differ by at most 1
A tree is considered
perfectly balanced
if it is height-balanced and all leaves are to be found on one level or two levels
The main goal is to keep the depths of all nodes to be O(log(n))
An
AVL tree
(by
A
delson
V
elskii,
L
andis) is a height-balanced binary search tree
Heap
The value of each node is greater (less) than or equal to the values stored in each of its children
The tree is
nearly complete
, i.e. it is perfectly balanced, and the leaves in the last level are all in the leftmost (rightmost) positions
Heap is used as Priority Queue and for heap-sorting
Graph
A
graph
is a collection of
vertices and the connections between them
Applications: Mapping, transportation, computer networks, electrical engineering, database (entity-relationship diagram)
Terminology
Directed
-> Directed graph
Undirected
-> Undirected graph
Mixed graph:
A graph that has both directed and undirected edges
The two vertices joined by an edge are called the
end vertices
(or
endpoints
) of the edge
Two vertices u and v are said to be
adjacent
if there is an edge whose end vertices are u and v
An edge is said to be
incident
to a vertex if the vertex is one of the edge’s endpoints
deg(v)
, is the number of incident edges of v
If deg(v) = 0 then u is called
isolated vertex
Multigraph:
A graph containing
multiple edges (parallel edges)
but no loops
-> Refers to the group of edges as a
collection
, not a set
Simple graph:
Graphs do not have parallel edges or self-loops
-> The edges of a simple graph are a
set
of vertex pairs (and not just a collection)
Path:
A sequence of alternating vertices and edges that starts at a vertex and ends at a vertex such that each edge is incident to its predecessor and successor vertex
-> A path is
simple
if each vertex in the path is distinct
Directed path
Cycle:
A path that starts and ends at the same vertex, and that includes at least one edge
-> A cycle is
simple
if each vertex in the cycle is distinct, except for the first and last one
Directed cycle
A undirected graph G is
connected
if, for any two vertices, there is a path
A directed graph G is
strongly connected
if for any two vertices u and v, there is a directed path
A directed graph is called
weakly connected
if replacing all of its directed edges with undirected edges produces a connected (undirected) graph
A
subgraph
of a graph G is a graph H whose vertices and edges are subsets of the vertices and edges of G, respectively
A
spanning subgraph
of G is a subgraph of G that contains all the vertices of the graph G
If a graph G is not connected,
its maximal connected subgraphs are called the
connected components
of G
Articulation point (cut-vertex):
If the vertex is removed from a graph (along with incident edges) and there is no way to find a path from a to b, then the graph is split into two separate subgraphs
If an edge causes a graph to be split into two subgraphs, it is called a
bridge
or
cut-edge
Connected subgraphs with no articulation points or bridges are called
blocks
A
complete graph
is a graph where every pair of vertices is connected by an edge
Spanning Tree
A
tree
is an undirected, connected graph without simple cycles
A
spanning tree
is a tree that includes all vertices of the original graph
Minimum Spanning Trees (MST)
are useful in many applications, for example, finding the shortest total connections for a set of edges
Cycle, Path
Euler path:
A path traversing all the edges of the graph exactly once
A connected multigraph has an Euler path but not an Euler cycle if and only if it has exactly two vertices of odd degree
Euler cycle:
A cycle traversing all the edges of the graph exactly once
A connected multigraph has an Euler cycle if and only if each of its vertices has even degree
Hamilton path:
Visits every vertex of the graph exactly once
Hamilton cycle:
Visits every vertex of the graph exactly once before returning, as the last step, to the starting vertex
Sorting
Bubble Sort
Complexity: O(n^2)
Best case: O(n)
Selection Sort
Complexity: O(n^2)
Insertion Sort
Complexity: O(n^2)
Best case: O(n)
Quick Sort
Best & Average case: O(n.logn)
Worst case: O(n^2)
Merge Sort
Complexity: O(n.logn)
Heap Sort
Complexity: O(n.log cơ số 2 n)
Radix Sort
One of the fastest sorting algorithms for numbers or strings of letters
Disadvantage: Can be slower than some other algorithms such as Quick Sort and Merge Sort
Topological Sort
Hashing
A technique used for performing insertions, deletions and finds in constant average time (i.e. O(1))
Not efficient in operations that require any ordering information among the elements, such as findMin, findMax and printing the entire table in sorted order
The ideal hash table structure is merely an array of some fixed size, containing the items
The size of the array is
TableSize
The mapping is called a
hash function
Unbiased: If we randomly choose a key, x, from the key space, the probability that f(x) = i is 1/M, where M is the size of the hash table
We call a hash function that satisfies
unbiased property
a
uniform hash function
Folding Hash Function
Shift folding:
Shift all parts except for the last one, so that the least significant bit of each part lines up with corresponding bit of the last part. Suppose x = 72320354121324
x1=723, x2=203, x3=541, x4=213, x5=24,
index= (x1 + x2 + x3 + x4 + x5) % 1000 = 1704%1000 = 704
Boundary folding
(folding at the boundaries): Reverses every other partition before adding
x1=723, x2=302, x3=541, x4=312, x5=24, index=1902%1000 = 902
Applications
Databases:
Efficient retrieval of records
Compilers:
Symbol tables
Games:
Lookup board configuration to find the move that goes with it
UNIX shell:
Quick command lookup
IP Routing:
Fast IP address lookup
A
HashMap
is a is an implementation of a Map ADT using hashing technique
HashSet
is another implementation of a set (an object that stores unique elements)
A
HashTable
is roughly equivalent to a
HashMap
except that it is
synchronized
and
does not permit null values
with methods to operate on hash tables
Collision Resolution
Open addressing method:
The collision is resolved by finding an available table entry other than the position (address) to which the colliding key is originally hashed
Chaining method:
Each position of the table is associated with a
linked list
or
chain
of structures whose
info
fields store keys or references to keys
The table can never overflow, because the linked list is extendible
Stack
A linear data structure that can be accessed only at one of its ends for storing and retrieving data
Last In, First Out (LIFO) data structure
Methods: clear(), isEmpty(), push(el), pop(), top(), last(), size()
Applications
Any sort of nesting (such as parentheses)
Evaluating arithmetic expressions (and other sorts of expression)
Implementing function or method calls
Keeping track of previous choices (as in backtracking)
Keeping track of choices yet to be made (as in creating a maze)
Undo sequence in a text editor.
Auxiliary data structure for algorithms
Component of other data structures
Activation record (AR) (Stack frame): Keeping track of local variables at run time
Array
Drawbacks:
Fixed length
Insert and delete lead to move other elements around