# 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.

7,322 questions
Filter by
Sorted by
Tagged with
35 views

### Job scheduling with minimum makespan

You are given n jobs, m workstations and an n × m two-dimensional task matrix T of the time each job will spend at each workstation. Each job becomes available at a specified time and may be processed ...
100 views

### Scheduling algorithm to minimize the number of late jobs

There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a_i$ and a duration $t_i$. All the jobs share a deadline length $d$ (deadline for each job is $a_i + d$). The problem is to ...
28 views

### Number of ways of tiling a 3*N board with 2*1 dominoes problem

I came across this problem, Tiling with Dominoes and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a ...
36 views

### k-enclosing rectangle in two-colored point set

I was asked to write an algorithm for the following problem, and discuss complexity: There are p points of two colours, black and white, in an n*m grid. Any cell in the grid can contain 0 or ...
65 views

### Find longest path in minimum spanning tree

Given an undirected MST with positive weights how can the longest path be found? Based on the accepted answer in this question Longest path in an undirected tree with only one traversal I've ...
82 views

### Converting a number from N to 0 in binary

Trying to solve this problem since 2 days. Still unable to figure out even a basic approach. Given a number $N$ in binary ($1$ to $10^5$), we need to convert it to $0$ using only 2 operations. ...
39 views

31 views

### Minimize shipping cost based on weight and price constraints

I'm trying to determine the least shipping cost when you have a number of items (each with a weight and a price) that can be combined into the same package. The constraints are as follows: There is a ...
59 views

### Reductions between LIS and LCS

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
52 views

### What algorithm should I use for the following problem?

Suppose we have 2 lists: List $G$: the goal, contains goal items each comes with a specific amount, $$G = \{i_1 \times Item_1, i_2 \times Item_2,\dots, i_n \times Item_n\}$$ List $I$: a list that ...
38 views

### Non consant size alphabet

Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.
110 views

171 views

15 views

### What is the correct way for beta reduction of lambda terms

my answer : (\x.\y.y)(xx) -> (\y.y)x -> y correct answer: (\x.\y.y)(xx) -> (\y.y) I was wondering would it be reduced one by one from left to right ? it seems the correct answer takes the whole (xx) ...
43 views

### In which situation do we choose randomized binary search instead of the normal binary search?

Both randomized and normal binary search takes O(log n) time complexity but why does the randomized version exist? In other words what is the advantage of randomized binary search even if it has same ...
15 views

### Min Cut Algorithm using Randomly inserted directions

I had a question about a different randomized min cut algorithm (I don't think it is as efficient as Karger's algorithm for larger sizes of min cuts but it is more efficient for smaller ones). My ...
33 views

### Is it possible to compute how many iterations this algorithm will take?

I want to know exactly how many iterations it would take this algorithm to terminate. In other words, is there a closed-form solution for the number of iterations? (For my input values, it is always ...
7 views

### Linear time addition of binary numerals using only primitive recursion and case analysis

Given binary numerals encoded like (in Haskell for example): data Bin = Z | T Bin | TI Bin With Z being 0, ...
401 views

### How do we place $8n$ objects in a grid of size $n \times n$?

How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in ...
25 views

### Don't understand minimax algorithm in terms of chess

I'm new to minimax algorithm, but i understand it's entire concepts as it's easy, my biggest issue is understanding it's implementation to my chess game, no internet solution answers this question ...
87 views

### Do all recursive problems have optimal substructure?

I am reading about dynamic programming and I understand the overlapping subproblem requirement but not sure why optimal substructure is explicitly stated. Are there problems that can be solved ...
32 views

### Algorithm To Process Purchases Efficiently and Apply Constraint

I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows: ...
184 views

### The origin of list data structure

Does anyone know when the list data structure was mentioned in computer programming/algorithms? Who gave birth to this list concept?
53 views

### Is purely functional programming in some situations less efficient than imperative programming?

I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that ...
32 views

### Time complexity of finding subsequences of a string segmented into parts

Let $S$ be a string of length $N$, consisting of digits 0 to 9. For convenience, we assume $N$ to be a multiple of 3. Then, we split $S$ into $N/3$ equal parts, each of length 3. For each equal part,...
81 views

### How to check if a list of XY coordinate meet the safety distance to each others?

My background is not CS so sorry for using improper term. But basically I want to check if a point on XY plane is "too close" to any other points, and do so with every points. In another words, if I ...
36 views

### Time complexity of an algorithm for finding a cycle of fixed length

I am considering the following algorithm for obtaining a cycle $C_k$ of fixed length $k$ in an undirected graph $G$. Assuming $G$ is in adjacency list form, say $r \in G$ is the root for a truncated ...
Our task is to color a given $2 \times N$ matrix with two colours red (R) and blue (B) such that no two adjacent cells are blue. For red, there are no restrictions. An example of all possible ...