C949 STUDY GUIDE V4

Finiteness

An algorithm must always have a finite number of steps before it ends. When the operation is finished, it must have a defined endpoint or output and not enter an endless loop.

Definiteness

An algorithm needs to have exact definitions for each step. Clear and straightforward directions ensure that every step is understood and can be taken easily.

Effectiveness

An algorithm's stages must be sufficiently straightforward to be carried out in a finite time utilizing fundamental operations. With the resources at hand, every operation in the algorithm should be doable and practicable.

Generality

Rather than being limited to a single particular case, an algorithm should be able to solve a group of issues. It should offer a generic fix that manages a variety of inputs inside a predetermined range or domain.

Modularity

This feature was perfectly designed for the algorithm if you are given a problem and break it down into small-small modules or small-small steps, which is a basic definition of an algorithm.

Correctness

An algorithm's correctness is defined as when the given inputs produce the desired output, indicating that the algorithm was designed correctly. An algorithm's analysis has been completed correctly.

Maintainability

It means that the algorithm should be designed in a straightforward, structured way so that when you redefine the algorithm, no significant changes are made to the algorithm.

Functionality

It takes into account various logical steps to solve a real-world problem.

Robustness

_____ refers to an algorithm's ability to define your problem clearly.

User-friendly

If the algorithm is difficult to understand, the designer will not explain it to the programmer.

Simplicity

 If an algorithm is simple, it is simple to understand.

Extensibility

Your algorithm should be extensible if another algorithm designer or programmer wants to use it.

Linear Search Concept

• _____ search is the simplest search algorithm.

• It works by sequentially checking each element of the array or list until the target element is found or the end of the collection is reached.

Linear Search Algorithm

1. Start from the first element of the array.

2. Compare the current element with the target element.

3. If they match, return the index of the element.

4. If they don't match, move to the next element and repeat the process.

5. If the target element is not found by the end of the array, return a "not found" indication.

Linear Search Time Complexity

O(n), where n is the number of elements in the array. This is because in the worst case, the algorithm may need to check every element in the array

Linear Search When to Use

• When the array or list is small.

• When the array is unsorted.

• When simplicity is more important than performance.

Binary Search Concept

• _____ search is much more efficient than linear search but requires the array or list to be sorted.

• It works by repeatedly dividing the search interval in half. If the target value is less than the middle element, the search continues in the left half, otherwise in the right half.

Binary Search Algorithm

1. Start with two pointers, one at the beginning (low) and one at the end (high) of the sorted array.

2. Find the middle element of the current interval.

3. Compare the middle element with the target:

   • If they match, return the index of the middle element.

   • If the target is less than the middle element, repeat the search on the left half.

   • If the target is greater, repeat the search on the right half.

4. If the interval becomes invalid (low > high), return a "not found" indication.

Binary Search Time Complexity

O(log⁡ n), where n is the number of elements in the array. This logarithmic time complexity makes _____ search significantly faster than linear search for large datasets.

Binary Search When to Use

• When the array or list is sorted.

• When the array is large and efficiency is crucial.

Linear Search Worst, Average and Best

• Best Case: O(1) — The target element is the first element.

• Average Case: O(n) — The target element is somewhere in the middle or not in the array.

Worst Case: O(n) — The target element is the last element or not present.

Binary Search Worst, Average and Best

• Best Case: O(1) — The target element is the middle element.

• Average Case: O(log ⁡n) — The target element is not immediately found but within the sorted array.

• Worst Case: O(log⁡ n) — The target element is at the extreme ends or not present.

Interpolation Search Concept

Similar to binary search but works on uniformly distributed data. It estimates the position of the target element based on the value.

Interpolation Search Time Complexity

O(log ⁡log ⁡n) in the best case, O(n) in the worst case.

Interpolation Search Use Case

Effective when the data is uniformly distributed.

Interpolation Search Worst, Average and Best

• Best Case: O(1) — The target element is exactly where the interpolation suggests.

