CPS616-Algorithms

Lab 1 - Sorting and Problem Size

Comparison of O(n²) algorithms (Selection Sort + Merge Sort). Three cases are tested:

1. Standard Selection Sort
2. Standard Merge Sort
3. Merge Sort with Selection Sort when the subarrays are small enough

Lab 2 - Divide and Conquer

Large integer multiplication, where the result is too large to be stored in regular integer data types. Strings + Vectors are used to represent these large numbers

Lab 3 - Minimum Spanning Trees

Finds the minimum spanning tree of an undirected graph, given as an adjacency matrix using Prim's Algorithm

One thing to note, this version of Prim's is NOT using a binary heap. This is the standard O(|V|²) implementation using an adjacency matrix (which is more rare I think?). Check out the code if you're looking for help on how to implement Prim's using an adjacency matrix.

Lab 4 - Greedy Interval Scheduling

Implements a greedy algorithm for accommodating bookings in a hotel with N rooms

Lab 5 - Dynamic 0/1 Knapsack

Finds an optimal solution to the 0/1 Knapsack problem. Two functions are implemented:

1. The brute force method O(2ⁿ)
2. Dynamic method O(nW) where n = # of items, W = capacity of knapsack