# Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

821 questions
Filter by
Sorted by
Tagged with
794 views

### Longest Increasing Subsequence

I got no responses on stackoverflow, so I'm asking here: How useful is the LIS (Longest Increasing Subsequence) problem in tackling other CS problems? There are a few algorithms, using patience ...
51 views

### Efficiently compute parallel matrix-vector product for block vectors?

I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product $$w = (E\otimes I_N)v$$ in parallel, where $\otimes$ is the ...
101 views

### Ways to implement a decision making process involving complex rules [closed]

I'm investigating different solutions for solving what looks like a decision making problem. Although the domain I'm working on is different, for the problem at hand, it's quite easy explaining with ...
1k views

### Confusion related to a divide and conquer problem

I have some confusion related to a divide and conquer problem. Here is the problem You’re consulting for a small computation-intensive investment company, and they have the following type of ...
216 views

### Sort binary matrix by swapping columns to make subrectangle of ones with maximum size

We have given binary matrix (matrix containing only 1 and 0) of size $n\cdot m$. We want to order the matrix such that the biggest rectangle containing only ones is with maximum size. For example if ...
91 views

### Computing min and max using median of 3 elements

How can I write an O(n)-time algorithm to find the minimum and maximum, given a list of n elements drawn from a totally ordered set using the subroutine median3(x,y,z) which returns the index of ...
708 views

### Minimal set of rows and columns covering all non-zero entries in matrix

Given a matrix $A \in \{0,1\}^{n \times n}$, use network flows to describe an algorithm that finds the minimal set $I$ of rows and columns such that any non-zero entry is in one of the rows or columns ...
123 views

### Given a directed graph and a vertex v, find all cycles that go through v? [duplicate]

Given a set of uniquely numbered items that each has three attributes id, from and two in ...
52 views

### Help in geometrically understanding “Linear Decision Trees”

In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as deﬁning a hyperplane in $R^n$. Thus, tracing a path through the tree computes ...
3k views

### Interval Scheduling Problem with more than One Resource

Consider the interval scheduling problem, see also here. In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest ...
2k views

### Shortest Path using DFS on weighted graphs

I read that shortest path using DFS is not possible on a weighted graph. I pretty much understood the reason of why we can't apply on DFS for shortest path using this example:- Here if we follow ...
1k views

### Community detection in weighted directed graphs for fixed number of communities

I have a weighted directed graph $G=(V,E)$ with positive weights. Say these vertices represent cities and the weight $w : V_1 \rightarrow V_2$ represents number of students moving into other cities ...
605 views

### Why can't we just use preorder traversal to check if a tree is subtree of binary tree?

Is preorder traversal enough to check if a tree is subtree of a binary tree? Are there any scenarios which I can miss if I use just the preorder traversal? What other methods can be used to check if ...
32 views

### Classification with optional/catchall attributes

Context Let $S$ be a set of objects, each object $S_k$ containing a set of attributes $A_k\subseteq A$, where $A$ is a global set of attributes. Suppose each attribute $a_k\in A$ can take on integer ...
559 views

### Probability that a random hash from a universal family is injective

This is a homework question, I don't want an actual answer, but rather guidance on how to obtain the correct answer. The question is as follows: In class we saw universal hashing as the solution to ...
1k views

### Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms

The main difference between Dijkstra algorithm and Bellman Ford algorithm that all texts (including CLRS) specify is that Dijkstra's algorithm need all non negative edge weights, while Bellman Ford ...
140 views

### Working out the connectives (And, Or, Not) in a Truth Table that has the outputs [duplicate]

I don't understand how to work backwards to work out a truth table that has been filled out already (I don't know the logical operators). E.g P | Q | Output 1 | 1 | 1 1 | 0 | 0 0 | 0 | 0 0 | 1 | 0 I ...
43 views

### Algorithm to extract line-like contour in 3d

Hello people on the internet, I'm currently searching for some kind of fast algorithm that allows me to extract curves in three dimensional space that arise as the intersection of two level sets of ...
183 views

### How to find polygons overlap reign

I have an algorithmic problem. I have a set of different polygons in the 2D space. Each polygon is represented according to its vertex representation (x and ...
498 views

### What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

From wikipedia In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the length of the input (the number of bits required ...
2k views

### How to draw a graph to disprove this statement?

The Problem: Indicate whether the following statements are true or false: a. If e is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum ...
80 views

### Known algorithms: subgraph with highest/lowest diameter?

Let be $G=(V,E)$ a directed graph without self loops, where each node has an out-degree of at least $k$. We want to find a $E'\subset E$, so that $G'=(V,E')$ has the following properties: Almost all ...
1k views

### Best way to merge 2 max heaps into a min heap

Assume we have 2 max heaps, each with n nodes. We want to merge these 2 heaps and build a min heap. What is the best way to do this? The easiest way is to consider 2 max heaps an array with $2n$ ...
583 views

### Which of the following problems can be reduced to the Hamiltonian path problem?

I'm taking the Algorithms: Design and Analysis II class, one of the questions asks: Assume that P ≠ NP. Consider undirected graphs with nonnegative edge lengths. Which of the following problems ...
173 views

### Total Number of Bits Needed to Represent a List of N elements

This is an excerpt from the algorithms textbook How to Think About Algorithms by Jeff Edmonds (This book is a gem by the way). I get his conclusion about Merge/Quick/Heap sorts having $O(NlogN)$ ...
383 views

### Proving correctness of search algorithms

I've seen correctness proofs for other searching algorithms; however, for this particular algorithm: search in a row-wise and column wise sorted matrix, I'm not able to generate a proper proof. ...
570 views

956 views

### Evaluating Statements Using a Parse Tree

I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, ...
546 views

### A special case for the subset sum problem: selecting from powers of two

Given a multiset $X=\{x_1,\dots,x_n\}$ where every element $w_i$ is a power of two, and given an integer $M$, I'd like to determine if there is any subset of $X$ that sums to $M$. (This question is ...
Given two DFA's , $M_1$ and $M_2$, I want to create an algorithm that determines if their languages are disjoint or not. The algorithm will run in polynomial time. My idea is this: Let's say WLOG ...
We have $n$ integers with lot's of repeated numbers. In this list, the number of distinct elements is $O(\log n)$. What's the best asymptotic number of comparisons for sorting this list? Any idea or ...