Data Structures and Algorithms Lecture Notes

Introduction

• Discusses data structures and algorithms.
• Topics covered: basic data structures, Big O notation, searching algorithms, sorting algorithms, graphs, and trees.
• Data structure: named location to store and organize data (e.g., family tree).
• Algorithm: collection of steps to solve a problem (e.g., baking a pizza).
• Importance: writing efficient code and preparing for job interviews.

Stacks

Definition

• Stack: LIFO (Last In First Out) data structure.
• Example: stack of books.

Operations

• push: add an object to the top of the stack.
• pop: remove an object from the top of the stack.
• Accessing bottom items requires popping all items on top.

Methods of Stacks

1. push: add an item.
2. pop: remove an item.
3. peek: view the top item without removing it.
4. empty: check if stack is empty.
5. search: find an item in the stack.

Use Cases

• Undo/redo features in text editors.
• Browser history navigation.
• Backtracking algorithms.
• Function call management in programming.

Queues

Definition

• Queue: FIFO (First In First Out) data structure.
• Example: line of people.

Operations

• enqueue: add an object to the end of the queue.
• dequeue: remove an object from the front of the queue.

Methods of Queues

1. offer: add an element to the end.
2. poll: remove an element from the front.
3. peek: view the front element without removing it.

Use Cases

• Keyboard buffers.
• Print job management.
• Navigating through file directories.

Priority Queues

Definition

• A priority queue is a FIFO data structure where elements are served based on priority.

Example

• Students with GPAs in a priority queue would be served according to their GPA.

Operations

• Similar to regular queues but include priority management.

Linked Lists

Definition

• A linked list consists of nodes containing data and links to the next node.
• Types: singly linked list and doubly linked list.

Advantages

• Efficient insertion and deletion.
• Dynamic size.

Disadvantages

• Poor random access (linear time complexity for searching).

Dynamic Arrays

Definition

• An array with resizable capacity (e.g., ArrayList in Java).

Advantages

• Random access in constant time.
• Good data locality.

Disadvantages

• Wasted memory due to capacity resizing.
• Slower resize operations.

Big O Notation

Definition

• Represents the performance of an algorithm as data size increases.

Common Complexities

• O(1): constant time.
• O(n): linear time.
• O(log n): logarithmic time (e.g., binary search).
• O(n^2): quadratic time (e.g., bubble sort).

Searching Algorithms

Linear Search

• Iterates through elements one by one.
• Time complexity: O(n).

Binary Search

• Requires sorted data; divides search space in half.
• Time complexity: O(log n).

Sorting Algorithms

Bubble Sort

• Compares adjacent elements and swaps if needed.
• Time complexity: O(n^2).

Selection Sort

• Finds the smallest element and places it at the beginning.
• Time complexity: O(n^2).

Insertion Sort

• Builds a sorted array one element at a time.
• Time complexity: O(n^2).

Merge Sort

• Divide and conquer algorithm; splits array into subarrays.
• Time complexity: O(n log n).

Quick Sort

• Selects a pivot and partitions elements around it.
• Time complexity: O(n log n) average case, O(n^2) worst case.

Graphs

Definition

• A graph consists of nodes (vertices) and edges connecting them.

Types

• Undirected and directed graphs.

Representation

1. Adjacency Matrix: 2D array; space complexity O(v^2).
2. Adjacency List: array of linked lists; space complexity O(v + e).

Tree Terminology

Definition

• A tree is a non-linear data structure with a hierarchical relationship.

Key Terms

• Root: top node.
• Leaf: node with no children.
• Depth: length of path to a node.
• Height: length of path from a node to its furthest leaf.

Binary Search Tree (BST)

• A binary tree where left children are less than the parent and right children are greater.

Tree Traversal

1. In-order: left, root, right (ascending order in BST).
2. Pre-order: root, left, right (used for copying).
3. Post-order: left, right, root (used for deletion).

Runtime Measurement

Measuring Runtime

• Use System.nanoTime() to measure the duration of a program.
• Subtract the start time from the end time for the total execution time.