Selection Sort and Swap Function Basics

A built-in data type for storing and manipulating sequences of characters. For example, a string variable can hold a word, a sentence, or even a paragraph.

A directive that instructs the compiler to include the contents of a specific header file. This allows the program to access additional functionalities and standard components.

A named block of code designed to perform a specific task. Functions help break down complex programs into smaller, reusable components.

A C++ keyword that creates an alias for a data type, allowing you to give it a more descriptive name.

A sorting algorithm that repeatedly finds the minimum element in the unsorted part of the array and swaps it with the first element of the unsorted part.

A programming technique that breaks down a problem into smaller, similar subproblems and then combines the solutions to those subproblems to solve the original problem.

A method for solving optimization problems by making locally optimal choices at each step, with the hope of arriving at a globally optimal solution.

A technique for solving problems that exhibit overlapping subproblems by storing the results of subproblems to avoid redundant computations.

A network flow problem involves finding the maximum flow of some commodity through a network, where each edge has a capacity limiting the flow on that edge.

In algorithms, recurrence relations are mathematical formulas that define a sequence of numbers based on previous terms in the sequence. They are often used to analyze the running time of recursive algorithms.

A directed spanning tree that connects all vertices in a graph with the minimum possible total edge weight.

A sequence alignment algorithm aims to find the best possible alignment between two biological sequences, revealing similarities and differences.

A way to represent relationships between objects, like people or locations. It consists of nodes, representing the objects, and edges, representing connections between them. Think of a social network connecting friends, or a map linking cities with roads.

A set of objects within a graph, representing individual elements. They are often visually depicted as circles in a graph visualization.

Connections between nodes in a graph, representing relationships between elements. Visualized as lines connecting nodes in a graph.

A fundamental scheduling problem where you have a resource, and multiple requests to use it, each with a start and finish time. The goal is to accept as many requests as possible without overlap.

A set of requests in the Interval Scheduling problem that can be accepted without any overlap. They represent a valid schedule.

In Interval Scheduling, when two requests can be scheduled without overlap, either the first request ends before the second starts, or vice versa.

A problem where you need to find the shortest route between two points in a graph. Each edge can have a weight (like distance or travel time). The goal is to find the path with the least total weight.

Similar to Shortest Path, but the goal is to find the path that minimizes the total cost (weight) of traveling through a specific set of locations within the graph. For example, finding the most cost-effective way to visit all towns in a region.

In this problem, finding a winning strategy for P2 is computationally difficult even for a reasonably sized graph. It requires a lengthy case-by-case analysis to convince someone that P2 has a winning strategy.

Determining if a player in a game has a winning strategy can be difficult, and there might not be a short or easy way to prove it.

A problem is PSPACE-complete if it's as complex as the most difficult problems solvable with limited memory. It's generally believed that PSPACE-complete problems are harder than NP-complete problems.

Competitive Facility Location is an example of a PSPACE-complete problem. It's considered to be very challenging to solve due to its computational complexity.

Many real-world problems, like game-playing and planning, belong to the class of PSPACE-complete problems. Solving them often involves dealing with complex strategies and decision-making under uncertainty.

In contrast to PSPACE-complete problems, checking the validity of a solution for an NP-complete problem is relatively straightforward.

The Independent Set Problem is an example of an NP-complete problem, where finding a solution can be hard, but verifying a proposed solution is relatively easy.

Finding a solution for a PSPACE-complete problem may not have a short or easy proof, which means it's difficult to convince someone that a particular solution is correct.