Lecture Notes: Data Structures and Algorithms
(DSA)
Instructor: Prof. Ahmad Zeeshan | Course Code: CS-201
Topics Covered
1. Arrays and Linked Lists
2. Stacks and Queues
3. Trees and Graphs
4. Sorting Algorithms
5. Searching Algorithms
6. Big-O Notation (Complexity Analysis)
1. Arrays
Definition: A collection of elements stored in contiguous memory locations.
Advantages: Fast indexing, easy traversal.
Disadvantages: Fixed size, costly insert/delete in middle.
2. Linked List
Definition: A collection of nodes where each node stores data and a pointer to the next node.
Advantages: Dynamic size, efficient insertion/deletion.
Disadvantages: No direct access, extra memory for pointers.
3. Stacks & Queues
Stack: LIFO (Last In, First Out). Example: Undo feature in editors.
Queue: FIFO (First In, First Out). Example: Print queue.
4. Trees
Tree: A hierarchical data structure with nodes.
Binary Tree: Each node has at most two children.
Binary Search Tree (BST): Left child < parent < right child.
5. Graphs
Graph: A set of vertices connected by edges.
Directed Graph: Edges have direction.
Weighted Graph: Edges have weights (used in shortest path algorithms).
6. Sorting & Searching Algorithms
Sorting:
- Bubble Sort: O(n^2)
- Merge Sort: O(n log n)
- Quick Sort: O(n log n) average.
Searching:
- Linear Search: O(n)
- Binary Search: O(log n) (works on sorted arrays).
7. Complexity Analysis (Big-O Notation)
Big-O gives the upper bound of an algorithm's runtime.
Examples:
- O(1): Constant time
- O(n): Linear time
- O(n^2): Quadratic time
- O(log n): Logarithmic time
Summary
This lecture introduced fundamental data structures and algorithms. Mastering these
concepts is essential for coding interviews, competitive programming, and real-world
problem solving.
