aalhour / c-sharp-algorithms Goto Github PK
View Code? Open in Web Editor NEW:books: :chart_with_upwards_trend: Plug-and-play class-library project of standard Data Structures and Algorithms in C#
License: MIT License
:books: :chart_with_upwards_trend: Plug-and-play class-library project of standard Data Structures and Algorithms in C#
License: MIT License
On the current master 9fc09bd, it seems that these two tests don't pass.
Example code that fails in DLinkedListTest:
/****************************************************************************************/
var stringsIterators = listOfStrings.GetEnumerator();
Debug.Assert(stringsIterators.Current == listOfStrings[0], "Wrong enumeration.");
Example code that fails in SortedDictionaryTests:
Debug.Assert(sortedDict["Bic"] == 12);
Debug.Assert(sortedDict["Carter"] == 13);
The errors were very minor (typos, forgetting to undo updates, etc), so I've fixed them myself.
Would it be okay for me to send a pull request for this?
Hello,
There are many static class
which are testing algorithms and data structures implementations. Why not creating a unit testing project instead (or additionnaly)?
ZwoRmi
looks not any bitmap in this repo.
plan for RoaringBitmap support ?
Create new scope Search (Algorithms), implementing fundamental search algorithms.
Also implement Binary Search.
Reference: https://en.m.wikipedia.org/wiki/Binary_search_algorithm
red back tree :in _adjustTreeAfterInsertion method,I found a problem which in code:
if (currentNode != null && currentNode != Root && _safeCheckIsRed(_safeGetParent(currentNode)))
{
//
// STEP 2.A:
// This is the simplest step: Basically recolor, and bubble up to see if more work is needed.
if (_safeCheckIsRed(_safeGetSibling(currentNode.Parent)))
{
// If it has a sibling and it is red, then then it has a parent
currentNode.Parent.Color = RedBlackTreeColors.Red;//black?
I think right code is currentNode.Parent.Color = RedBlackTreeColors.Black
I think the IsAnagram() method doesn't work as expected. For example, it would fail for the below string combinations ("abc","bbb") or ("acdf", "bcde").
I think a simple LINQ implementation would be easy enough to implement here.
If you like, I could do that and also implement unit tests for it.
I just wanted to say I building at the moment a bit-array.
This bit-array is in namespace DataStructures.BitArray
I hope this is correct.
I put also a Nunit test to it.
Implement the Open-Addressing Hash Table Data Structure.
Top priority goes to implementing the the data structure with Double-Hashing algorithm. Nevertheless, implementing all of the three main Open-Addressing algorithms is always welcome.
The three main Open-Addressing Algorithms:
int midIndex = collection.Count / 2;
var leftCollection = collection.GetRange(startIndex, midIndex);
var rightCollection = collection.GetRange(midIndex, (endIndex - midIndex) + 1);
leftCollection = InternalMergeSort<T>(leftCollection, 0, leftCollection.Count - 1, comparer);
rightCollection = InternalMergeSort<T>(rightCollection, 0, rightCollection.Count - 1, comparer);
No need to invoke GetRange, as it copies the data and consumes extra memory. Passing StartIndex, EndIndex along with the original array should be sufficient. Don't you think so?
Implement the B Tree Data Structure.
Implement the R-Tree Data Structure.
Fix broken DijkstraShortestPaths tests.
To do this fix may require also do some fix in algorithms.
Proposal to implement the Sieve of Atkin algorithm for finding prime numbers. It's more advanced than the Sieve of Eratosthenes, having better run time performance.
Wikipedia: https://en.wikipedia.org/wiki/Sieve_of_Atkin
Hello,
same story just like with RedBlackTree issue, I noticed that not all tests pass.
I would like to work on these tests or implementation depends on what the problem will turn out to be.
I will try to add more test cases.
Related with an earlier reported problem #76
Regards.
I was planning to add this algorith as described in https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Implement the Hilbert R-Tree Data Structure.
Implement the Bloom Filters data structure.
Implement Hashset and return an IEnumerable instead of List implementation to reduce time complexity of solution.
Is your feature request related to a problem? Please describe.
Automatically list new and existing contributors on the README document
Describe the solution you'd like
Use an automated service like contributors-img where the images are listed automatically.
Describe alternatives you've considered
N/A
Additional context
N/A
protected bool _remove(RedBlackTreeNode nodeToDelete)
{
if (nodeToDelete == null)
return false;
// Temporary nodes
RedBlackTreeNode<TKey> node1, node2;
// If nodeToDelete has either one child or no children at all
if (!nodeToDelete.HasLeftChild || !nodeToDelete.HasRightChild)
{
node1 = nodeToDelete;
}
else
{
// nodeToDelete has two children
node1 = (RedBlackTreeNode<TKey>)base._findNextLarger(nodeToDelete);//why is _findNextLarger
}
// Left child case
if (node1.HasLeftChild)
{
node2 = node1.LeftChild;
}
else
{
node2 = node1.RightChild;
}
// If node2 is not null, copy parent references
if (node2 != null)
node2.Parent = node1.Parent;
if (node1.Parent != null)
{
if (node1.IsLeftChild)
{
node1.Parent.LeftChild = node2;
}
else
{
node1.Parent.RightChild = node2;
}
}
else
{
Root = node2;
Root.Parent = null;
}
// Swap values
if (!node1.IsEqualTo(nodeToDelete))
{
nodeToDelete.Value = node1.Value;
}
// Adjust the Red-Black Tree rules
if (node1.Color == RedBlackTreeColors.Black && node2 != null)
{
_adjustTreeAfterRemoval(node2);
Root.Color = RedBlackTreeColors.Black;
}
// Decrement the count
base._count--;
return true;
}
node1 = (RedBlackTreeNode)base._findNextLarger(nodeToDelete); in this code why is find larger but not find smaller.
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html this link shows the process of delete a note,and it process is find a smaller note but not larger note
which is right?
I have implemented an similar IGraph<T>
, which acts like a undirected unweighted graph.
It should be fast at finding paths and other connexity algorimths; but slower at direct manipulation like adding or removing edges.
It stores in memory the clan: the maximal complete subgraphs in ISet<T>
's
If you are interesed i could implement it to your IGraph<T>
interface and merge it.
Hello @aalhour. I am unsure of how to run the unit tests that are placed in the UnitTest folder. In the MainProgram folder I see you have a program.cs that allows you to specify which test(s) to run. How do you accomplish this same task in the UnitTest folder? Thanks!
Implement the B+ Tree Data Structure.
Implement the Ternary Trees Data Structure.
I have written a optimized version of Anagram detecting, do you guys accept optimization?
Before: 2n+2(n log n)+n
After: 3n
Implement the Finger Trees data structure.
Reference: http://www.staff.city.ac.uk/~ross/papers/FingerTree.html.
Hello,
after downloading the repository, I noticed that not all tests pass.
e.g. tests related with RedBlackTree.
I would like to work on these tests or implementation depends on what the problem will turn out to be if nobody else actual work with it?
I can also add some more unit test for that trees.
Regards.
Describe the bug
The README document contains a few issues regarding list formats, e.g.: list sentences ending with a .
character.
To Reproduce
N/A
Expected behavior
List sentences don't end with a .
character.
Write a loop, from 1 to 80000, each time add a random int to the max heap.
In theory it takes very little time(NlogN, N=80000, <1sec ), but the program does take a long time.
I'v also tested the BinaryHeap in https://github.com/SolutionsDesign/Algorithmia, it performs well, so it is probably due to the bad algorithm.
Implement the K-ary Tree Data Structure.
Specifically:
C-Sharp-Algorithms/DataStructures/Graphs/WeightedEdge.cs Line:36
Currently, Travis CI doesn't run tests from the UnitTest project when building the project, I want it to run all tests as part of the build process.
With many vertices and not many edges, the Dijkstra algorithm fails on the following line:
//_edgeTo = new WeightedEdge[_edgesCount];
which now runs with the following line:
_edgeTo = new WeightedEdge[_verticesCount];
Similarly the test for optimality fails in DijkstraShortestPaths with directed edges, I think because code fails due to adding an edge weight to Infinity, when it should not do this for the directed edge when the edge is not in the right direction.
//Debug.Assert(_checkOptimalityConditions(Graph, Source));
(_distances[v] + edge.Value < _distances[w])
infinity + an edge weight will be less than distances[w](infinity + positive number) = small number.
FindGCD() is not working as expected.It runs as infinite loop if I try to find a GCD of 4,5 with value of r =4 everytime.
Hi,
Are there any plans to migrate this project to .net standard and/or have a nuget package?
Hello @karv,
I have added 3 new methods to the IGraph interface.
I have added empty implementations for these methods to the CliqueGraph class, the one you contributed, which throw a "Not Implemented Exception".
I am opening this issue because you are the owner of this class, and now it needs your maintenance.
Running tests on Travis-CI and locally gets aborted due to a weird error. Find the command, environment and stderr output below:
Command:
dotnet test UnitTest/UnitTest.csproj
Error:
The active test run was aborted. Reason: ncTaskMethodBuilder`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Start[[Xunit.Sdk.TestClassRunner`1+<RunTestMethodsAsync>d__38[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]], xunit.execution.dotnet, Version=2.4.0.4049, Culture=neutral, PublicKeyToken=8d05b1bb7a6fdb6c]](<RunTestMethodsAsync>d__38<System.__Canon> ByRef)
at Xunit.Sdk.TestClassRunner`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].RunTestMethodsAsync()
at Xunit.Sdk.TestClassRunner`1+<RunAsync>d__37[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNext()
at System.Runtime.CompilerServices.AsyncTaskMethodBuilder`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Start[[Xunit.Sdk.TestClassRunner`1+<RunAsync>d__37[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]], xunit.execution.dotnet, Version=2.4.0.4049, Culture=neutral, PublicKeyToken=8d05b1bb7a6fdb6c]](<RunAsync>d__37<System.__Canon> ByRef)
at Xunit.Sdk.TestClassRunner`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].RunAsync()
at Xunit.Sdk.TestCollectionRunner`1+<RunTestClassesAsync>d__28[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNext()
at System.Runtime.CompilerServices.AsyncTaskMethodBuilder`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Start[[Xunit.Sdk.TestCollectionRunner`1+<RunTestClassesAsync>d__28[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]], xunit.execution.dotnet, Version=2.4.0.4049, Culture=neutral, PublicKeyToken=8d05b1bb7a6fdb6c]](<RunTestClassesAsync>d__28<System.__Canon> ByRef)
at Xunit.Sdk.TestCollectionRunner`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].RunTestClassesAsync()
at Xunit.Sdk.TestCollectionRunner`1+<RunAsync>d__27[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].MoveNext()
at System.Runtime.CompilerServices.AsyncTaskMethodBuilder`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].Start[[Xunit.Sdk.TestCollectionRunner`1+<RunAsync>d__27[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]], xunit.execution.dotnet, Version=2.4.0.4049, Culture=neutral, PublicKeyToken=8d05b1bb7a6fdb6c]](<RunAsync>d__27<System.__Canon> ByRef)
at Xunit.Sdk.TestCollectionRunner`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].RunAsync()
at System.Threading.Tasks.Task`1[[System.__Canon, System.Private.CoreLib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=7cec85d7bea7798e]].InnerInvoke()
at System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object)
at System.Threading.Tasks.Task.ExecuteWithThreadLocal(System.Threading.Tasks.Task ByRef)
at System.Threading.Tasks.Task.ExecuteEntry()
at System.Threading.Tasks.SynchronizationContextTaskScheduler+<>c.<.cctor>b__8_0(System.Object)
at Xunit.Sdk.MaxConcurrencySyncContext.RunOnSyncContext(System.Threading.SendOrPostCallback, System.Object)
at System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object)
at Xunit.Sdk.MaxConcurrencySyncContext.WorkerThreadProc()
at System.Threading.Thread.ThreadMain_ParameterizedThreadStart(System.Object)
at System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object)
Environment:
macOS Sierra
Case 5 -- could this be a test verification failure?
Xunit.Sdk.TrueException: 'Wrong root.
Expected: True
Actual: False'
Assert.True(avlRoot.Value == 6, "Wrong root.");
The code seems to produce the tree of 5 at L1, 2 and 6 are children of 5 (L2), 1 and 3 are children of 2 (L2), 7 is right child of 6 (L2). This is a valid BST and AVL tree.
The final (expected) tree mentioned in the comments (lines 119-127) is not a proper BST.
Suggest changing the assertions or updating case #5 to set up a tree that does require rebalancing after root node deletion. I can make the change and submit a PR from here.
Implement the R+ Tree Data Structure.
Implement the Suffix Tree data structures.
Hello,
I read that you start this repo as an interview-preparation project. Now, what do you want to do with it? Keep collecting c# implementation of algorithms? It could be nice to share them on Rosetta Code or Wikipedia for example.
Also, I wrote algorithms in C# for learning purpose in this repository. If you want, I can share all of them in a pull request.
Cheers,
Fix broken UndirectedWeightedDenseGraph tests.
To do this fix may require also do some fix in structure.
Implement the Radix Trees Data Structure.
Hello, searching through the repo i stumbled upon this Queue
implementation.
The Queue implementation uses Generics for the values it holds but the container is of type object[]
.
Is there any reason for that?
Could i do my first pull request to make this enhancement?
Thank you for your time.
Implement the B* Tree Data Structure.
The SelectionSort() is not a SelectionSort its a BubbleSort
Implement the R* Tree Data Structure.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.