2436 Data Structures and Algorithms
Ashley Andruss
Created on July 31, 2024
Over 30 million people build interactive content in Genially.
Check out what others have designed:
BEYONCÉ
Horizontal infographics
ALEX MORGAN
Horizontal infographics
ZODIAC SUN SIGNS AND WHAT THEY MEAN
Horizontal infographics
GOOGLE - SEARCH TIPS
Horizontal infographics
OSCAR WILDE
Horizontal infographics
NORMANDY 1944
Horizontal infographics
VIOLA DAVIS
Horizontal infographics
Transcript
cmap1:concept
cmap1:concept
cmap1:concept
cmap1:concept
cmap1:concept
cmap1:concept
cmap1:concept
cmap1:concept
cmap1:concept
cmap1:concept
cmap2: implementation
cmap2: implementation
cmap2: implementation
cmap2: implementation
cmap2: implementation
cmap2: implementation
cmap2: implementation
cmap2: implementation
cmap2: implementation
cmap2: implementation
dynamic arrays
HEAPS
big o notation
STACKS
HASHING
TREES
linked lists
GRAPHS
Recursion
QUEUES
Data Structures and Algorithms
encompasses
encompasses
Implementation: Dynamic Arrays
Concept: Dynamic Arrays
Implementation: Queues
Concept: Queues
Implementation: Recursion
Concept: Recursion
Implementation: Linked List
Concept: Linked List
Implementation: Big O Notation
Concept: Big O Notation
Implementation: Stacks
Concept: Stacks
Implementation: Graphs
Concept: Graphs
Implementation: Trees
Concept: Trees
Implementation: Heaps
Concept: Heaps
Implementation: Hashing
Concept: Hashing
What is a concept map?
Nodes correspond to the concepts or important terms related to your studies of a topic. For example, the concept "water" can be defined by other concepts, such as liquid, solid, and gas. The relationship of each concept to other concepts determines its meaning. Thus, a concept map is a set of relationships among other concepts. Labeled links identify the type of relationship. Therefore, the line between a pair of concepts denotes a relationship, and the label on the line tells how the two concepts are related. For example, in a concept map of seasons, the relationship between the amount of sunlight and temperature variations is labeled as "cause" – in other words it is an action relationship between antecedent and consequent. In a concept map of dairy policies, the relationship between "dairy policy" and "federal milk marketing order" is labeled as "includes" because it represents an inclusion relationship between superset and subset.
https://pennstatelearning.psu.edu/istudy_tutorials/conceptmaps/conceptmaps_print.html
why do amap first?
computer science
- Help me to visualize what I already know about a topic. They guide my study and research about that topic and can enhance meaningful and deeper learning.
- To construct a concept map, you need to determine important concepts and the relationships between these concepts. By doing that, you explore your understanding of the topic. In other words, you examine and reflect on what you know about the topic.
- This fundamental understanding enhances the ability to build optimized and accurate code, leading to a comprehensive program to solve complex problems.
https://pennstatelearning.psu.edu/istudy_tutorials/conceptmaps/conceptmaps_print.html | https://gogeometry.com/mindmap/academic_computer_science.html
go to implementation
Main menu
cmap 1: concept
Dynamic Arrays
asks the question of
how
leading to the
that have key characteristics of
a
when
including a(n)
explaining
contiguous blocks ofmemory
with
accessedusing indices
including
such as
dynamic resizing
including
where
for
can this be used in
such as
such as
definition
advantages
it is used in
problems solved
having a(n)
applications
operations
can this be applied with the
process
disadvantages
such as
scenarios
structure
such as
why
step 1
step 2
dynamic data structures
collection of elements
efficient random accessO(1)
unknown dataset size
underlying fixed-sizearray
what
capacity variable
frequent insertionor deletion
totalallocated space
size variable
for numberof elements
staticarray limitations
resizing operations new array
linked lists
selection sort
binarysearch
linear search
static array fixed size
quick selection
simplified operations
queues
stacks
hash tables
bucket sort
quicksort
mergesort
heapsort
dynamic graphs
searchalgorithms
execute operations steps
deletion
sortingalgorithms
initialization
insertion
resize
access
search
insertionsort
bubble sort
cmap 2: implementation
Dynamic Arrays
has operations such as
encompassing a
following
Main menu
to decide
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
such as
with step 1
canhave a
with step 2
with step 3
resize
with step 4
with step 5
step 1
search
step 2
step 3
step 4
step 1
step 2
step 3
step 4
step 5
step 1
access
step 2
step 3
Shift elementsfrom specific index to left
Check Array Midpoint Valuesmid; mid-1; mid+1
Copy Elementsold array to new array
Format Each ElementE.g., comma-separated values
Shift elementsfrom specific index to right
question
question
question
question
question
Update sizedecrease by 1
End Searchreturn -1 if not found
Deallocate Memoryused by old array
End PrintInclude new line or termination
End Searchreturn -1 if not found
Update ReferenceOriginal array referance point to new array
Print ElementsOutput into specified format
Repeat Until Foundlow; high; low > high
Insert elementat specific index
Increment sizeof array by 1
DeletionLocation
AccessSteps
ResizeSteps
PrintSteps
SearchLocation
Insertion Location
question
process
process
process
process
process
process
deletion
insertion
Insert at Beginning?
Linear Search?
Validate Index0 <= index < size
Delete at Beginning?
Delete at End?
Insert at End?
Insert at Specific Index?
Access Elementreturn index
Binary Search?
Delete at Specific Index?
Is There Capacity?
Where to Delete?
Is the Index In Bounds?
Print entire array or up to index?
What is the New Capacity?
Where to Search?
Where to Insert?
call recursive function
define the array
define recursive call
define base case
create recursive case
recursive process
Check capacity & if array needs resizing
Start from 1st ElementSet index pointer to 0
Check if array is empty
Check capacity & if array needs resizing
Check if array is empty
Check capacity & if array needs space
Check if array is empty
Initialize Pointers0 to size - 1
Start From 1st Elementindex pointer to 0
Determine New CapacityEx: new_cap = cap *2
Increment size of array by 1
Increment size of array by 1
encompassing a
Insert elementindex 0
Decrement size of array
Check Each Element Match? Return index
Iterate Through Searchmid = (low+high)/2
Allocate New Arraynew_cap
Iterate Through Arrayloop elements up to size
Validate indexIs within bounds0 to size - 1
Validate indexIs specific index within 0 to size (out of bounds)
Decrement size of array
Insert new elementat size index
Shift elements to the leftindex 1 to size - 1
Iterate Through ArrayCompare target value; increment
Shift elements to the rightsize - 1 to 0
encompassing a
encompassing a
encompassing a
following
to decide
such as
Resize Array Now or Until Necessary?
How to Shift Elements?
What is the Current Capacity?
How should the output be formatted?
What Index Do You Want?
Which Element to Search For?
Which Element to Delete?
step 1
step 2
step 3
step 1
step 2
step 3
step 4
step 1
step 2
following
to decide
such as
step 1
step 2
step 3
step 1
step 2
step 3
step 4
step 4
step 5
following
such as
following
such as
following
such as
step 1
step 2
step 1
step 2
step 3
step 4
step 5
step 1
step 3
step 4
step 5
step 2
go to implementation
Main menu
cmap 1: concept
Recursion
asks the question of
leading to the
to solve
a
how
including a
explaining
such as
including
when
including
for
can this be used in
such as
smaller instances of the same problem
such as
it is used in
where
having a(n)
can this be applied with the
such as
such as
step 1
step 2
definition
advantages
problems solved
applications
operations
process
disadvantages
scenarios
structure
why
tree traversals
graphs
function that calls itself
fit for hierarchial data
simplifies complex problems
nested structures
basecase
what
linked lists
recursivecase
repetitive subtasks
tree traversal & graphs
factorial & gcd
memory intensive
stack overflow risk
fibonacci series
towers of hanoi
divide and conquer
pre-order
binary search
depth-first search
post-order
in-order
quicksort
mergesort
heapsort
searchalgorithms
recursive case (calls function)
sortingalgorithms
base case (stop recursion)
function calls itself
cmap 2: implementation
Recursion
components such as
following
as
Main menu
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
as
recursive case
question
question
Define the simplest problem (e.g., n== 0 in factorial)
Call function with smaller input
Identify Recursive Case
Ensure Termination (base case)
Implement FunctionCall
step 1
process
process
step 2
step 4
step 3
base case
steps
Identify Base Case
encompassing a
following
such as
What step reduces the problem size?
When should recursion stop?
following
such as
as
as
go to implementation
Main menu
how
cmap 1: concept
Linked List
asks the question of
when
leading to the
a
including a(n)
where
explaining
with
including
definition
USE CASES
lIMITATIONS
applications
process
scenarios
types
structure
why
Create a new node
Find the node to be removed.
Update the head to be the new node
Free the memory of the removed node
Point the new node's next reference to the current head
Update the previous node's reference to skip the removed node
Implementing other data structures like stacks, queues, and graphs
for
A data structure consisting of nodes.
Efficient insertions/deletionsand dynamic memory allocation
can this be used in
When the number of elements is unknown or changes frequently.
When random access is not needed
Used when frequent insertions/deletions are needed
Singly, Doubly, Circular Linked Lists.
Nodes contain data and references to the next node.
what
it is used in
having a(n)
Slower access time compared to arrays
can this be applied with the
Memory management in operating systemsnavigation
Removing elements
Adding elements
Applications that require dynamic memory allocation, such as text editors and databases.
Create an empty list with the head pointing to null.
initialization
step 1
step 2
has
step 3
cmap 2: implementation
Linked List
has operations such as
encompassing a
following
Main menu
to decide
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
such as
Traversal
access
question
question
question
question
DeletionLocation
AccessSteps
PrintSteps
Action
Insertion Location
question
process
process
process
process
process
deletion
insertion
Insert at Beginning?
Traverse
Start at head
Delete at Beginning?
Delete at End?
Insert at End?
Insert at Specific Index?
Move to next node using next
Move to next node using next
Delete at Specific Index?
Is There Capacity?
Where to Delete?
Where to Insert?
Reassigning pointers to insert node
Assigning new node as tail
Traversing to the end
Remove tail node
Print value
Move to next node using next
Find the correct position
Reassigning head to next node
Find the node to delete
Start from head
Start from head
Reassigning head to next node
Assigning new node as head
Find the correct position
Check if the node is the head
Check if the list is empty
encompassing a
encompassing a
encompassing a
following
to decide
such as
How to Shift Elements?
How should the output be formatted?
What position Do You Want?
How to traverse?
Which Element to Delete?
following
to decide
such as
following
such as
following
such as
step 1
step 2
go to implementation
Main menu
cmap 1: concept
Big O Notation
asks the question of
when
leading to the
a
including a(n)
HOW
where
explaining
with
including
definition
Use cases
liMITATIONS
applications
applications
scenarios
structure
Type
why
Measures algorithm efficiency in time/space
hELPS IN ANALYZING ALGORITHM PERFORMANCE
can this be used in
O(1), o(n), o(n^2)...
FUNCTIONS DESCRIBE WORST-CASE SCENARIO growth.
what
breadth-first search
Operating Systems:
Game Development:
QUICK SORT
MERGE SORT
SORTING ALGORITHMS
graph algorithms
O(n^2): Bubble sort, Selection sort
0(N):LINEAR SEARCH
O(n log n): Merge sort, Quick sort (average case)
Big O notation doesn't reflect constant factors.
Hash Table: Average O(1) lookup, but worst-case O(n) due to collisions.
Quick Sort – O(n log n) on average but O(n^2) in the worst case with poor pivot selection.
bubble sort
o(log n):binary search
sEARCH ALGORITHMS
Algorithms like A* for pathfinding are chosen based on Big O to ensure smooth performance even with complex environments.
0(1) :HASH TABLE OPERATIONS
Scheduling algorithms are evaluated based on Big O complexity.
BINARY SEARCH
used in evaluating algorithm scalablity
it is used in
having a(n)
dOESNT ACCOUNT FOR CONSTANTS AND LOWER ORDER TERMS
including a(n)
having a(n)
cmap 2: implementation
Big O Notation
has operations such as
encompassing a
following
Main menu
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing
such as
Examples
Scenarios
Optimizing Space Usage
Graph
Worst case
Memory allocation
Recursive algorithms
Identifying Recurrence Relations
Solving Recurrence Relations
Loops
Recursion
Space
Time
Single
Sorting
Average Case
Consecutive
Nested
Recursion trees
Examples of recurrence relations
Adding time complexities of consecutive statements
Master theorem
Min time required under optimal conditions
Quick sort with random pivots
Max time required for worst conditons
Bubble: O(n^2)
BFS: O(V+E)
Linear: O(n)
Dijkstra's: O(V^2)
Merge: O(nlogn)
Heap Sort:
Quick Sort:
Binary: O(logn)
Expected time r for random inputs
Tail Recursion: Optimized by some languages to use constant space.
Linear search if target is not present
In-place Sorting Algorithms: Heap sort (O(1) space complexity).
Techniques to reduce space complexity
Understanding memory usage in functions
Counting space complexity in recursion
Counting variable and data structures
Stack space in recursion
What is recurrence relations?
O(log n) recursion: Binary search in a recursive form.
Tail Recursion: Mention if a language optimizes tail-recursive functions to use O(1) space.
O(n) space for recursion due to stack frames (for algorithms like depth-first search).
O(n) recursion: Linear recursion like factorial or Fibonacci (without memoization).
Time complexity in sequential operations
Counting iterations in nested loops
Nested loops: O(n^2) (e.g., comparing all pairs in an array)
Single loop: O(n) (e.g., iterating through an array)
Time complexity of single loops
Time complexity of nested loops
Counting iterations in single loops
encompassing a
Average Case: For quick sort, it might help to mention that it is O(n log n) in average cases.
Best Case: Example of bubble sort’s best case (already sorted array, O(n)).
Linear search if the first element is target
Worst Case: Highlight how quick sort degrades to O(n^2) with poor pivot selection.
Best case
Search
encompassing a
go to implementation
cmap 1: concept
Stacks
asks the question of
leading to the
Main menu
that utilizes the
a
including a
how
explaining
with
including
for
can this be used in
it is used in
when
having a(n)
can this be applied with the
such as
step 1
last in first out (LifO) Principle
step 2
such as
step 3
where
definition
Problems solved
advantages
applications
operations
process
disadvantages
scenarios
structure
why
EXPRESSION EVALUATION
UNDO MECHANISMS
syntax parsing
MEMORY MANAGMENT
Data structure
back tracking & Depth-first search
fast insertion/deletion
expression evaluation
order preservation
fUNCTION CALL
topelement
what
linked nodes/array
undo operation(last element added is needed first)
potential overflow if too many pushes
siZE LIMITATION
bROWSER hISTORY
execute operations steps
manage stack pointer/size
isEmpty
function cALL MANAGEMENT
initialize empty stack
POP
push
PEEK (Top)
cmap 2: implementation
Stacks
has operations such as
encompassing a
following
Main menu
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
such as
pEAK
iSEMPTY
Update head to new node
update head to next node
delete old head node
Create a new node
Check if stack is empty
Check if stack is empty
Check if stack is empty
store data from head
Return data from head node
Point node's next to current head
Check if head is null
Check if head is null
Check if head is null
Assign data to node
Array-based
Array-based
Array-based
Array-based
Linked list-BASED
Linked list-BASED
Linked list-BASED
Linked list-BASED
pOP
PUSH
Decrement top
Retrieve element at top
Return element at top
Increment top
Check if top is -1
Check if top is -1
Check if top is -1
Check if stack is empty
Check if stack is empty
Check if stack is empty
Add element at top positions
Compare top with max - 1
Check if stack is full
encompassing a
encompassing a
following
such as
following
such as
following
such as
go to implementation
Main menu
how
cmap 1: concept
Queues
asks the question of
when
leading to the
that have key characteristics of
a
First In,First Out (FIFO) principle
including a(n)
where
explaining
with
definition
Use cases
applications
operations
process
Limitations
scenarios
structure
Types
including
why
Operating systems
Queues manage tasks in CPU scheduling and handling print jobs.
Where customers are served in the order they arrive (like aline at the bank).
To manage requests, where the first request made should be the first oneserved.
for
Linear data structure
scheduling
Handling async data
Buffering
can this be used in
unknown dataset size
Linear collection
what
not sutiable Priority order is needed
elements added at one end
frequent insertionor deletion
Priority
Double ended
Circular
Elements removed at other end
Simple
it is used in
having a(n)
Not suitable for random access
can this be applied with the
such as
WEB SERVERS
execute operations steps
DEQUEUE
CUSTOMER SERVICE SYSTEMS
initialization
ENQUEUE
ISEMPTY
FRONT
step 1
step 2
including a(n)
cmap 2: implementation
Queues
has operations such as
encompassing a
following
Main menu
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
such as
peek
increment rear in circular
print front in circular
increment front in circular
ensures the rear points to the front
ensures the rear points to the front
ensures the rear points to the front
insert based on given priority
print based on given priority
remove based on given priority
determine priority based on context
determine priority based on context
determine priority based on context
Deque
Deque
Deque
sIMPLE
sIMPLE
sIMPLE
pRIORITY
pRIORITY
pRIORITY
Circular
Circular
Circular
dequeue
ENQUEUE
increment the front poitner
increment the rear pointer
Adding at rear
remove at rear
print rear index
remove an element in the front
Adds an element to the rear
Adding at front
remove at front
print front index
print front index
where to remove element?
Where to add a new element?
encompassing a
following
such as
following
such as
following
such as
following
such as
following
such as
go to implementation
Main menu
how
cmap 1: concept
Hashing
asks the question of
when
leading to the
a
including a(n)
where
explaining
with
including
definition
advantages
problems solved
applications
operations
process
disadvantages
scenarios
structure
including
why
Database indexing
caches
capacity
LOAD FACTOR
dynamic data structures
for
Hash function
Dynamic Resizing: Hash table can grow/shrink based on load factor.
Fast Lookups: O(1) on average for insertion, deletion, search
can this be used in
unknown dataset size
Hash table
such as
what
BUCKET
frequent insertionor deletion
it is used in
having a(n)
Collisions Solved: Collisions are handled using chaining or open addressing.
Efficient Retrieval: Overcomes the slow search time of linear searches.
Resizing Overhead: Rehashing all elements during resizing is time-consuming.
Collisions: Keys may hash to the same index, requiring extra work.
can this be applied with the
high-speed lookups
Total number of slots in the hash table.
hash maps
Ratio of filled slots to total capacity; used to decide resizing.
Slot in the table to hold elements.
Array-like structure where the hash function directs elements.
Maps a key to an index in the hash table.
such as
hash tables
hash sets
execute operations steps
deletion
initialization
Collision Handling
insertion
resize
access
search
step 1
step 2
cmap 2: implementation
has operations such as
encompassing a
following
Main menu
to decide
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
such as
resize
step 1
search
step 2
step 3
step 4
access
Rehash all elements
Handle chaining if needed
question
question
question
question
question
Return element or indicate not found
Free old memory
Format output
DeletionLocation
AccessSteps
ResizeSteps
PrintSteps
SearchLocation
Insertion Location
question
process
process
process
process
process
process
deletion
insertion
INSERTION
SEARCH
Validate index using hash function
DELETION
Return element at index, handle collision if needed
Is There Capacity?
Where to Delete?
Is the Index In Bounds?
Print entire array or up to index?
What is the New Capacity?
Where to Search?
Where to Insert?
Compute index using hash function
Compute index using hash function
Compute index using hash function
Iterate over all buckets
Determine new capacity based on load factor
Remove element or mark as deleted
Adjust load factor and resize if needed
encompassing a
Insert if free, else handle collision
Handle collision if needed
Handle collision if needed (chaining/open addressing)
Allocate new table
Print elements in each bucket
Locate element at index
Check bucket for element
Check if index is free
encompassing a
encompassing a
encompassing a
following
to decide
such as
Resize Array Now or Until Necessary?
How to Shift Elements?
What is the Current Capacity?
How should the output be formatted?
What Index Do You Want?
Which Element to Search For?
Which Element to Delete?
step 1
step 2
step 3
following
to decide
Adjust load factor and resize if necessary
such as
step 1
step 2
step 3
step 4
following
such as
following
such as
following
such as
step 1
step 2
step 1
step 2
step 3
step 4
step 1
step 3
step 4
step 2
step 4
step 5
Hashing
go to implementation
Main menu
how
cmap 1: concept
Heaps
asks the question of
when
leading to the
that have key characteristics of
The parent node is always greater than orequal to its children.
The parent node is always less than or equalto its children.
a
Max heap
including a(n)
Min Heap
where
explaining
with
definition
USE CASES
applications
operations
process
LIMITATIONS
scenarios
structure
Types
including
why
dynamic data structures
for
special type of binary tree
Priority Queues
HEAP SORT
can this be used in
unknown dataset size
Max heap
Binary tree
min heap
such as
what
graph algoS
Parent node>child node
frequent insertionor deletion
such as
it is used in
having a(n)
Fixed Structure
High Memory Overhead
Not Ideal for Searching Arbitrary Elements
can this be applied with the
linked lists
selection sort
binarch search
linear search
such as
the largest or the smallest is at the root
such as
quick selection
queues
stacks
hash tables
bucket sort
quicksort
mergesort
heapsort
dynamic graphs
searchalgorithms
execute operations steps
deletion
sortingalgorithms
initialization
insertion
resize
access
search
insertionsort
bubble sort
step 1
step 2
including a(n)
cmap 2: implementation
Heaps
has operations such as
encompassing a
following
Main menu
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
resize
Peak
Heapify
process
process
process
process
process
deletion
insertion
encompassing a
encompassing a
encompassing a
maintains a complete binary tree
apply the heap property recursively
(for min-heap, this is the smallest; for max-heap, it’s the largest)
Remove the last element
Replace the root with the last element in the heap
smallest in min-heap, largest in max-heap
Access the root element
Start from the last non-leaf node
Add the new element at the end of the heap
Remove the root element
Swap as needed until the heap property is restored (min-heap or max-heap)
by swapping with its smallest (min-heap) or largest (max-heap) child until correct.
Efficient way to build a heap from an unsorted array (O(n) complexity).
Efficiently returns the min/max value while maintaining the heap structure.
No modification to the heap, only read access.
Bubble down the replaced root to restore the heap property
Constant time (O(1)) since the root element is always at the top
Replace it with the last element in the heap, then bubble down as in delete
Move elements down the tree until the subtree satisfies the heap property.
Bubble up the element by comparing it to its parent
following
following
following
following
go to implementation
Main menu
cmap 1: concept
Trees
asks the question of
leading to the
a
including a(n)
explaining
how
with
including
including
when
for
can this be used in
it is used in
having a(n)
can this be applied with the
where
such as
step 1
step 2
definition
advantages
problems solved
applications
operations
process
disadvantages
scenarios
structure
why
binary search trees (bsts)
hierarchical, non-linear data structure
natural hierarchy
efficient searching, insertion, deletion
efficiently searching or sorting large datasets
decision making
root
what
edge
branch
storing hierarchical relationships (e.g., xml/html)
leaves
nodes with or without children
organizing hierarchial data (e.g., file systems)
complex balancing
potentialskew
avltrees
execute operations steps
deletion
heaps
b-trees
maintain parent-child relationship
insertion
search
traversal
cmap 2: implementation
Trees
has operations such as
encompassing a
following
Main menu
as
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
such as
with step 1
canhave a
with step 2
with step 3
with step 4
with step 5
search
if smaller
if larger
traversal
question
question
question
STEP 2
STEP 2
STEP 3
STEP 3
STEP 1
STEP 1
question
process
process
process
process
deletion
insertion
Find node to delete
Start atRoot
Update tree's balance (if required, like in AVL)
Repeat Step 2 until an empty spot is found
Update tree's balance (if required, like in AVL)
Insert new node at the empty position
Compare new node's value with current node
Check the node's children
STEP 2
STEP 3
STEP 1
STEP 4
STEP 5
How to remove while maintaining structure?
Where to Insert the New Node?
STEP 2
combine results from subtrees
STEP 3
define tree node structure
Choose Traversal Type
STEP 1
recurse on child nodes
handle base case (leaf node)
create recursive traversal methods
recursive process
Recursively apply chosen order
Process each node during visit
Start at Root
Remove Node
Move Left
Start atRoot
encompassing a
Replace Node's Value with Successor's Value
Replace Node's Value with Successor's Value
Delete the In-Order Successor
Find In-Order Successor (smallest node in right subtree)
STEP 4
In what order to visit nodes?
Move Right
encompassing a
Continue until the value is found or you reach a null/empty node.
If node is not found, return false or doesn't exist.
Compare target value with current node
as
as
as
STEP 4
as
How do we find a specific node?
following
as
such as
if no children
as
as
Node is Found
In-Order
Pre-Order
Move Left
Post-Order
Move Right
following
as
such as
if values match
as
as
as
following
as
such as
as
as
as
if one child
if two children
To Balance: After an insert or delete, calculate Balance Factor = Height of left subtree - Height of right subtree. If the balance factor is out of range (e.g., >1 or <-1 for AVL): Perform rotation(s): Single Rotation: Left or Right. Double Rotation: Left-Right or Right-Left. Update the heights and continue balancing if necessary.
if target is smaller
if target is larger
Left, Root, Right
Root, Left, Right
Left, Right, Root
go to implementation
Main menu
how
cmap 1: concept
Graphs
asks the question of
when
leading to the
including a(n)
where
explaining
with
including
advantages
problems solved
applications
operations
process
disadvantages
scenarios
structure
including
why
Computer Networks
for
VERTICES
Models Real-World Relationships
Efficient for Pathfinding
can this be used in
Modeling Networks
Edges
what
unweighted graph
Directed Graph
Pathfinding
Dependency Tracking
Adjacency List
weighted graph
Undirected Graph
Adjacency Matrix
it is used in
having a(n)
Dependency Resolution
Optimized Network Routing
resizing operations new array
Modeling Connections
can this be applied with the
such as
Social Networks
CYCLE DETECTION
Adjacency Matrix
Task Scheduling
Recommendation Systems
graph representation
Adjacency List
Traversal (DFS/BFS)
Minimum Spanning Tree (Kruskal's or Prim's)
Shortest Path (Dijkstra’s Algorithm)
step 1
step 2
cmap 2: implementation
Graphs
has operations such as
encompassing a
following
Main menu
to decide
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
such as
Graph Representation
Topological Sorting (for DAG)
step 1
Minimum Spanning Tree (Kruskal's or Prim's)
step 2
step 3
step 4
step 1
step 2
step 3
step 4
step 5
Cycle Detection
Mark the current vertex as visited
Mark the vertex as visited
Yes: Add the vertex to the stack (post-order) No: Continue DFS for adjacent vertices
Repeat for all vertices
Dequeue vertex and visit all adjacent vertices
question
question
question
question
question
Move to the unvisited node with the smallest distance
Repeat until all nodes are visited
Repeat until all vertices are connected (V-1 edges)
Return the reversed stack as the topological sort
For each edge (u, v):Is there an edge between u and v?Yes: Add vertex v to the list of vertex u (and vice versa for undirected)
Once all vertices are visited, reverse the post-order stack
Create a list for each vertex
Repeat for all vertices
Repeat until all vertices are included in the MST
Enqueue all adjacent unvisited vertices
Continue until all vertices are visited
Step 3: Set source vertex as current
Continue until queue is empty
Step 2: Mark all nodes as unvisited
Step 1: Initialize distances (source = 0, others = infinity)
AccessSteps
Step 1: Perform DFS from each unvisited vertexStep 2: Add vertices to the sort order after visiting all adjacent verticesStep 3: Reverse the post-order traversal to get the topological sort
Step 1: Choose adjacency matrix or adjacency listStep 2: Implement the chosen representation
Step 1: Choose the algorithm (Kruskal's or Prim's)Step 2: Add edges or vertices to the MST based on the algorithm
Step 1: Select starting vertexStep 2: Choose DFS or BFS
question
process
process
process
process
process
process
Shortest Path (Dijkstra’s Algorithm)
traversal (dfs/bfs)
DFS Process
Kruskal's Algorithm
Step 1: Validate the vertex index (if necessary)
Step 2: Perform DFS or BFS based on the graph type
Prim's Algorithm
Dijkstra’s Process
Which method to use :DFS or BFS
What is the source vertex?
Is the graph directed or undirected?
Which representation to use: adjacency matrix or adjacency list?
Adjacency List
Adjacency Matrix
What is the current capacity for sorting?
Which algorithm: Kruskal's or Prim's?
Where to start traversal?
Start at root vertex
Sort edges by weight
Start at root vertex
Calculate tentative distances to neighboring nodes
Start at any vertex
Create a 2D array (V x V)
Start DFS from any unvisited vertex
Backtrack if no adjacent vertex exists
encompassing a
Recursively visit unvisited adjacent vertices
Check for cycle
Add the smallest edge that connects a new vertex
For each vertex:Have all adjacent vertices been visited?
For each edge (u, v):Is there an edge between u and v?Yes: Mark matrix at [u][v] (and [v][u] for undirected)No: Leave matrix entry as 0
Update shortest distance for each neighbor
Enqueue and mark root as visited
Add smallest edge to MST
Mark vertex as visited
encompassing a
encompassing a
encompassing a
following
to decide
such as
Which nodes require shortest paths?
Is the graph a DAG?
How should the output be formatted?
What vertex or index to check for a cycle?
Where to search for the MST?
step 1
step 2
step 3
step 4
following
to decide
such as
step 1
step 2
step 3
step 1
step 2
step 3
step 4
step 4
following
such as
following
such as
following
such as
step 1
step 2
step 1
step 2
step 3
step 4
step 5
step 1
step 3
step 1
step 2
step 2
BFS Process
step 5
step 5
step 3
You did it! I'm proud of you. :)
go to implementation
Main menu
how
cmap 1: concept
Dynamic Arrays
asks the question of
when
leading to the
that have key characteristics of
contiguous blocks ofmemory
a
accessedusing indices
including a(n)
dynamic resizing
where
explaining
with
including
definition
advantages
problems solved
such as
applications
operations
process
disadvantages
scenarios
structure
including
why
dynamic data structures
for
collection of elements
efficient random accessO(1)
can this be used in
unknown dataset size
underlying fixed-sizearray
such as
what
capacity variable
frequent insertionor deletion
totalallocated space
such as
size variable
for numberof elements
it is used in
having a(n)
staticarray limitations
resizing operations new array
can this be applied with the
linked lists
selection sort
binarch search
linear search
such as
static array fixed size
such as
quick selection
simplified operations
queues
stacks
hash tables
bucket sort
quicksort
mergesort
heapsort
dynamic graphs
searchalgorithms
execute operations steps
deletion
sortingalgorithms
initialization
insertion
resize
access
search
insertionsort
bubble sort
step 1
step 2
cmap 2: implementation
Dynamic Arrays
has operations such as
encompassing a
following
Main menu
to decide
An awesome title
Describe the problem you’re going to resolve and, above all, the reason why your idea is interesting
INTRODUCTION HERE
encompassing a
such as
with step 1
canhave a
with step 2
with step 3
resize
with step 4
with step 5
step 1
search
step 2
step 3
step 4
step 1
step 2
step 3
step 4
step 5
step 1
access
step 2
step 3
Shift elementsfrom specific index to left
Check Array Midpoint Valuesmid; mid-1; mid+1
Copy Elementsold array to new array
Format Each ElementE.g., comma-separated values
Shift elementsfrom specific index to right
question
question
question
question
question
Update sizedecrease by 1
End Searchreturn -1 if not found
Deallocate Memoryused by old array
End PrintInclude new line or termination
End Searchreturn -1 if not found
Update ReferenceOriginal array referance point to new array
Print ElementsOutput into specified format
Repeat Until Foundlow; high; low > high
Insert elementat specific index
Increment sizeof array by 1
DeletionLocation
AccessSteps
ResizeSteps
PrintSteps
SearchLocation
Insertion Location
question
process
process
process
process
process
process
deletion
insertion
Insert at Beginning?
Linear Search?
Validate Index0 <= index < size
Delete at Beginning?
Delete at End?
Insert at End?
Insert at Specific Index?
Access Elementreturn index
Binary Search?
Delete at Specific Index?
Is There Capacity?
Where to Delete?
Is the Index In Bounds?
Print entire array or up to index?
What is the New Capacity?
Where to Search?
Where to Insert?
call recursive function
define the array
define recursive call
define base case
create recursive case
recursive process
Check capacity & if array needs resizing
Start from 1st ElementSet index pointer to 0
Check if array is empty
Check capacity & if array needs resizing
Check if array is empty
Check capacity & if array needs space
Check if array is empty
Initialize Pointers0 to size - 1
Start From 1st Elementindex pointer to 0
Determine New CapacityEx: new_cap = cap *2
Increment size of array by 1
Increment size of array by 1
encompassing a
Insert elementindex 0
Decrement size of array
Check Each Element Match? Return index
Iterate Through Searchmid = (low+high)/2
Allocate New Arraynew_cap
Iterate Through Arrayloop elements up to size
Validate indexIs within bounds0 to size - 1
Validate indexIs specific index within 0 to size (out of bounds)
Decrement size of array
Insert new elementat size index
Shift elements to the leftindex 1 to size - 1
Iterate Through ArrayCompare target value; increment
Shift elements to the rightsize - 1 to 0
encompassing a
encompassing a
encompassing a
following
to decide
such as
Resize Array Now or Until Necessary?
How to Shift Elements?
What is the Current Capacity?
How should the output be formatted?
What Index Do You Want?
Which Element to Search For?
Which Element to Delete?
step 1
step 2
step 3
step 1
step 2
step 3
step 4
step 1
step 2
following
to decide
such as
step 1
step 2
step 3
step 1
step 2
step 3
step 4
step 4
step 5
following
such as
following
such as
following
such as
step 1
step 2
step 1
step 2
step 3
step 4
step 5
step 1
step 3
step 4
step 5
step 2
Main menu
How does a dynamic array differ from a static array?
What is a dynamic array?
Why is resizing an important feature of dynamic arrays?
Dynamic Array
Contextualize your topic with a subtitle
What (Loops and Recursion):Loops:Single Loop: Counts the iterations in a single loop (O(n)).Nested Loop: Counts the iterations in nested loops, where each loop depends on the other (O(n²)).Consecutive Loops: Adds the time complexity of consecutive loops (O(n) + O(m)).Recursion:Identifying Recurrence Relations: Analyzes how recursive calls are made and how they affect time complexity.Solving Recurrence Relations: Uses the Master Theorem or recursion trees to solve and derive time complexity from recurrence relations.2. Why (Understanding Time Complexity):Single and Nested Loops: Helps in determining how algorithms grow with input size.Recursion: Essential to understand how dividing problems into smaller subproblems affects time.3. When (Use Cases):Loops: Used when counting iterations in algorithms like linear search or selection sort.Recursion: Useful in recursive algorithms such as divide-and-conquer strategies like Merge Sort or calculating Fibonacci numbers.4. Where (Common Use Cases):Single Loop: Linear search or basic iteration through data.Nested Loop: Sorting algorithms like Bubble Sort that involve comparing elements in pairs.Recursion: Algorithms like Merge Sort and algorithms involving trees or graphs.
- Explain the step-by-step processes involved.
how?
20%
80%
- Provide a definition and key characteristics. Syntax: - Define type int, char, float- Example: int arr[3]Initialization:- int arr[3] = {1, 2, 3} - Explain the fundamental principles. - Discuss the basic structure or components. - Include any related terminology and concepts.
what?
Definition:Example: "Big O notation is a mathematical notation that describes the upper bound of an algorithm's time complexity, providing a worst-case scenario of its performance."Focus:Time Complexity: Execution time (how the algorithm scales with input size).Space Complexity: Memory usage (how much memory the algorithm needs as the input size grows).
what?
. What (Best, Average, and Worst Case Scenarios):Best Case: Minimum time required under optimal conditions.Average Case: Expected time for typical conditions (random inputs).Worst Case: Maximum time required under the worst possible conditions.2. Why (Understanding Different Cases):Helps in assessing how well an algorithm performs not just in optimal conditions but also when inputs are random or adversarial.3. When (Scenarios Apply):Best Case: Useful when input is already sorted (e.g., searching the first element).Average Case: Typical inputs (random or mixed data).Worst Case: Worst-case scenario where the input is in reverse order or leads to maximum complexity (e.g., searching the last element).4. Where (Common Use Cases):Best Case: Linear search when the target is the first element.Average Case: Quick Sort with random pivots.Worst Case: Linear search when the target is not present or at the end.5. How (Implementation of Different Cases):Best Case Example (Linear Search):
To highlight super relevant data. 90% of the information we assimilate comes through sight.
Use graphics in your presentation...
Deletion:1. What (Definition of Deletion):Deletion removes a key-value pair from the hash table.2. Why (Purpose of Deletion):Necessary to free up space and maintain the integrity of the table when keys are no longer needed.3. When (When to Delete):Used when a key is no longer needed or must be updated.4. Where (Use Cases):Databases and cache systems often delete stale or invalid data.5. How (Implementation of Deletion):Compute the hash value of the key.Find the bucket where the key is stored.Remove the key-value pair.Handle any collisions that may arise.
To highlight super relevant data. 90% of the information we assimilate comes through sight.
Use graphics in your presentation...
1. What (Definition of Access):Access refers to the ability to retrieve data from the hash table based on the key.2. Why (Purpose of Access):Important for reading the stored data for further operations.3. When (When to Access):Access is performed when the value associated with a key needs to be read.4. Where (Use Cases):Often used in caching, databases, and associative arrays.5. How (Implementation of Access):Typically, access is part of the search operation.Code Example: Follows the same logic as searching.
What (Definition of Print):Print outputs the current state of the hash table, showing all key-value pairs.2. Why (Purpose of Print):Useful for debugging and verifying the contents of the hash table.3. When (When to Print):Typically used during development or when needing to log the current state of the table.4. Where (Use Cases):Print operations are common in testing environments or debugging situations.5. How (Implementation of Print):Iterate through all the buckets.Print all key-value pairs stored in each bucket.
- Discuss the situations or conditions for its use.
when?
- Mention the advantages and benefits. - Explain the problem it solves or the need it addresses.
why?
- Explain the step-by-step processes involved.
how?
Search Algorithms:Linear Search: O(n).Binary Search: O(log n).Sorting Algorithms:Bubble Sort: O(n²).Quick Sort: O(n log n) (average), O(n²) (worst case).Merge Sort: O(n log n).Graph Algorithms:Breadth-First Search (BFS): O(V + E), where V is vertices and E is edges.Dijkstra’s Algorithm: O(V²) or O((V + E) log V) with a priority queue.
Where?
- Discuss the situations or conditions for its use.
when?
What (Definition of Resize):Resize involves expanding the hash table and rehashing all existing elements when the load factor exceeds a threshold.2. Why (Purpose of Resize):To maintain efficiency when the number of elements exceeds the table's capacity, avoiding excessive collisions.3. When (When to Resize):When the load factor (number of elements divided by table size) exceeds a certain threshold (e.g., 0.7).4. Where (Use Cases):Hash tables in dynamic applications, such as memory caches or dynamic associative arrays.5. How (Implementation of Resize):Double the size of the table.Rehash all existing elements into the new table.Update the capacity.
1. What (Definition of Search):Search finds the value associated with a key in the hash table.2. Why (Purpose of Search):Essential for retrieving stored data quickly, based on the key.3. When (When to Search):Occurs when data needs to be accessed using a known key.4. Where (Use Cases):Common in lookup tables, caches, and dictionaries.5. How (Implementation of Search):Compute the hash value of the key.Check the bucket for the key.If found, return the value.If not found, return an indication of failure.
To highlight super relevant data. 90% of the information we assimilate comes through sight.
Use graphics in your presentation...
Scenarios:Used when there is an unknown dataset size.Frequent insertion or deletion of elements is required.
when?
Applications:Dynamic data structures such as:Linked Lists.Stacks.Queues.Hash Tables.Dynamic Graphs.Search Algorithms, such as:Quick Selection.Binary Search.Linear Search.Sorting Algorithms, such as:Bubble Sort.Quick Sort.Merge Sort.Bucket Sort.Insertion Sort.Selection Sort.Heap Sort.
Where?
Operations:Insertion, Deletion, Access, Search, Resize: Key operations in hashing.Process:Step 1: Initialization.Step 2: Execute operations.
how?
- https://www.geeksforgeeks.org/array-data-structure-guide/
- https://www.geeksforgeeks.org/top-50-array-coding-problems-for-interviews/
- https://www.geeksforgeeks.org/c-arrays/
- https://leetcode.com/tag/array/
Other Resources to Practice:
learn more
Definition: Hashing is a collection of elements that:Have key characteristics of being accessed using indices.Utilize dynamic resizing.Are stored in contiguous blocks of memory.Structure:Underlying fixed-size array.Capacity variable (total allocated space).Size variable for the number of elements.
what?
Advantages:Efficient Random Access: O(1) time complexity for accessing elements.Problems Solved:Static Array Limitations: Handles issues with static arrays like:Fixed size.Simplified operations.
why?
- Specify where it is used in the real world. - Highlight relevant contexts and scenarios.
Where?
Search Algorithms:Linear Search: O(n).Binary Search: O(log n).Sorting Algorithms:Bubble Sort: O(n²).Quick Sort: O(n log n) (average), O(n²) (worst case).Merge Sort: O(n log n).Graph Algorithms:Breadth-First Search (BFS): O(V + E), where V is vertices and E is edges.Dijkstra’s Algorithm: O(V²) or O((V + E) log V) with a priority queue.
- Mention the advantages and benefits. - Explain the problem it solves or the need it addresses.
why?
What (Common Algorithm Examples):Search Algorithms:Linear Search (O(n)): Check each element until the target is found.Binary Search (O(log n)): Divide the search space in half at each step, requires sorted data.Sorting Algorithms:Bubble Sort (O(n²)): Repeatedly swap adjacent elements if they are in the wrong order.Merge Sort (O(n log n)): Divide the array into halves, sort each half, and then merge them.Graph Algorithms:Breadth-First Search (BFS): O(V + E) where V is vertices and E is edges.Dijkstra’s Algorithm: O(V²) or O((V + E) log V) using a priority queue for shortest paths.2. Why (Why These Examples Matter):Search Algorithms: Common for finding specific elements in datasets.Sorting Algorithms: Essential for arranging data in a particular order efficiently.Graph Algorithms: Critical for pathfinding, traversal, and optimization in network-like structures.3. When (Use Cases for Each Example):Linear Search: Used when data is unsorted.Binary Search: Used when data is sorted.Bubble Sort: Simple but inefficient for large datasets.Merge Sort: Efficient for larger datasets.BFS: Used in shortest path problems.Dijkstra’s Algorithm: Optimal for weighted graph shortest paths.4. Where (Common Use Cases):Search Algorithms: Used in databases and data retrieval systems.Sorting Algorithms: Used in ordering elements, especially in preprocessing for searching algorithms.Graph Algorithms: Used in network routing, social network analysis, and many real-world applications.5. How (Implementation of Algorithms):Binary Search Example:
- Specify where it is used in the real world. - Highlight relevant contexts and scenarios.
Where?
- Explain the step-by-step processes involved.
how?
Best Case Complexity:Definition: Minimum time required under optimal conditions.Example: Linear Search, when the first element is the target (O(1)).Worst Case Complexity:Definition: Maximum time required under the worst conditions.Example: Linear Search, when the target is the last element or not present (O(n)).Average Case Complexity:Definition: Expected runtime for random inputs.Example: Quick Sort with random pivots (O(n log n)).
when?
What (Memory and Recursive Algorithms):Memory Allocation: Focuses on how much memory is allocated for variables and data structures.Recursive Algorithms: Includes the stack space used in recursion, which can grow based on recursion depth.Optimizing Space Usage: Techniques like using in-place algorithms to reduce space complexity.2. Why (Memory Usage Consideration):Memory Allocation: Important for resource-constrained environments.Recursive Algorithms: Can lead to stack overflow if the recursion depth is too large.3. When (Space Optimization Needed):Used when space is limited, or the algorithm has high memory requirements (e.g., deep recursion).4. Where (Common Use Cases):Recursive algorithms (e.g., recursive tree traversal).In-place sorting algorithms (e.g., Quick Sort).5. How (Implementation of Space Optimization):Recursive Example (Fibonacci with Memorization to reduce space)
1. What (Definition of Insertion):Insertion is the process of adding a key-value pair into a hash table.2. Why (Purpose of Insertion):The insertion operation is critical for storing data in the hash table efficiently, allowing for quick retrieval later.3. When (When to Insert):Insertions occur when a new key-value pair needs to be stored or when resizing requires rehashing of elements.4. Where (Use Cases):Hash tables are used in databases, caches, and associative arrays (dictionaries), where fast insertion is essential.5. How (Implementation of Insertion):Compute the hash value of the key.Check if the corresponding bucket is empty.If the bucket is empty, insert the key-value pair.If there's a collision, handle it using techniques like separate chaining or open addressing.
- Provide a definition and key characteristics. Syntax: - Define type int, char, float- Example: int arr[3]Initialization:- int arr[3] = {1, 2, 3} - Explain the fundamental principles. - Discuss the basic structure or components. - Include any related terminology and concepts.
what?
Purpose:Provides a worst-case scenario for algorithm performance. Helps compare the efficiency of algorithms.Types of Complexity Classes:Constant Time (O(1)): The execution time remains constant, regardless of input size.Example: Accessing an element in an array by index.Logarithmic Time (O(log n)): Execution time increases logarithmically with input size.Example: Binary search in a sorted array.Linear Time (O(n)): Execution time grows linearly with input size.Example: Iterating through an entire array.Linearithmic Time (O(n log n)): Execution time grows linearly, multiplied by a logarithmic factor.Example: Efficient sorting algorithms like Merge Sort.Quadratic Time (O(n²)): Execution time grows proportionally to the square of the input size.Example: Nested loops such as in Bubble Sort.Cubic Time (O(n³)): Execution time grows proportionally to the cube of the input size.Example: Matrix operations with three nested loops.Exponential Time (O(2^n)): Execution time doubles with each addition to the input size.Example: Recursive algorithms like the Towers of Hanoi.Factorial Time (O(n!)): Execution time grows factorially with the input size.Example: Permutations of a set, such as the Traveling Salesman Problem.
why?