Binomial Heaps
The binomial heap is a heap structure that supports a more efficient union operation than the binary tree. The binomial tree perform a union in time O(log n) while the binary tree does the same in O(n) time. However a trade off of the binomial tree is that finding the minimum takes O(log n) time [...]
Matroids
I will try to define the concepts of matroids in the context of greedy algorithms.
How are matroids relevant to greedy algorithms. Matroids are a structure that always yields the optimal solution when the greedy method is applied to it . Understanding and recognizing when a matroid can be used seem like a good way to [...]
Minimum Spanning Trees
Minimum Spanning Trees
A Spanning tree in a graph is a tree for which all vertexes are connected without forming a cycle
A minimum spanning tree is a spanning tree in a weighted graph with the minimum weight. There could be more than one minimum spanning tree in the same graph
We will discuss two ways [...]
Dynamic Programming
There are 4 basic steps to dynamic programming
1. Establishing the structure of the optimal solution.It seems to me that the structure for the optimal soultion can be obtained by finding a way to describe the problem in the following way: First find sub problems. In what way can the problem be represented where solutions to [...]
Blog for Algorithm Analysis
As part of the requirement of the graduate course for algorithm analysis at UPRM, I was asked to create an educational journal were I can share any insights, questions or links I come across during this course. I will try to update this post with relevant material as often as possible. This is the [...]