Archive for 2018

greedy algorithms javascript

Greedy Algorithms

· · Leave a Reply

Now that we understand dynamic programming, let’s dive into greedy algorithms. A greedy algorithm (also used in solving optimization problems) is one that builds a solution in small steps, making a locally optimal choice at each step in hopes that eventually it will find a solution that can be applied globally. So what does all this mean? We call it greedy because, at each step, it makes the most optimal choice (this is what we mean by locally optimal – meaning whatever value I have at this step, is the most optimal). It continually runs (step by step) until the best optimal solution is found overall. Greedy algorithms do not always give the most optimal solutions (they don’t always work). However for many problems they actually do (even nontrivial ones!). Sometimes, this is all you want for a given problem ( an optimal or even suboptimal solution – something that works decently). Sometimes making a decision that looks right at the moment will give you the best solution. But we know this does not always work in the real world. This is what greedy algorithms are all about. Read More

dynamic-programming

Dynamic Programming

· · 2 Replies

From this post onwards, we will be covering advanced algorithms in javascript. We are going to learn about dynamic programming. The definition of this algorithm is a little abstract, and the best way to understand it, is to see it in action. My goal is to make this a great resource for learning how to implement dynamic programming problems in javascript. To understand this algorithm we must first try to understand what optimization problems are. Why? Let’s start off with dynamic programming, which is a way of solving optimization problems by breaking them into smaller subproblems. Read More

Javascript Sorting Algorithms

Sorting Algorithms In Javascript

· · Leave a Reply

In a previous post we learned about searching algorithms. We also learned that sorting is equally important; that sorting and searching go hand in hand. Sorting is deeply embedded in everything we do. Lets define sorting even though we all know what it is. Sorting is simply rearranging elements in a collection in increasing or decreasing order based on a property. That property could be a datatype like string or number. We could even sort based on some complex datatype. So if you have a class with many different properties, we could sort based on those properties. In the real word, we sort cards when we play poker, when buying online we like to search in order of price (sorted from lowest to highest or vice versa), or perhaps even sorting by product number reviews (my favorite type of sort when shopping on amazon). We sort emails, phone contacts, travel dates (you get the picture). Read More

javascript heaps

Javascript Heaps

· · Leave a Reply

Previously in other posts (on data structures) we learned about Queues. Particularly speaking, we discussed what priority queues were. What we didn’t know is that the underlying foundation of priority queue is the heap data structure (which we will be learning about in this post). Remember that a priority queue is a data structure that allows you to access an item in a collection with the highest priority. Accessing such an item can be done in so many different ways such as using arrays or lists (binary trees being one of them). However the best way to implement priority queues is to use the heap. When accessing, inserting or deleting into  such data structures, the heap is the most performant (faster than arrays/lists/binary trees). What we really didn’t talk about in that post (on queues) was runtime complexity. We implemented methods such as enqueue, dequeue, etc. but we never considered how performant they were with basic operations such as adding and removing from the queue. Lets look at a diagram. Read More