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.

Theoritical Homeworks