C949 V4 Full Study Guide

Finiteness (Characteristic)

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 (Characteristic)

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

Input (Characteristics)

An algorithm requires one or more inputs. The values that are first supplied to the algorithms before its processing are known as inputs. These inputs come from a predetermined range of acceptable values

Output (Characteristics)

One or more outputs must be produced by an algorithm. The output is the outcome of the algorithm after every step has been completed. The relationship between the input and results should be clear

Effectiveness (Characteristics)

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 opertation in the algorithm should be doable and practicable.

Generality (Characteristic)

Rather than being limited to a signle 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 (Factors)

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 (Factors)

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 (Factors)

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 (Factors)

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

Robustness (Factors)

Robustness refers to an algorithm's ability to define your problem clearly

User-friendly (Factors)

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

Simplicity (Factors)

If an algorithm is simple, it is simple to understand

Extensibility (Factors)

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

Brute Force Algorithm (Type of Algorithm)

A straightforward approach that exhaustively tries all possible solutions, suitable for small problem instances but may become impractical for larger ones due to its time complexity

Recursive Algorithm (Type of Algorithm)

A method that breaks a problem into smaller, similar subproblems and repeatedly applies itself to solve them until reaching a base case, making it effective for tasks with recursive structures

Encryption Algorithm (Type of Algorithm)

Utilized to transform data into a secure, unreadable form using cryptographic techniques, ensuring confidentiality and privacy in digital communications and transactions

Backtracking Algorithm (Type of Algorithm)

A trial-and-error technique used to explore potential solutions by undoing choices when they lead to an incorrect outcome, commonly employed in puzzles and optimization problems

Searching Algorithm (Type of Algorithm)

Designed to find a specific target within a dataset, enabling efficient retrieval of information from sorted or unsorted collections

Sorting Algorithm (Type of Algorithm)

Aimed at arranging elements in a specific order, like numerical or alphabetical, to enhance data organization and retrieval.

Hashing Algorithm (Type of Algorithm)

Converts data into a fixed-size hash value, enabling rapid data access and retrieval in hash tables, commonly used in databases and password storage

Divide and Conquer Algorithm (Type of Algorithm)

Breaks a complex problem into smaller subproblems, solves them independently, and then combines their solutions to address the original problem effectively

Greedy Algorithm

Makes locally optimal choices at each step in the hope of finding a global optimum, useful for optimization provlems but may not always lead to the best solution

Dynamic Programming Algorithm (Type of Algorithm)

Stores and reuses intermediate results to avoid redundant computations, enhancing the efficiency of solving complex problems

Randomized Algorithm (Type of Algorithm)

Utilizes randomness in its steps to achieve a solution, often used in situations where an approximate or probabilistic answer suffices.

Recursive Algorithms

A recursive algorithm is one that solves a problem by breaking it down into smaller instances of the same problem, which it then solves in the same way. This process continues until the problem is reduced to a base case, which is solved directly without further recursion.

Base Case

This is the condition under which the recursion stops. It represents the simplest instance of the problem, which can be solved directly without further recursion

Recursive Case

This is the part of the algorithm that breaks the problem down into smaller instances of the same problem and then calls the algorithm recursively on these smaller instances

Stack (Recursive Algorithms)

Each recursive call is placed on the system call stack. When the base case is reached, the stack begins to unwind as each instance of the function returns its result

Advantages of Recursion

Simplicity: Recursive solutions are often more elegant and easier to understand than their iterative counterparts.

Direct Translation: Some problems are naturally recursive, like tree traversals, making recursion the most straightforward approach

Disadvantages of Recursion

Performance: Recursive algorithms can be less efficient due to the overhead of multiple function calls and potential stack overflow issues for deep recursion.

Memory Usage: Recursion can consume more memory because each function call adds a new frame to the call stack.

When to use recursion

When a problem can naturally be divided into similar sub-problems (e.g., tree traversal, searching algorithms like binary search).

When the recursive solution is significantly simpler or more intuitive than an iterative one.

Linear Search (Concept)

Linear 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.

Time Complexity of Linear Search

O(n), where n is the number of elements in the array

When to use linear search algorithm

When the array or list is small.

When the array is unsorted.

When simplicity is more important than performance.

Binary Search Concept

Binary 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.

Time complexity of Binary Search

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

Linear Search Best Case

O(1) - The target element is the first element

Linear Search Average Case

O(n) - The target element is somewhere in the middle or not in the array

Linear Search Worst Case

O(n) - The target element is the last element or not present

Binary Search Best Case

O(1) - The target element is the middle element

Binary Search Average Case

O(log n) - The target element is not immediateley found but within the sorted array

Binary Search 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 Best Case

O(1) — The target element is exactly where the interpolation suggests