• Average Case: O(log ⁡log⁡ n) — Uniformly distributed data.

• Worst Case: O(n) — Highly skewed data distribution or worst interpolation.

Depth-First Search (DFS) and Breadth-First Search (BFS) Concept

• Used primarily in graph and tree data structures. ____ explores as far as possible along one branch before backtracking, while ____ explores all neighbors at the present depth before moving on to nodes at the next depth level.

Depth-First Search (DFS) and Breadth-First Search (BFS) Time Complexity

O(V+E), where V is the number of vertices and E is the number of edges.

Depth-First Search (DFS) and Breadth-First Search (BFS) Use Case

Useful for searching nodes in graphs and trees.

Depth-First Search (DFS) Worst, Average and Best

• Best Case: O(1) — The target node is found immediately.

• Average Case: O(V+E)— Typically when all nodes and edges must be explored.

Worst Case: O(V+E) — The target node is the last one discovered.

Breadth-First Search (BFS) Worst, Average and Best

• Best Case: O(1) — The target node is the root or the first node checked.

• Average Case: O(V+E) — All nodes and edges need to be explored.

• Worst Case: O(V+E) — The target node is the last one explored.

Array Description

______ is a collection of homogeneous elements stored in contiguous memory locations. Each element in the ____ can be accessed using its index.

Python Equivalent: list

Array Operations

• Access: O(1) — Direct access to elements via index. 

• Search:

  • Linear Search: O(n)

Binary Search: O(log⁡ n) (only if the array is sorted)

Array Operations Insertion

• At the End: Append the element to the end of the array. If the array is full (fixed size), you may need to resize it.

  • Time Complexity: O(1) (amortized if resizing is needed).

• At a Specific Index: Shift elements to the right from the index to create space, then insert the new element.

Time Complexity: O(n), where n is the number of elements after the insertion point.

Array: Operations: Deletion

• From the End: Remove the last element.

  • Time Complexity: O(1).

• From a Specific Index: Shift elements to the left to fill the gap left by the removed element.

Time Complexity: O(n), where n is the number of elements after the removal point.

Linked List Types

• Singly Linked List: Each node points to the next node.

• Doubly Linked List: Each node points to both the next and previous nodes.

Circular Linked List: The last node points back to the first node, forming a loop.

Linked List Operations

• Access: O(n) — Requires traversal from the head to the desired node.

Search: O(n) — Requires traversal to find the target element.

Linked List Operations: Insertion

• At the Beginning (Singly/ Doubly Linked List): Create a new node and adjust the head (and possibly tail in a doubly linked list).

  • Time Complexity: O(1).

• At the End (Singly Linked List): Traverse to the last node, then insert the new node.

  • Time Complexity: O(n).

• At a Specific Position: Traverse to the position and insert the node, adjusting the pointers.

Time Complexity: O(n).

Linked List Operations: Deletion

• From the Beginning: Adjust the head pointer to the next node.

  • Time Complexity: O(1).

• From the End: Traverse to the second last node, adjust its pointer to null.

  • Time Complexity: O(n).

• From a Specific Position: Traverse to the node before the one to remove, then adjust pointers to bypass the removed node.

  • Time Complexity: O(n).

Methods for Lists/Arrays

append()

• Description: Adds an element to the end of the list.

Syntax: list.append(element)

Methods for Lists/Arrays

extend()

• Description: Extends the list by appending elements from another iterable (e.g., another list).

Syntax: list.extend(iterable)

Methods for Lists/Arrays

insert()

• Description: Inserts an element at a specific index in the list.

Syntax: list.insert(index, element)

Methods for Lists/Arrays

remove()

• Description: Removes the first occurrence of a specified value from the list.

Syntax: list.remove(element)

Methods for Lists/Arrays

pop()

• Description: Removes and returns the element at the specified index. If no index is specified, it removes and returns the last element.

Syntax: list.pop(index)

