RUNTIME RUSH: Algorithms Practice and Worksheet

This set of flashcards covers vocabulary and key concepts from the CS0007 Algorithm modules including Introduction, Analysis, Brute Force, Divide and Conquer, Decrease and Conquer, Transform and Conquer, Greedy Algorithms, and Dynamic Programming.

Algorithm

A sequence of unambiguous instructions for solving a problem.

Finiteness

The property that an algorithm must terminate after a finite number of steps.

Implementation of an algorithm

The step that involves translating each step of an algorithm into code.

Pseudocode

A high-level description of an algorithm without syntax restrictions.

Program testing

The primary purpose is to find errors in the program.

Time complexity

The relationship between input size and the number of steps required.

Sieve of Eratosthenes

An algorithm used for generating a list of prime numbers.

Euclid’s algorithm

An algorithm used to find the greatest common divisor (GCD) of two numbers.

Stack

A data structure that follows the LIFO (Last-In, First-Out) principle.

Graph

In computer science, a collection of points called vertices connected by edges.

Tree

A connected acyclic graph.

Maximum edges in an undirected graph

$\frac{n(n-1)}{2}$ where $n$ is the number of vertices.

Height of a tree

The length of the longest simple path from the root to a leaf.

Recursion

A process where a function calls itself directly or indirectly.

Base case

A condition in a recursive function defined primarily to avoid infinite loops.

Tail recursion

Occurs when the recursive call is the last operation performed in the function.

Big Oh (O) notation

Asymptotic notation that represents the worst-case scenario of an algorithm's running time.

Space complexity

The amount of memory required by an algorithm to run.

Binary search time complexity

$O(\log n)$ in a sorted array of size $N$.

Indirect recursion

Occurs when a function calls another function that later calls the original function.

Big Omega (\Omega) notation

Represents the lower bound of an algorithm's running time.

Brute-force approach

A straightforward approach based directly on the problem's statement and definitions.

Traveling Salesman Problem

A problem involving finding the shortest tour that passes through all cities exactly once.

Hamiltonian circuit

A path that visits all cities exactly once and returns to the starting city.

Nearest Neighbor Algorithm

An algorithm commonly used as a heuristic for solving the Traveling Salesman Problem.

Exhaustive search efficiency (Knapsack)

$\Theta(2^n)$ is the efficiency for the exhaustive search approach to the Knapsack Problem.

Divide and Conquer

An algorithm design idea involving dividing a problem into smaller sub-problems, solving them independently, and combining their solutions.

Merge Sort

A sorting algorithm that uses the Divide and Conquer approach with a worst-case time complexity of $O(n \log n)$. child subtrees of any node differ by at most one.

Pivot

In Quick Sort, a value used to partition the array into two parts: one with smaller values and one with larger values.

Strassen’s Matrix Multiplication

An algorithm for matrix multiplication that reduces recursive calls and has a time complexity of $O(n^{2.8074})$.

Decrease and Conquer

An algorithm strategy that exploits the relationship between a problem and its smaller instance.

Breadth First Search (BFS)

A traversal method that explores all neighbors at the present depth before moving to the next level, often using a queue.

Depth First Search (DFS)

A graph traversal algorithm that uses a stack explicitly or implicitly and has a time complexity of $O(V + E)$. child subtrees of any node differ by at most one.

Transform and Conquer

An algorithm strategy focused on transforming a problem into a simpler or more convenient form.

AVL tree

A balanced binary search tree where the heights of the two child subtrees of any node differ by at most one.

Balance factor (AVL)

$Height(\text{left-subtree}) - Height(\text{right-subtree})$.

Gaussian elimination

A technique for solving systems of linear equations by transforming a matrix into a triangular form using elementary row operations.

Greedy algorithm

An algorithm that makes the locally optimal choice at each stage.

Minimum Spanning Tree (MST)

A tree that connects all vertices with the minimum total edge weight.

Dijkstra's Algorithm

A greedy algorithm invented by Edsger W. Dijkstra to find the shortest path from a single source node to all other nodes in a graph.

Prim's Algorithm

A greedy algorithm that builds an MST by adding the lowest weight edge connecting a vertex in the tree to a vertex outside; complexity is $O(V^2)$ with an adjacency matrix.

Kruskal's Algorithm

An MST algorithm that builds the tree one edge at a time by processing edges in ascending order of weight, with a complexity of $O(E \log E)$. child subtrees of any node differ by at most one.

Dynamic Programming

A method for solving problems by breaking them into overlapping sub-problems and storing their results to avoid repeated calculations.

Memoization

Storing the results of expensive function calls and reusing them when needed in Dynamic Programming.

Floyd-Warshall algorithm

An algorithm used for finding the shortest paths between all pairs of vertices in a graph with a complexity of $O(n^3)$. child subtrees of any node differ by at most one.

Tower of Hanoi minimum moves

The minimum number of moves required to solve the puzzle with $n$ disks is $2^n - 1$.