Introduction to algorithms

By R. Shyamasundar. 1996

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Autoregressive Entity Retrieval (2020, methodology): “Thus, we define our constrain in terms of a prefix tree T (aka trie) (Cormen et al., 2009) where nodes are annotated with tokens from the vocabulary.”
The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks (2018, methodology): “Concretely, we implement a shortest-path algorithm directly inspired by Dijkstra’s algorithm [11] which computes the shortest distance on a graph with non-negative edge weights.”
A Sentimental Education: Sentiment Analysis Using Subjectivity Summarization Based on Minimum Cuts (2004, methodology): “…can use maximum-ﬂow algorithms with polynomial asymptotic running times — and near-linear running times in practice — to exactly compute the minimum-cost cut(s), despite the apparent intractability of the optimization problem (Cormen, Leiserson, and Rivest, 1990; Ahuja, Magnanti, and Orlin, 1993).”
Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training (2017, background): “radient top-kselection. Given the target sparsity ratio of 99.9%, we need to pick the top 0.1% largest over millions of weights. Its complexity is O(n), where nis the number of the gradient elements (Cormen, 2009). We propose to use sampling to reduce top-k selection time. We sample only 0.1% to 1% ”
Interpreting random forest classification models using a feature contribution method (2013, methodology): “We propose to use DFS (depth first search [9]) to traverse the tree and compute the vector Y n mean once a training set for a node n is determined.”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, methodology): “Our algorithm is based on Kruskal’s method [CLRS01]: we keep adding edges between points in approximately increasing order, and merging components that are connected by the edges.”
Beyond Data and Model Parallelism for Deep Neural Networks (2018, methodology): “Similar to the BellmanFord shortest-path algorithm [14], the delta simulation algorithm iteratively dequeues updated tasks and propagates the updates to subsequent tasks (line 6-14).”
Monocular Object Instance Segmentation and Depth Ordering with CNNs (2015, methodology): “Occasionally clusters need to be merged and we use a union-find data structure to keep track of the equivalence classes [5].”
OFA: Unifying Architectures, Tasks, and Modalities Through a Simple Sequence-to-Sequence Learning Framework (2022, methodology): “To overcome these issues, we introduce a search strategy based on preﬁx tree (Trie, [68]).”
Hash Layers For Large Sparse Models (2021, background): “Hash functions have long been employed throughout Computer Science [13], and can take a variety of forms.”
ORANGE: a Method for Evaluating Automatic Evaluation Metrics for Machine Translation (2004, background): “Given two sequences X and Y , the longest common subsequence (LCS) of X and Y is a common subsequence with maximum length (Cormen et al. 1989).”
Efficient Private Statistics with Succinct Sketches (2015, methodology): “Following the master theorem [21], we know that this process converges in O (log n ) steps, for n elements in the domain of the values/median.”
Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers (2020, methodology): “Unidirectional FAVOR using fast prefix-sum precomputation in parallel [29, 15] has O(MLd) space complexity to store GPS which can be reduced to O(Md+ Ld+ML) by running a simple (though non-parallel in L) aggregation of GPS i,:,: without storing the whole tensor G PS in memory.”
Unsupervised Object Discovery and Tracking in Video Collections (2015, background): “(1) is then efﬁciently optimized by dynamic programming (DP) [6, 26].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “The greedy algorithm is then exactly Kruskal’s algorithm to find maximum weight spanning trees [49].”
A survey of algorithmic recourse: definitions, formulations, solutions, and prospects (2020, background): “A number of heuristics-based approaches are also explored, e.g, finding the shortest path (Dijkstra’s algorithm [46]) between 𝒙 F and potential 𝒙 CF s on an empirical graph where edges are placed between similar instances (according to, e.g., Gaussian kernel) [149].”
An optimal algorithm for approximate nearest neighbor searching fixed dimensions (1998, methodology): “Instead we opted for the much simpler technique of applying a standard partitioning algorithm as used in QuickSort (see [Cormen et al. 1990]).”