Methods for Lists/Arrays

index()

• Description: Returns the index of the first occurrence of a specified value.

Syntax: list.index(element, start, end)

Methods for Lists/Arrays

count()

• Description: Returns the number of occurrences of a specified value in the list.

Syntax: list.count(element)

Methods for Lists/Arrays

sort()

• Description: Sorts the elements of the list in ascending order (or descending order if specified) in place.

Syntax: list.sort(reverse=False)

Methods for Lists/Arrays

reverse()

• Description: Reverses the elements of the list in place.

Syntax: list.reverse()

Methods for Lists/Arrays

copy()

• Description: Returns a shallow copy of the list.

Syntax: list.copy()

Record

• A _______ is a composite data structure used to store a collection of related fields, each with a specific name and data type. 

• It is commonly used to model entities in databases and programming, allowing for structured and organized data storage. 

• ______ are versatile and can represent complex objects with multiple attributes, making them essential in many applications.

Stack Description

• A _______ is a linear data structure that follows the Last-In-First-Out (LIFO) principle, meaning the last element added is the first one to be removed.

Python Equivalent: list or collections.deque

stack operations

• Push (Insertion): O(1) — Add an element to the top of the stack.

• Pop (Deletion): O(1) — Remove the top element from the stack.

• Peek/Top: O(1) — View the top element without removing it.

IsEmpty: O(1) — Check if the stack is empty.

bag description

• A _____ (also known as a multiset) is a simple data structure that allows for storing a collection of elements where duplicate elements are allowed. Unlike a set, which requires all elements to be unique, a _____ can contain multiple occurrences of the same element.

Python Equivalent: collections.Counter

bag operations

• Add (add) — Adds an element to the bag.

  • Simply add the element, usually at the end or beginning, depending on the implementation (array, linked list, etc.).

    • Time Complexity: O(1).

• Check Membership (contains) — Checks if an element is in the bag.

• Count Occurrences (count) — Counts how many times an element appears in the bag.

• Remove (remove) — Removes one occurrence of an element from the bag.

  • Typically, bags do not have a direct remove operation unless implemented, in which case:

    • Remove Specific Element: Find the element and remove it, adjusting structure accordingly.

      • Time Complexity: O(n).

• Get Size (size) — Returns the total number of elements in the bag, including duplicates.

queue description

• A ______ is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the first element added is the first one to be removed.

Python Equivalent: collections.deque or queue.Queue

queue operations

• Enqueue (Insertion/Push): O(1) — Add an element to the end of the queue.

• Dequeue (Deletion/Pop): O(1) — Remove the front element from the queue.

• Front/Peek: O(1) — View the front element without removing it.

• IsEmpty: O(1) — Check if the queue is empty.

deque description

• A ______ is a linear data structure that allows insertion and deletion of elements from both the front and rear ends.

Python Equivalent: collections.deque

deque operations

• InsertFront: O(1) — Add an element to the front.

• InsertLast: O(1) — Add an element to the end.

• DeleteFront: O(1) — Remove an element from the front.

• DeleteLast: O(1) — Remove an element from the end.

• PeekFront: O(1)— View the front element.

• PeekLast: O(1) — View the last element.

IsEmpty: O(1) — Check if the deque is empty.

hash table: description

• A ________ is a data structure that maps keys to values using a hash function, which transforms the key into an index in an array.

• Python Equivalent: dict

hash table operations

• Insert: O(1) — Map a key to a value by computing its hash.

• Search: O(1) — Retrieve the value associated with a given key.

• Delete: O(1) — Remove the key-value pair from the table.

hash tables: handling collisions

• Chaining: Store multiple elements at the same index using a linked list.

Open Addressing (Probing): Find another open slot using techniques like linear probing, quadratic probing, or double hashing.

hash tables: hashing

____ is the process of mapping keys to indices in an array using a hash function. It ensures efficient data retrieval by minimizing the number of comparisons required.

tree: description

