Please enable JavaScript.
Coggle requires JavaScript to display documents.
Data Structures andAlgorithms ----------------- Data Camp --------------- …
Data Structures and
Algorithms
----------------- Data Camp ---------------
What is an
algorithm
?
Set of instructions that solve a problem.
STEPS:
Design
Code
What are
data structures
?
Structure of values that hold
and manipulate data when we execute an algorithm.
Advanced
linked lists
Parts
Data and pointer
The last link points to None
Data doesn't need to be stored in
contiguous blocks of memory.
Data can be located in any available memory address.
LINKS
Two links in either direction,
double linked list.
One link for each node,
singly linked list.
Real uses
stacks
queues
graphs
Access information by navigating backward and forward.
web browser
music playlist
Algorithms
stack
queues
Queues, Hash Tables, Trees, Graphs and Recursion
Queues
Real world
printer tasks in a printer
Tickets for a concert
Taxi services
Implementation
Implementation
Hash Tables
(key, value)
Almost every programming language has a built-in hash table.
hashes
hash maps
dictionaries
associative arrays
diccionaries (Python)
EXAMPLE
Name of the dishes are the keys and the prices are the values.
Nested dictionary
my_menu (bigger dictionary), sushi, paella (in dictionaries).
Structure
positions are slot or bucket:
mapping and key where the
value will be stored
Python handles all these problems for us.
It takes O(1)
Methods
Iterate over the whole dictionary
Iterate over the key and value
Trees
and graphs
TREES
Terminology
Height
Implementation
can build but not really professional...
TREES ARE A TYPE OF GRAPH
Graph vs Trees
Real Uses
Hierarchical relationships:
File systems of a computer.
Structure of an HTML document.
Chess .- possible moves of the rival.
Searching and sorting algorithms
GRAPHS
People and friendship between people.
Data structure formed by a set of nodes (vertices), connected by links (edges)
TYPES
Directed graph
Specific direction
David follows Martin, but Martin doesn't follow David.
Undirected graph
Weighed graphs
The weighed graph represent the distance of different cities.
Real Uses
Social Networks
friendship
follows
likes
Location and Distances
optimize routes
Graph databases
Searching and sorting algorithms.
Implementation
Build a graph:
Recursion
Function calling itself.
When we use loops, we can use recursion.
Can solve problems that seem very complex at first.
Example with no recursion:
Identify the best case:
Ensures that our algorithm doesn't execute forever.
Factorial base case --> n = 1 or n = 0
Computer uses a stack to keep track of the functions.
Call stack
REAL USES
Dynamic Programming
Optimization Technique
Reduce the complexity of recursive algorithms
Used for any problem that can be divided into smaller subproblems.
subproblems overlap
Memoization technique.
Searching Algorithms
Linear search
Complexity of O(n)
Analysis of complexity
Binary search
Complexity O(log n)
BST
search
return False
insert
delete
one child
delete it.
connect the child with node's parent.
no children
delete it
two children
Replace it with its successor.
(node with the least value greater
than the value of the node.)
find the successor
(visit the right child, keep visiting the
left nodes until the end.)
if the successor has a right child:
this child becomes the left child of the
successor's parent.
USES
order list efficiently
Much faster at searching than arrays and linked lists.
Much faster at inserting and deleting than arrays.
Implement more advanced data structure.
Depth First Search
Traversal
Pre-order
Complexity O(n)
create copies of a tree
get prefix expressions
Post-order
Complexity O(n)
deleting binary trees.
get postfix expressions.
In-order
Complexity O(n)
nodes values in ascending order.
https://coggle.it/diagram/Z-1k3UiC-iVUCEqt/t/arboles-avl-y-rojinegro-data-structures
Basic Operations
Graphs
It needs to keep track of visited vertices.
VS
Breadth First Search
Starts from the root and visits
every node of every level.
Not for graphs
graphs
the visited nodes keeps track of all the vertices we visit.
Sorting Algorithms
https://coggle.it/diagram/aAEwrw75rfBG-sSP/t/-
Stack
pop