Interpolation Search Average Case

O(log log n) - Uniformly distributed data

Interpolation Search 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. DFS explores as far as possible along one branch before backtracking, while BFS explores all neighbors at the present depth before moving on to nodes at the next depth level.

DFS and BFS Time Complexity

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

DFS/BFS Use Case

Useful for searching nodes in graphs and trees

DFS Best Case

O(1) -The traget node is found immediately

DFS Average Case

O(V+E) - Typically when all nodes and edges must be explored

DFS Worst Case

O(V+E) - The target node is the last one discovered

BFS Best Case

O(1) - The target node is the root or the first node checked

BFS Average Case

O(V+E) - All nodes and edges need to be explored

BFS Worst Case

O(V+E) -The target node is the last one explored

Bubble Sort Distinct Characteristics

Repeatedly swaps adjacent elements if they are in the wrong order.

Simple, but inefficient for large datasets.

"Bubbles" the largest element to the end of the list.

Bubble Sort Use Case

Simple but inefficient for large datasets. Best used for educational purposes or small lists.

Bubble Sort Best Case

O(n) - The array is already sorted (with an optimized version that stops early)

Bubble Sort Average Case

O(n²) - Average case with random elements

Bubble Sort Worst Case

O(n²) - The array is sorted in reverse order

Selection Sort Use Case

Inefficient for large lists, but useful when memory writes are more expensive than comparisons

Selection Sort Distinct Characteristics

● Finds the minimum element and swaps it with the first unsorted element.

● Reduces the problem size by one in each iteration.

● Always performs O(n2) comparisons, regardless of input

Selection Sort Best Case

O(n2) — Selection sort does not improve with better input, always O(n2).

Selection Sort Average Case

O(n2) — Average case with random elements.

Selection Sort Worst Case

○ O(n2) — Selection sort is insensitive to input order

Insertion Sort Use Case

Good for small or nearly sorted lists

Insertion Sort Distinct Characteristics

● Builds a sorted list one element at a time.

● Efficient for small or nearly sorted datasets.

● Shifts elements to make space for the current element

Insertion Sort Best Case

O(n) — The array is already sorted

Insertion Sort Average Case

Average case with random elements

Insertion Sort Worst Case

The array is sorted in reverse order

Merge Sort Use Case

Efficient and stable, good for large datasets

Merge Sort Distinct Characteristics

● Divides the list into halves, sorts each half, and then merges them.

● Stable and efficient for large datasets.

● Requires additional space for merging.

Merge Sort Best Case

O(n log⁡ n) — Merge sort's time complexity is the same in all cases.

Merge Sort Average Case

O(n log⁡ n)

Merge Sort Worst Case

O(n log⁡ n)

Quicksort Use Case

Often faster in practice than merge sort but less stable

Quicksort Distinct Characteristics

● Selects a "pivot" element and partitions the array around it.

● Recursively sorts the partitions.

● Efficient, but can degrade to O(n2) if poor pivot selection occurs.

Quick Sort Best Case

O(n log⁡ n) — The pivot splits the array into two nearly equal halves.

Quicksort Average Case

O(n log⁡ n) — Average case with random pivots.

Quicksort Worst Case

O(n2) — The pivot is always the smallest or largest element, leading to unbalanced partitions.

Quicksort

Look for the keywords "pivot" and/or "split". (Pivot, Split)

Heap Sort Use Case

Useful when memory usage is a concern as it's an in-place algorithm

Heap Sort Distinct Characteristics

Utilizes a binary heap data structure.

Builds a max-heap and repeatedly extracts the maximum element.

Efficient and in-place, but not stable.

Heap Sort Best Case

O(n log⁡ n) — Heap sort's time complexity is the same in all cases.

Heap Sort Average Case

O(n log⁡ n)

Heap Sort Worst Case

O(n log⁡ n)

Heap Sort

Look for code that uses a heap data structure to repeatedly extract the maximum (or minimum) element and rebuilds the heap. (Heapify, Extract Max, Build Heap)

Counting Sort Use Case

Efficient for sorting integers or other items with a small range of possible values

Counting Sort Distinct Characteristics

Non-comparative sorting.

Counts occurrences of each element and uses this information to place elements.

Efficient for small ranges of integers.

Counting Sort Best Case

O(n+k)— k is the range of the input.

Counting Sort Average Case

O(n+k)

Counting Sort Worst Case

O(n+k)

Radix Sort Use Case

Effective for sorting large numbers or strings with a fixed length

Radix Sort Distinct Characteristics

Sorts numbers by processing individual digits.

Non-comparative, stable, and efficient for specific data types.

Often combined with counting sort.

Radix Sort Best Case

O(n*k) — k is the number of digits in the largest number

Radix Sort Average Case

O(n*k)