All Posts in “Javascript”

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

javascript search algorithms

Searching Algorithms In Javascript

· · Leave a Reply

Searching is fundamental to any programming language. It would be a waste to have data structures, and no way of searching through them. Searching is fundamental in life (we even search for the meaning of our very own existence), so it only makes sense that after we create collections of data, that we want to search through them. By searching we are able to find answers to problems we are trying to solve. Take a phone book for example, or a telephone directory. Most of these come with tools that help make search relatively simple. For example, there are guides within the book that show you which letter you are currently on (making it easy to jump quickly to a section). Read More

Javascript Graph Algorithms

Javascript Graphs

· · 2 Replies

Graphs are mind blowing! The first time i studied graphs and its applications, i was simply in awe. The first thing one might think when they hear graphs is to think of some kind of chart or diagram. But that is not the case. They are actually derived from the study of networks and are an extremely hot topic these days. We have all used graph applications without even realizing it. Social media and social networks (Facebook, Twitter, Instagram, etc), the internet, etc. are applications of Graphs, and are used to model many real world systems, like airlines, road traffic, communication, etc. Graphs also fall under the non-linear data structures, but take things to a whole new level. You can even think of linked lists and the binary tree data structure as a form of graph (so we have been using graph applications without even realizing it). Linked lists have node connections from one node directly to another node, and binary trees have one node which could potentially connect to 1 or a maximum of 2 nodes. With graphs any node could potentially link to another node within the collection. So it is not limited as linked lists or Binary Trees. Lets look at our first graph. Read More

Javascript Binary Search Trees

Javascript Trees

· · 4 Replies

A tree data structure is very similar to a linked list. Where linked lists are linear (meaning we have each node in the collection pointing to a next node in a fixed sequence), a tree data structure is non-linear. This means we can have each node potentially pointing to one or more nodes. Think of a trees as a way to order things hierarchically. Example are, graphical representations of data (like an organizational charts), files in a file system or even sorted collections of data. When working with trees, order of the elements is not important (if it is, you can store your collection in a linked list, stack, queue, etc). Lets take a look at an example of an organizational chart ( a type of tree structure showing hierarchical data ). Read More

javascript hashing

Hashing

· · 2 Replies

In the last post we talked about Maps. We learned that Maps can be referred to as dictionaries, associative arrays, etc. Sometimes you will also hear Maps or Sets being referred to as a Hash ( You will hear  the likes of HashMaps or HashSets ). These types of key/value pair collections, are “Hash-bashed Data Structures”. What is hashing? In my very first post on data structures, i mentioned that Linked Lists are faster at adding data quicker to a collection, than it is at retrieving. Hashing is a way of storing data that makes retrieval and access extremely fast (Runtime complexity of O(1) for both retrieval, access, and deletion operations). Our collection is stored in a data structure known as a hash-table. This table is what makes data retrieval and storage so fast. When we looked at Maps in the last post (or even linked lists), anytime we wanted to find data, we had to traverse the whole collection in order to find it. Given a key, we would enumerate the whole thing for its value.Therefore it would take a long time we had a huge collection. Hash tables can be used to solve this problem. Read More

Javascript Dictionaries / Maps and Sets

Maps (Dictionaries) & Sets

· · Leave a Reply

As we journey down the lane of data structures, you may or may not have noticed a pattern for how we access data. Since the underlying data storage we have used have been arrays, we have had to rely heavily on using numeric type indexing to retrieve values. Even though in stacks and queues we were only interested items at the top or front, indirectly we were still using some sort of indexing to get those item values. Also when we did traversals in our data structure, it was based on indexing. While this has served us well, sometimes you want to put more meaning into how you retrieve values. Asking for items[0], doesn’t really give a clear definition of what is being asked for. Read More

Javascript Queues

Javascript Queues

· · 5 Replies

In the previous chapter, we learned about the Stack data structure. We will be talking about javascript queues in this post. The difference between a stack and a queue is the way items are added and removed. While items in a stack are LIFO collections, items in a queue are FIFO (First In First Out). A queue returns items in the same order it way added. The first to get in, is the first out! Lets see how this relates to the real world. Think of a grocery store or the bank cashier for example. The people who join the line, checkout out in the order they got in. If you are in line first, you get served first. If you are last in line, you are served last. Anyone who enters the bank goes to the back of the line (in queue). The same applies when you tell a printer to print a document. The items to print are queued, and are printed on a first come first serve bases. In software development, queues are used in multi threading and concurrency situations, where tasks that are waiting to be processed, are executed in an order of FIFO.   Read More