Scribd
Upload
20 views2 pages

DSA_Notes_Cpp

The document provides a comprehensive overview of data structures and algorithms in C++, covering time and space complexity, various data structures like arrays, strings, stacks, queues, linked lists, trees, and graphs, as well as key concepts in searching, sorting, hashing, recursion, backtracking, and dynamic programming. It includes common problems and techniques associated with each topic, such as binary search, tree traversals, and dynamic programming strategies. The notes also highlight the use of the C++ Standard Template Library (STL) for efficient data handling.

Uploaded by

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

DSA_Notes_Cpp

The document provides a comprehensive overview of data structures and algorithms in C++, covering time and space complexity, various data structures like arrays, strings, stacks, queues, linked lists, trees, and graphs, as well as key concepts in searching, sorting, hashing, recursion, backtracking, and dynamic programming. It includes common problems and techniques associated with each topic, such as binary search, tree traversals, and dynamic programming strategies. The notes also highlight the use of the C++ Standard Template Library (STL) for efficient data handling.

Uploaded by

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

Ὅ DSA Handwritten-Style Notes (C++)

✏ Basics
● Time Complexity: O(1) < O(log n) < O(n) < O(n log n) < O(n^2)
● Space Complexity measures memory usage.
● STL Quick: vector, map, set, stack, queue.

✏ Arrays & Strings


● Two Pointer: Start and end indices move towards each other.
● Sliding Window: Fixed/variable size window to optimize loops.
● Common Qs: Reverse array, rotate array, max subarray sum.

✏ Searching & Sorting


● Binary Search: O(log n), works on sorted arrays.
● Sorting: QuickSort (O(n log n)), MergeSort (O(n log n)), BubbleSort (O(n^2)).
● Upper Bound / Lower Bound usage in C++ STL.

✏ Hashing
● map/unordered_map store key-value pairs.
● set/unordered_set store unique elements.
● Useful for frequency counting and lookups.

✏ Stack & Queue


● Stack: LIFO (last in, first out).
● Queue: FIFO (first in, first out).
● Applications: Expression evaluation, BFS.

✏ Linked List
● Singly LL: Node with data + next.
● Doubly LL: Node with data + prev + next.
● Common Qs: Reverse LL, detect cycle (Floyd’s algo).

✏ Recursion & Backtracking


● Recursion: Function calls itself.
● Base Case + Recursive Case.
● Backtracking: Undo choices to explore all solutions.
✏ Trees & BST
● Tree Traversals: Inorder, Preorder, Postorder.
● BST: Left < Root < Right.
● Common Qs: Height of tree, Lowest Common Ancestor.

✏ Graphs
● BFS: Level-order traversal.
● DFS: Depth-first traversal.
● Graph Representations: Adjacency list/matrix.

✏ Dynamic Programming Basics


● Break problem into subproblems, store results.
● Memoization (top-down) vs Tabulation (bottom-up).
● Common Qs: Fibonacci, Knapsack, Coin Change.

You might also like