• A _______ is a hierarchical data structure composed of nodes, where each node contains a value and references to child nodes. The top node is called the root, and nodes with no children are called leaves.

Python Equivalent: Custom class with Node and Tree classes

Binary Search Tree (BST)

A binary tree where the left child contains values less than the parent, and the right child contains values greater than the parent.

AVL Tree

• A self-balancing binary search tree.

Red-Black Tree

• Another type of self-balancing binary search tree.

B-Tree

• A self-balancing tree that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.

full binary tree

A binary tree in which every node has either 0 or 2 children.

complete binary tree

• A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.

perfect binary tree

• A binary tree in which all interior nodes have two children and all leaves are at the same level.

balance binary tree

• A binary tree where the height of the left and right subtrees of any node differ by at most one.

tree operations

• Insertion: O(log ⁡n) for balanced trees like AVL or Red-Black Trees; O(n) for unbalanced trees.

• Deletion: O(log ⁡n) for balanced trees; O(n) for unbalanced trees.

  • BST: Find the node to be removed, then:

    • No Children: Just remove the node.

    • One Child: Bypass the node and link its parent directly to its child.

    • Two Children: Find the in-order predecessor (or successor), swap values, and remove the predecessor (or successor) node.

    • Time Complexity: O(log n) on average, O(n) in the worst case.

• Search: O(log ⁡n)  for balanced trees; O(n) for unbalanced trees.

• Traversal:

  • In-order: O(n) — Left, Root, Right (used in BSTs to get sorted order).

  • Pre-order: O(n) — Root, Left, Right.

  • Post-order: O(n) — Left, Right, Root.

  • Level-order: O(n)— Traverse nodes level by level.

Tree Traversal

• Pre-Order Traversal (NLR) - Node, Left, Right

• In-Order Traversal (LNR) - Left, Node, Right

• Post-Order Traversal (LRN) - Left, Right, Node

Tree traversal Visual mnemonic

• Pre-Order: Imagine starting at the root and touching it first.

• In-Order: Imagine walking along the edge of the tree, touching the left side first, then the root, and then the right side.

Post-Order: Imagine leaving the tree by processing the children before the root.

heap description

• A ____ is a specialized tree-based data structure that satisfies the ____ property. In a max-_____, the parent node is always greater than or equal to its children; in a min-_____, the parent node is always less than or equal to its children.

Python Equivalent: heapq (min-heap by default)

heap operations

• Insert: O(log ⁡n) — Add a new element and adjust the heap to maintain the heap property.

  • Add the Element at the End:

    • Insert the new element at the end of the heap (i.e., the next available leaf node).

  • Heapify Up (Percolate Up):

    • Compare the inserted element with its parent node.

    • If the heap property (Min-Heap or Max-Heap) is violated (e.g., in a Min-Heap, if the new element is smaller than its parent), swap the element with its parent.

    • Repeat the process until the heap property is restored or the element becomes the root.

• DeleteMax/Min: O(log ⁡n) — Remove the root (max or min) and adjust the heap.

  • Remove the Root Element:

    • The root element of the heap (the smallest element in a Min-Heap or the largest in a Max-Heap) is removed. This is because the root element has the highest priority.

  • Replace the Root with the Last Element:

    • Move the last element in the heap (the rightmost leaf node) to the root position.

  • Heapify Down (Percolate Down):

    • Compare the new root element with its children.

    • If the heap property is violated (e.g., in a Min-Heap, if the root is greater than any of its children), swap the root with the smallest child (in a Max-Heap, swap with the largest child).

    • Repeat the process down the tree until the heap property is restored.

• PeekMax/Min: O(1)— Access the root element.

• Heapify: O(n) — Convert an unsorted array into a heap.

set description

• A ______ is an abstract data structure that stores unique elements, with no specific order. It supports operations that allow the management of unique collections of data.

Python Equivalent: ____

set operations

• Insert: O(1) on average — Add a new element if it’s not already present.

