CS302 Final Exam - Algorithms Design

A sequence of characters, often used to represent text or data.

A way to decompose a square matrix into the product of a lower triangular matrix (L) and an upper triangular matrix (U).

A matrix where all elements below the main diagonal are zero.

A matrix where all elements above the main diagonal are zero.

A way to find the shortest paths between all pairs of vertices in a graph.

A property of a graph where there is a path between any two vertices.

A graph where each edge has a weight of 1.

A procedure where the Floyd-Warshall Algorithm is used to check for transitive closure in a graph by assigning a weight of 1 to each edge and then comparing the resulting distance matrix to a matrix of all elements less than the number of vertices.

In dynamic programming, you break down a problem into smaller overlapping subproblems, solve each subproblem once, and store the results in a table to avoid redundant calculations. Greedy algorithms, on the other hand, make locally optimal choices at each step hoping to reach the global optimal solution. Greedy algorithms don't store intermediate results and might not always find the best solution.

A problem is in P (Polynomial time) if it can be solved by an algorithm with a running time that's a polynomial function of the input size. NP (Nondeterministic Polynomial time) problems can be verified in polynomial time, but finding a solution might require exponential time. NP-Complete problems are the hardest NP problems, meaning if you find a polynomial-time solution for one, you've solved all NP problems. "P=NP?" asks if all NP problems can be solved in polynomial time. If they are, it has profound implications for cryptography and other fields.

0/1 Knapsack using Dynamic Programming is an approach to solve the knapsack problem where you can either take an item or leave it. It uses a table to store the optimal values for each combination of items and weight capacity. This algorithm achieves the optimal solution.

0/1 Knapsack using Brute Force simply tries every possible combination of items to find the one that maximizes value within the given weight limit. It explores all possible solutions, making it slower but guarantees the optimal solution.

Depth First Search (DFS) explores a graph by going as deep as possible along each branch before backtracking. It uses a stack data structure to keep track of visited nodes.

Breadth First Search (BFS) explores a graph level by level, visiting all nodes at the current level before moving to the next. It uses a queue data structure to manage nodes.

Dijkstra's algorithm is an efficient algorithm to find the shortest path from a starting node to all other nodes in a graph. It works by iteratively selecting the node with the smallest tentative distance and updating the distances of its neighbors.

Bellman-Ford algorithm is another shortest path algorithm that can handle graphs with negative edge weights. It iterates over all edges multiple times, relaxing the shortest path estimates until convergence.