Design Algorithms
Homework Solutions for Design Algorithm Course as Computer Science B.Sc. Student at Department of Mathematical Sciences, Sharif University of Technology
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
Description
This repository includes my homework and projects around Algorithms and Data structures.
Table of Coding Problems
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 |
Theoretical Problems
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.