725G97 - Data Structures and Algorithms

Overview

This repository contains the work completed during the 725G97 Data Structures and Algorithms course at Linköping University. The course covers key concepts in algorithm design and analysis, data structures, and algorithmic problem-solving techniques, including:

• Algorithm design and analysis: Techniques for designing efficient algorithms and analyzing their time and space complexity (e.g., Big O notation).

• Data structure implementation and optimization: Implementing and optimizing fundamental data structures like linked lists, stacks, queues, trees, and hash tables for various use cases.

• Sorting, searching, and graph algorithms: Exploring common algorithms for sorting (e.g., quicksort, mergesort), searching (e.g., binary search, linear search), and graph-related problems (e.g., depth-first search, breadth-first search, Dijkstra’s algorithm).

• Time complexity and efficiency: Evaluating the performance of algorithms through time and space complexity analysis, and optimizing them to solve problems effectively within resource constraints.

Labs

• Lab 1: In this lab, we implemented a hash table, exploring different hashing techniques and resolving collisions. The exercise aimed to understand how hash tables work under the hood and the impact of various hash functions on the performance of insertion, search, and deletion operations.

• Lab 2: This lab involved implementing an AVL tree, a type of self-balancing binary search tree. The task included implementing rotations to maintain balance during insertions and deletions, while ensuring optimal time complexity for search, insert, and delete operations.

• Lab 2.5: In this exercise, we built a priority queue to manage events in a particle simulation. This lab required us to implement a priority queue efficiently and use it to handle the simulation's event scheduling based on the priority of each event.

• Lab 3: This lab focused on developing an algorithm to find points on a 2D plane that satisfy certain geometric properties and drawing lines between them. It involved working with computational geometry techniques to process and visualize the data in a graphical representation.

• Lab 4: he goal of this lab was to develop an algorithm capable of identifying the longest chain of words, where each word in the chain can be formed by changing exactly one character from the previous word. The focus was on optimizing the algorithm to ensure its efficiency when handling large datasets.