DESCRITPION

SharpAlgos is an collection of Algorithms and Data Structures written in C# 11

Your contribution is welcome.

Requirements:

• Visual Studio 2022
• .Net Core 7

DATA STRUCTURES

Priority Queues:

• Min & Max Priority Queue

Range Queries:

• Sparse Table
• Segment Tree (with range updates)

Others:

• TRIE
• Ternary Search Tree
• Interval Tree
• Union Find
• Cartesian Tree

ALGORITHMS

Graphs:

• Shortest/Longest Paths:
  • Depth First Search
  • Breadth First Search
  • Dijkstra
  • Bellman Ford
  • Floyd Warshall
• Cycles:
  • All Cycles Detection (using Johnson Algo)
  • Negative Cycle Detection
  • Cycle with Minimum Average Weight
  • Tramp Steamer Problem
• Strongly Connected Components
• Minimum Spanning Tree
• Topological Sort
• Tree
  • Lowest Common Ancestor (LCA)
• Euler Path
• Hamiltonian Path
  • Travelling Salesman Problem
  • Bitonic Tour
• Bipartire Graph
  • Maximum Matching
  • Perfect Matching : optimizing total cost of Matching
  • Perfect Matching : optimizing min/max cost of Matching
• Flows:
  • Maximum Flow (using Edmond Karp algo)
  • Minimum Cut
• 2SAT Problem

Strings:

• Edit Distance (with insertion, deletion, substitution and transposition)
• Nearest word in a dictionary
• Longest Common Subsequence (LCS)
• All Longest Common Subsequence
• Shortest Common Supersequence (SCS)
• Longest Repeated Subsequence
• Longest Palindromic Subsequence
• Longest Palindrome
• Longest Common Substring

Integer Array:

• Maximum Sub Sum
• Maximum Sub Sequence Sum with no adjacent element
• Largest Rectangle Area in a Histogram
• Minimum Sum Partition
• Longest Alternating Subsequence
• Longest Increasing Subsequence (LIS)
• Longest Bitonic Subsequence

Geometry:

• Convex Hull
• Area of a polygon
• Nearest Points (minimum distance between a set of points)
• Farthest Points (maximum distance between a set of points)
• Smallest circle including a set of points

Boolean Matrix:

• All connected areas
• Maximal square
• Maximal rectangle

Integer Matrix:

• Maximum Submatrix Sum

Math:

• Greatest Common Divisor
• Multiplicative Inverse
• Prime Check
• Prime Factorization
• Sieve of Eratosthenes

Board Games:

• N Queen Problem
• Knight Probability

Arrays:

• Duplicate detection in intervals

Coin changes:

• Minimum Coin change-making problem
• Same but with infinite number of coins
• Number of distinct ways to achieve a target amount

Stock Prices:

• Max Profit if only 1 transaction allowed
• Max Profit with infinite number of transactions
• Max Profit with at most K transactions

Others:

• Knapsack
• All Permutations
• All Combinations
• Stable Mariage Matching using Gale-Shapley algo
• Optimal Matrix Chain Multiplication