Originally published at https://shawnlyu.com on October 27, 2020.
Garbage collection (GC) in Java refers to the automatic process of memory management. In Java, objects are created on the heap, and when some of them are unreferenced/unreachable, garbage collectors will collect them and free up memories. There are four ways in Java to make objects unreachable and ready for the GC:
Notably, JVM runs GC and we cannot expect when it does. However, we can request JVM for GC, but it provides no guarantee that GC will run. …
This is originally posted at https://shawnlyu.com/algorithms/binary-search-find-upper-and-lower-bound/
This post will introduce one specific application of Binary Search, i.e., when you are asked to find the upper or lower bound, or more precisely, when you need to find the maximum of the smallest value or the minimum of the largest value.
Binary Search is an algorithm to search for a target from a sorted array. It selects the middle element in the array and compares it against the target; if they are not equal, it eliminates one half of the array and keeps searching the other half in the same manner(Wikipedia).
The most basic application of it is to find a number or a position from an array. Some practices could be found on…
In computer science, a disjoint-set data structure … is a data structure that stores a collection of disjoint (non-overlapping) sets. … It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set.
Disjoint Set helps to group distinct elements into a collection of disjoint sets. There are two major functions associated with it: finding the set that a given element belongs to and merging two sets into one (Cormen, Thomas H., and Thomas H. Cormen. Introduction to Algorithms). This post will introduce the implementations of two functions union(u,v) and find(p), and provide more details using Leetcode 200. …
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
This post will introduce one of the algorithms to find an MST: Prim. Logics, time/space complexities, and implementations will be provided. Feat. Leetcode challenge 1584. Min Cost to Connect All Points.
Prim’s logic is quite similar to Dijkstra’s algorithm, which also finds the lightest edge greedily. It starts with an arbitrary vertex
v and ends up with a set of edges
A spanning all the vertices. At each step, it would look for the edge that connects
A to an isolated vertex in the graph. …
Originally published at https://shawnlyu.com on August 18, 2020.
Apart from vanilla BFS introduced in Intro to Graph Algorithms — BFS & DFS, there’s another variant of BFS called bi-directional BFS. Instead of searching from source to target, bi-directional BFS starts with the source and the target at the same time, and search the graph simultaneously. The improvement of time complexities is shown as below, as referring to @ Huahua.
Originally published at https://shawnlyu.com on May 29, 2020.
Graphs are a pervasive data structure in computer science, and algorithms for working with them are fundamental to the field.
Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.
Given a graph defined as G=(V,E) which is a set of vertices and edges, we’d be curious about how to represent it and how to search it systematically so as to visit the vertices following the edges. …