This repository contains a collection of programming problems for the Algorithm Design and Analysis Laboratory at our faculty. These problems are designed to teach students about various algorithmic techniques and data structures and the majority of the implementations provided in this repository are written in Java.
Requirements and explanations are included at the beginning of each program.
The following topics are included in this repository:
-
Binary Search Trees: Operations such as: walks, finding the height of a tree, searching for a key, finding the successor of a node, but also design exercises like: determining if a tree is perfectly balanced, checking if exist two nodes with the sum equal to a given s, printing the paths with sum s, printing the levels, creating a balanced BST from a sorted array.
-
AVL Trees: Implementation of insertion into a balanced AVL tree (comparison between BST and AVL: insertion time of the nodes and search time).
-
Trie Trees: Implementation of insertion of a new word to the tree, printing (in alphabetical order) all the words contained by the tree.
-
Design By Induction: Implementation of various algorithmic problems using the design-by-induction technique, including the Successful Party Problem, Celebrity Problem, and Skyline Problem (Manber).
-
Prim's Algorithm: Implementation of Prim's algorithm for finding the minimum spanning tree of a weighted undirected graph using distance arrays in Java.
-
Kruskal's Algorithm: Implementation of Kruskal's algorithm to determine the Minimum Spanning Tree Forest of a weighted undirected graph with N nodes.
-
Dynamic Programming: Reducing the time complexity by applying Dynamic Programming techniques, such as eliminating recursion and applying memoization (Rod Cutting problem from CLRS - chapter 15.1, Longest Common Subsequence problem)
-
Shortest Path Algorithms: Shortest paths in directed graph with positive weights - Dijkstra Algorithm; shortest paths in directed graph with negative weights - Bellman-Ford Algorithm
This repository encompasses essential notions in the field of computer science, providing a strong foundation for designing algorithms and solutions that are both correct and efficient.