Homework Solutions for Design Algorithm Course as Computer Science B.Sc. Student at Department of Mathematical Sciences, Sharif University of Technology.
Spring 2023
Supervisor: Dr. Shahram Khazaei
This repository includes my homework and projects around Algorithms and Data structures.
Each problem has a PDF file describing the problem in Persian in the format of a story. Algorithms are supposed to be fast and efficient to accept the original problem restrictions.
| Problem | Description |
|---|---|
| BalancedParanthesisMinimumSwapsCounter | Finding minimum swaps needed to balance an input string of parentheses |
| ClosestPointsFinder | Finding closest points on a 2d plane with different data structures in O(n log n) |
| DiversityCoefficientFinding | Calculating Diversity Coefficient among a group of singers in a singing competition |
| FarthestNodeFinder | Finding the farthest node from the given starting node using Dijkstra |
| LongestCommonIncreasingSubsequence | Finding Longest Common Increasing Subsequence between two strings using Dynamic Programming |
| MaximumVerticalMarginClassifier | a simple sudo SVM Classifier which only considers vertical distance (solved by LP) |
| RookPlacingwithinAllowedArea | Placing Rooks in an N*N chess board in which each rook is allowed to place only in a specified area without threatening other rooks |
| SafeMST | indicates that a list of edges are all part of the MST of the given graph using some sudo-kruskal algorithm |
| SafePathFinder | indicates that there is a safe path between the start and end point in a graph which has some unsafe edges |
| ShortestPathesToGraphBuilder | Given a list of shortest path lengths between vertices and trying to make the smallest graph with these properties |
| TreeSplittingCounter | Given a tree, trying to count all combinations of splitting this tree with some restrictions |
There is some theoretical homework along with my solutions around the algorithm topics. (my answers may be incorrect!) sourcebook of the course:
Algorithms
Book by Christos Papadimitriou, Sanjoy Dasgupta, and Umesh Vazirani
The problems are in Persian but my answers are in English.