KEMBAR78
DSA Notes | PDF | Algorithms And Data Structures | Computer Programming
Scribd
Upload
20 views3 pages

DSA Notes

This document provides an overview of data structures and algorithms, including definitions, operations, and performance analysis. It covers various data structures such as arrays, stacks, queues, lists, trees, heaps, and hash tables, along with their respective operations and complexities. Additionally, it discusses sorting algorithms and collision handling techniques in hash tables.

Uploaded by

jeetameta44
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 views3 pages

DSA Notes

This document provides an overview of data structures and algorithms, including definitions, operations, and performance analysis. It covers various data structures such as arrays, stacks, queues, lists, trees, heaps, and hash tables, along with their respective operations and complexities. Additionally, it discusses sorting algorithms and collision handling techniques in hash tables.

Uploaded by

jeetameta44
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/ 3

Data Structures and Algorithms Notes

Analyzing Algorithms

Algorithm: Step-by-step procedure to solve a problem.

Specification: Describes input, output, and method.

Best Case: Minimum time for any input.

Average Case: Expected time for all inputs.

Worst Case: Maximum time for any input.

Asymptotic Notations:

- Big-O (O): Upper bound (worst case)

- Omega: Lower bound (best case)

- Theta: Tight bound (average case)

- Little-o: Strict upper bound

Elementary Data Structures: Arrays

Representation: Stored in contiguous memory.

Operations:

- Search: Linear (unsorted), Binary (sorted)

- Insert: End (O(1)), elsewhere (shift)

- Delete: Shift elements after removal

- Min & Max: Linear scan

Stacks

LIFO structure.

Operations: Push, Pop, Peek.

Applications: Expression evaluation, backtracking.

Queues
Data Structures and Algorithms Notes

FIFO structure.

Operations: Enqueue, Dequeue, Peek.

Applications: Scheduling, buffering.

Lists

Linear collection with positions.

Singly/Doubly Linked Lists.

Allows insertion/deletion at any position.

Sorting Algorithms

Bubble Sort: Swap adjacent if out of order. O(n^2)

Selection Sort: Find min, place at start. O(n^2)

Insertion Sort: Insert each element in sorted position. O(n^2)

Merge Sort: Divide, sort, merge. O(n log n)

Trees

Nodes with parent-child hierarchy.

Terms: Root, Child, Leaf, Subtree.

Binary Tree: Max 2 children.

Representation: Array or linked.

Traversal: In-Order, Pre-Order, Post-Order.

Binary Search Trees (BST)

BST Property: Left < Root < Right.

Operations: Search, Insert, Delete (3 cases).


Data Structures and Algorithms Notes

Heaps

Complete binary tree.

Min-Heap: Parent <= children.

Max-Heap: Parent >= children.

Operations: Insert (heapify up), Delete (heapify down).

AVL Trees

Self-balancing BST.

Balance factor = height(left) - height(right) <= 1.

Uses rotations to rebalance.

Dictionaries & Hash Tables

Unordered key-value pairs.

Hashing: Maps keys to indices.

Collisions: Handled via chaining or open addressing.

Hash Functions: Distribute keys uniformly.

Collision Handling

Separate Chaining: Linked list at each index.

Open Addressing:

- Linear Probing: Sequential search

- Quadratic Probing: Interval grows quadratically

- Double Hashing: Second hash function for step size

Load Factor: Entries/table size.

Rehashing: Resize table and reinsert entries.

You might also like