[go: up one dir, main page]
Scribd
Upload
6 views2 pages

Data Structures Algorithms Cheatsheet Styled

The document provides a comprehensive overview of data structures and algorithms, focusing on recursion, sorting algorithms, searching algorithms, graph traversal, advanced pathfinding, and dynamic programming. It highlights when to use recursion, the importance of sorting, various sorting algorithms with their time complexities, and methods for searching data. Additionally, it discusses graph traversal techniques, types of graphs, and optimization strategies like caching and memoization in dynamic programming.

Uploaded by

stella luna
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views2 pages

Data Structures Algorithms Cheatsheet Styled

The document provides a comprehensive overview of data structures and algorithms, focusing on recursion, sorting algorithms, searching algorithms, graph traversal, advanced pathfinding, and dynamic programming. It highlights when to use recursion, the importance of sorting, various sorting algorithms with their time complexities, and methods for searching data. Additionally, it discusses graph traversal techniques, types of graphs, and optimization strategies like caching and memoization in dynamic programming.

Uploaded by

stella luna
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

Data Structures & Algorithms Cheatsheet (Summary)

Recursion – When to Use


 Use recursion when:
 Problem divides into smaller subproblems of the same type
 Subproblems are identical in nature
 Solutions combine to solve the whole problem
 👉 Common in trees & divide-and-conquer problems

Sorting Algorithms
 Arrange array/list elements in ascending or descending order.:
 Why sorting matters:
 • Faster data access & processing
 • Optimizes operations in databases, finance, etc.
 • Improves efficiency of software systems
 Why not just use sort()?:
 • Performance varies with dataset
 • May not maintain order of equal elements
 • Limited customization
 • May need more memory
 Why many sorting algorithms?:
 Each has tradeoffs: speed, stability, memory, implementation ease.

Common Sorting Algorithms


 Bubble Sort:
 Swap adjacent items until sorted. Time: O(n²). Easy but slow.
 Selection Sort:
 Find smallest, move to front. Time: O(n²). Simple but inefficient.
 Insertion Sort:
 Insert into correct position. Time: O(n²), Best O(n). Good for small/nearly sorted data.
 Merge Sort:
 Divide, sort halves, merge. Time: O(n log n). Stable, extra memory needed.
 Quick Sort:
 Pivot, partition, recurse. Avg O(n log n), Worst O(n²). Very fast with good pivot.
 Choosing Algorithm:
 Small/almost sorted → Insertion. Large → Quick/Merge. Simple but slow →
Bubble/Selection.
 Comparison vs Non-Comparison Sort:
 • Comparison: Quick, Merge, Insertion, Selection, Bubble. Lower bound O(n log n).
 • Non-Comparison: Counting, Radix, Bucket. Can reach O(n).
 Fun Fact:
 V8 (Chrome/Node.js) uses hybrid Quick + Insertion Sort.
Searching Algorithms
 Linear Search:
 Check items one by one. Time: O(n). Works on unsorted data.
 Binary Search:
 Divide sorted array in half. Time: O(log n). Requires sorted data.

Graph Traversal
 BFS (Breadth-First Search):
 Level by level. Queue. Time: O(V+E). Finds shortest path in unweighted graph.
 DFS (Depth-First Search):
 Deep first. Stack/Recursion. Time: O(V+E). Finds paths, cycles.
 BFS vs DFS:
 • BFS: More memory, finds shortest path.
 • DFS: Less memory, explores all.

Advanced Pathfinding
 Dijkstra’s Algorithm:
 Non-negative weights. Time: O((V+E) log V). Fast for sparse graphs.
 Bellman-Ford Algorithm:
 Handles negative weights. Time: O(VE). Slower but flexible.
 Negative Edge Weights:
 Represent penalties, need Bellman-Ford.
 Relaxation:
 Update distance if shorter path found.

Graph Types
 Sparse Graph:
 Few edges compared to vertices.
 Common in social networks, transport maps.
 Often faster to process.

Dynamic Programming (DP)


 Break problem into smaller subproblems.
 Store solutions to reuse (avoid recomputation).
 Optimizes performance.
 Caching:
 Store frequently accessed data for quick retrieval.
 Memoization:
 Cache function results to avoid recalculation.
 Difference: Caching = general data, Memoization = function results.

You might also like