• Delete: O(1) on average — Remove an element if it exists.

• Search: O(1) on average — Check if an element is present in the set.

• Union: O(n) — Combine elements from two sets.

• Intersection: O(n) — Get common elements between two sets.

• Difference: O(n) — Get elements present in one set but not the other.

graph description

• A _____ is a collection of nodes (vertices) connected by edges. _____ can be directed (edges have a direction) or undirected (edges do not have a direction).

• Python Equivalent: dict of lists, collections.defaultdict, or custom class

graph types: Directed Graph (Digraph)

All edges have a direction.

graph types: Undirected Graph

• Edges do not have direction.

praph types: Weighted Graph

• Edges have weights representing costs or distances.

graph operations

• Add Vertex: O(1) — Add a new node.

  • Vertex: Simply add the vertex to the vertex set.

    • Time Complexity: O(1).

• Add Edge: O(1) — Add a connection between two nodes.

  • Edge: Add an edge by connecting two vertices, updating adjacency lists or matrices.

    • Time Complexity: O(1) for adjacency list, O(1) for adjacency matrix.

• Remove Vertex: O(V+E) — Remove a node and its associated edges.

  • Vertex: Remove the vertex and all associated edges.

    • Time Complexity: O(V + E) in an adjacency list, O(V^2) in an adjacency matrix, where V is the number of vertices and E is the number of edges.

• Remove Edge: O(1) — Remove a connection between two nodes.

  • Edge: Remove the edge between two vertices.

    • Time Complexity: O(1) for adjacency list, O(1) for adjacency matrix.

• Search:

  • Depth-First Search (DFS): O(V+E) — Explore as far as possible along each branch before backtracking.

  • Breadth-First Search (BFS): O(V+E)— Explore all neighbors of a node before moving to the next level.

Dijkstra's Shortest Path Algorithm

Overview:

• Type: Greedy algorithm.

• Applicability: Works on graphs with non-negative edge weights.

• Time Complexity: O(V²) for the simplest implementation, O(V log V+E) with a priority queue (using a binary heap), where V is the number of vertices and E is the number of edges.

• Functionality: It finds the shortest path from a single source vertex to all other vertices in a graph by iteratively selecting the vertex with the smallest known distance, updating the distances to its neighbors, and marking it as visited.

Bellman-Ford Shortest Path Algorithm

Overview:

• Type: Dynamic programming algorithm.

• Applicability: Works on graphs with negative edge weights and can detect negative weight cycles.

• Time Complexity: O(V*E), where V is the number of vertices and E is the number of edges.

• Functionality: It calculates the shortest path from a single source vertex to all other vertices by relaxing all edges repeatedly over V−1 iterations.

dictionary/map description

A _____ (in Python) or ___ (in many other programming languages) is a data structure that stores key-value pairs, where each unique key maps to a specific value. __________ provide efficient insertion, deletion, and lookup operations, typically in O(1) time on average due to the underlying hash table implementation.

Key Operations in a Dictionary/Map

Insertion

Description: Adding a new key-value pair to the dictionary.

Lookup (Access)

Description: Retrieving the value associated with a given key.

Deletion

Description: Removing a key-value pair from the dictionary.

Update

Description: Updating the value associated with a given key.

Check Existence

Description: Checking if a key exists in the dictionary.

Iteration

Description: Iterating over keys, values, or key-value pairs in the dictionary.

Get Method

Description: Retrieving the value associated with a given key, with an optional default if the key doesn’t exist.

Length

Description: Getting the number of key-value pairs in the dictionary.

Clearing

Description: Removing all key-value pairs from the dictionary.

Copying

Description: Creating a shallow copy of the dictionary.

Pop

Description: Removing a key from the dictionary and returning its value.

Popitem

Description: Removes and returns an arbitrary key-value pair as a tuple (key, value).

Setdefault

Description: Returns the value of a key if it exists; otherwise, inserts the key with a specified value and returns that value.