Repository created for the course "Algorithm Design and Analysis" at the Wroclaw University of Science and Technology.
During this course, 3 mini projects will be carried out.
The first project concerns various sorting algorithms, their construction, strengths and weaknesses and exemplary application.
In first project, we will implement such methods as:
- quicksort sorting
- sorting by merging
- introspective sorting
Second project explores the practical implementation and benchmarking of graph algorithms using two fundamental representations: adjacency list and adjacency matrix. The main focus is on Dijkstra’s algorithm for finding shortest paths in weighted graphs with non-negative weights.
Second project includes:
- Implementations of both undirected graph representations (adjacency list and adjacency matrix) in C++.
- Dijkstra’s algorithm for both: all shortest paths from a single source, and the shortest path between two vertices, for each representation.
- Automated benchmarking on randomly generated graphs of various sizes and densities, measuring performance across 100 runs for each configuration.
- Comparative analysis of the results, highlighting how the data structure impacts the efficiency of shortest path algorithms, depending on graph size and density.
- Test driver to visualize and verify correctness for small graphs.