Algorithms and Data Structures Review Flashcards

Vocabulary-style flashcards covering algorithm fundamentals, complexities, graph theory, sorting algorithms, and problem-solving techniques like dynamic programming and backtracking.

Algorithm

A step-by-step procedure used to solve a problem or perform a task.

Characteristics of a Good Algorithm

It should be correct, efficient, clear, finite (must stop), and easy to understand.

Time Complexity

The measure of how much time an algorithm takes to execute.

Space Complexity

The amount of memory required by an algorithm during execution.

Big-O Notation

A notation used to represent the efficiency of an algorithm in terms of time or space complexity.

Graph

A collection of vertices (nodes) and edges connecting them.

Weighted Graph

A graph in which edges have weights or costs assigned to them.

Spanning Tree

A tree that connects all vertices of a graph without cycles.

Minimum Spanning Tree (MST)

A spanning tree with the minimum total edge weight.

Prim's Algorithm

A greedy method used to find the minimum spanning tree by selecting minimum-cost edges.

Kruskal's Algorithm

A greedy algorithm that finds the minimum spanning tree by selecting edges in increasing order of weight.

Cycle Detection in Kruskal's

A process needed to avoid forming loops and ensure a valid spanning tree.

Floyd's Algorithm

An algorithm that finds the shortest paths between all pairs of vertices in a graph.

Warshall's Algorithm

An algorithm used to find the transitive closure of a graph.

Transitive Closure

A representation showing whether a path exists between every pair of vertices in a graph.

Dijkstra's Algorithm

An algorithm that finds the shortest path from a source vertex to all other vertices.

Dijkstra's Algorithm Failure Condition

It fails for negative edge weights because they may give incorrect shortest paths.

Time Complexity of Dijkstra's (Adjacency Matrix)

$$O(V^2)$$

Topological Sorting

The linear ordering of vertices in a directed graph.

Directed Acyclic Graph (DAG)

A directed graph with no cycles.

0/1 Knapsack Problem

A problem where an item is either completely included or excluded from the knapsack, solved using dynamic programming.

Dynamic Programming

A method of solving problems by breaking them into smaller subproblems and storing results.

Fractional Knapsack

A problem where items can be taken partially, solved using the greedy method.

Selection Sort

A sorting algorithm that repeatedly selects the smallest element and places it in the correct position.

Selection Sort Time Complexity

$$O(n^2)$$

Quick Sort

A divide-and-conquer sorting algorithm that uses a pivot element.

Quick Sort Average-case Complexity

$$O(n \log(n))$$

Quick Sort Worst-case Complexity

$$O(n^2)$$

Merge Sort

A stable divide-and-conquer algorithm that divides and merges sorted arrays with a time complexity of $O(n \log(n))$.

Recursion

A process where a function calls itself.

Backtracking

A method of solving problems by trying solutions and undoing wrong choices.

N-Queens Problem

The problem of placing $N$ queens on a chessboard so that no two queens attack each other.

N-Queens Worst-case Complexity

$$O(N!)$$

Sum of Subsets Problem

The problem of finding subsets whose sum equals a given target value.

State-Space Tree

A tree representing all possible solutions of a problem.

Greedy vs. Dynamic Programming

Greedy makes local optimal choices, while dynamic programming solves subproblems and stores results.

BFS (Breadth-First Search)

An exploration method that visits nodes level by level.

DFS (Depth-First Search)

An exploration method that explores deeply before backtracking.

Adjacency Matrix

A 2D array used to represent graph connections.

Adjacency List

A method of storing connected vertices as lists.

Priority Queue

A data structure where elements are served based on priority.

Algorithm Analysis

The evaluation of an algorithm to determine efficiency in terms of time and memory usage.