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.

Filter by
Sorted by
Tagged with
0
votes
0answers
5 views

data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure need to support the following operations

I've got this question from an exercise and i'm not sure if it is possible to do so Think of new data structure Q with priotry queue which allow us to find the median in $O(1)$ and the data structure ...
0
votes
2answers
12 views

PRECISE DPLL algorithm definition

I am confused about the precise definition of the DPLL algorithm. Various sources tend to define DPLL differently: In pages 110-114 of the book Handbook of Satisfiability(Editors: Biere, A., Heule, M....
0
votes
1answer
7 views

Find sets of weighted objects to maximize number of sets with weight >= X

I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
-1
votes
0answers
23 views

Minimum cost problem of breaking containers in O(nlogn)

Can anyone kindly give me some hint on solving this? There are $n$ water containers placed on the top of each other ($container_1$ on top of $container_2$, $container_2$ on top of $container_3$, ...), ...
-1
votes
0answers
8 views

How can I shove that L is not regular in the language [duplicate]

How can I show that the language 𝐿 = {π‘Ž 𝑛, 𝑛 𝑖𝑠 π‘Ž π‘π‘’π‘Ÿπ‘“π‘’π‘π‘‘ π‘ π‘žπ‘’π‘Žπ‘Ÿπ‘’} is not regular
1
vote
1answer
24 views

Greedy algorithm for problem asking for solution of size *at most* $k$

Given an integer $k$ and a complete weighted bipartite graph with sides $A,B$ in which the weight of the edge $(i,j)$ is $c_{ij} \geq 0$, we want to find a set $S$ of at most $k$ edges that maximizes $...
0
votes
1answer
18 views

Linear programming reduce errors

Most normal linear programming problems look like this: We choose some point in the double shaded area that solves our optimizer and we're good to go. However, I've come across a problem where it's ...
0
votes
0answers
6 views

How can I create an algorithm in pseudo-code generating a sequence of numbers in such an order that they only are different at one position by 1?

Let's say we want to create sequences of the numbers {0,1,2} which are all at length n What I want to create is an algorithm which generates (and outputs) such sequences that they are only different ...
0
votes
0answers
16 views

Two-Sum - Many Sums Algorithm Design Refactor

🧩 How to convert a two-sum item solution to have as many items as possible based on a given total capacity and optimizing for runtime complexity? πŸš€ Original Two-Sum Determine whether there are two ...
0
votes
0answers
17 views

Two-Sum - Range Allowance Algorithm Design

🧩 What is the best way to find a two-sum solution within a range plus/minus of a total capacity provided, optimizing for runtime over memory complexity? πŸš€ Original Two-Sum Determine whether there ...
2
votes
0answers
16 views

Hungarian method: seemingly different algorithms from different sources?

When I look online for examples of the Hungarian method for solving the min-weight assignment problem, for example here, it involves iterating on the cost matrix; subtracting entries from the rows and ...
1
vote
1answer
27 views

Inductive proof for Euclid's algorithm

I'm studying The Algorithm Design Manual and the proof exercises of the first chapter are really hard(at least for a first-timer). I asked a question on here about the previous question in the ...
-4
votes
0answers
53 views

Solve this problem without code ( Move the block : slide puzzle) [closed]

Consider the game Move the Block (gameplay https://www.youtube.com/watch?v=6d0NcUougD4). Move the Block : Slide Puzzle is a simple game whose goal is sliding block puzzle game. The game instructions ...
0
votes
0answers
23 views

Analysis of updating vertex and one example?

I see the following image on google: And I want to find Amortized Cost for Updating of each vertex on Dijkstra algorithm. I have an answer $O(E/V)$. I'm get stuck it means at this answer we should ...
-3
votes
0answers
71 views

Consider the game move the block slide puzzle [closed]

Consider the game Move the Block (gameplay https://www.youtube.com/watch?v=6d0NcUougD4). Move the Block : Slide Puzzle is a simple game whose goal is sliding block puzzle game. The game instructions ...
1
vote
1answer
28 views

Average of all sums of subarrays

I ran into a very hard question. We have array of $n$ integers. for $1 \leq i \leq j \leq n$. we want to set $c_{ij}$= Sum of all values in the range $i$ to $j$ of this array. we want to finding ...
0
votes
1answer
15 views

Choosing the right function

I'm trying to hash integers n = 4k(0,4,8,12,16...) into an array of linked lists of size 4 (chaining). What is a good hasing function that guarantees a good ...
0
votes
0answers
23 views

Algorithm for finding shortest set of paths through a weighted DAG (?)

Short version What algoithm can find an optimal (or near optimal) solution to the following problem? Given the following: a weighted DAG, with one start node (only has outgoing edges) and one end ...
0
votes
0answers
22 views

How does secondary clustering occur in hashing?

One of my friends said me that secondary clustering is the phenomenon occurring when the probe sequence has the same initial value. This definition shows that secondary clustering occurs in linear ...
2
votes
1answer
15 views

What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it. Here is the problem: A company is in ...
1
vote
1answer
16 views

Deterministic algorithms for computational distance between distributions

Computational distance between sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ can be defined as the maximum, over all probabilistic polynomial time algorithms ...
0
votes
0answers
22 views

Evolution strategies for TSP

I'm trying to figure out how evolution strategies would work for the traveling salesman problem. I've done this with the genetic algorithm already, but am curious about how this would be done using ES....
-3
votes
0answers
40 views

Design a algorithm of graph

Given an undirected graph ${G = (V;E)}$. Three different markers are initially placed at vertices ${s1, s2,s3}$ respectively. Each round, you may pick a pair of adjacent vertices ${u,v}$ and either ...
1
vote
1answer
26 views

Inductive proof for the Bubblesort algorithm

I'm studying Algorithms and Data Structures from The Algorithm Design Manual and I'm having a hard time going through the exercises. Specifically, the proofs are a bit hard and not really explained in ...
1
vote
0answers
14 views

Strong orientation graph algorithm with Robbins' theorem

I've been asked a question that goes something like this: Using depth-first search and Robbins' theorem, design and analyze an efficient algorithm to construct a strong orientation of a given ...
-4
votes
0answers
13 views

Max-Flow Problems [closed]

Given the network below, we can formulate the maximum flow problem as a linear program. The general formulation is below: (a) Reduce the number of constraints in the general formation above by ...
0
votes
1answer
27 views

Ensure a vertex has the highest flow in max-flow algorithm

Let's suppose we have a supplier, sorting facilities, shipping companies and a target warehouse. We produce n packages of the product, and each goes to a different sorting facility (so every facility ...
-1
votes
1answer
28 views

Time complexity of a machine which combines Insertion Sort and Quicksort

Given a machine that sorts an array of length $n$ with the following algorithm: Sort first $2\sqrt{n} + 1$ elements of array with Insertion Sort.(Check Insertion Sort) Select the median of the whole ...
0
votes
0answers
17 views

Why is KMP preprocessing O(N)?

My intuition tells me that there is <=1 increase in lps for each increase in the index. Can someone make a better argument why this is O(N)? My confusion arises from ...
0
votes
0answers
59 views

Distribution Sort - Split elements

I have read from the following references about Distribution Sort: https://users.cs.duke.edu/~reif/courses/alglectures/vitter.papers/Vit.IO_survey.pdf (5.1. Sorting by Distribution) https://en....
1
vote
1answer
22 views

splitting of people betwen groups with group prioritiy list per person

Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group. Every person has a monotone ranking from highest (most ...
0
votes
0answers
33 views

External Sorting - Calculate passes with different number of disks

Let suppose that we have a file with n = 10^6 records. The block size is B = 10 records and we have available main memory m = 20 blocks. (Sorting with MergeSort) a) If we have 1 disk find minimum ...
-1
votes
0answers
9 views

How can I simply sum up the values in the third column using numpy in a table? [closed]

box ID fruit name count sold price per fruit ($) 53686 kiwi 3 0.5 57181 strawberry 101 0.2 25274 apple 0 0.8 48800 orange 35 0.6 ...
0
votes
1answer
31 views

oone exmple in hash topics?

Example: Suppose $H:${$1,...,n$} $\rightarrow ${$1,..,n$} be a uniform hash function. for input $x$, $z$ is equal to number of trailing zero in the right side of $H(x)$. for $0 \leq c \leq 1$ what is ...
0
votes
1answer
60 views

Two-Sum - Pre-sort Optimization Algorithm Design

🧩 Is it possible to optimize the runtime of a two-sum solution by receiving a pre-sorted input either in ascending or descending order? πŸš€ Original Two-Sum Determine whether there are two items whose ...
1
vote
1answer
32 views

How can I make the variance of a multiple sum of set of fixed number of variables minimum?

Here is the problem: There are $MN$ people, where there are $M>1$ seeds and $N>0$ people are in each seed. We have to make $N$ teams of $M$ people where everyone in the team have different seeds....
1
vote
1answer
24 views

Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints

I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'βŠ‚V$ such that $RβŠ‚V'$, $N[V']=V$, $βˆ€v'∈V '[βˆƒr∈R ($path($r', v'$)$)]$ that ...
1
vote
1answer
48 views

Optimal algorithm to distinguish given black box access

This is a variant of this question. Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. Assume that $D$ and $U$ are far apart in total ...
1
vote
1answer
41 views

Minimum sum of squared Euclidean distance between two arrays

Question: Given two sorted sequences in increasing order, $X$ and $Y$. $Y$ is of size $k$ and $X$ is of size $m$. I would like to find a subset of $X$, $i.e$, $X'$ of size $k$, and considering the ...
5
votes
2answers
817 views

Exact definition of average time complexity?

Now I'm from a mathematical background, and I found CS people's definition of average time complexity a bit... confusing, to say the least. Here is a definition that I feel comfortable with: Consider ...
1
vote
0answers
24 views

Does the existence of a matroid structure imply that the greedy algorithm is optimal?

I was going through the topic of matroid structures for the problems like Activity selection ,minimum spanning tree. I also came to know how to solve if a problem exhibits matroid structure. The ...
3
votes
2answers
66 views

Right most set bit O(log N)

I tried to do the problem Find first set bit in Geeks for Geeks, and this is the code I used. ...
-3
votes
0answers
15 views

How can I create the table and solve the error, why did the error happened? [closed]

import world_population.csv population = Table.with_columns( "Population", population_amounts, "Year", years ) population No module named 'world_population'
0
votes
0answers
26 views

What is your approach to writing code? [closed]

I've took on computer science school, now I mainly want to work in IT but I have to go through two years in which I have to study and pass programming. Now first semester, I got a C (because I couldn'...
0
votes
1answer
23 views

SMO, Random forest and Bayes net algorithms: why does Random forest perform better?

I analyzed a dataset using those 3 different algorithms. As I can see, Random forest performs better in most cases. My dataset is composed of 4000 instances of two classes (class A 2000 elements, ...
0
votes
1answer
15 views

How to avoid drawing dense maps?

The problem I have in hand is like drawing Google Maps by myself, in particular, roads. When my map scale is huge, I face no problem, but when I zoom out there are too many things to draw -- sure, I ...
0
votes
0answers
11 views

How to find the “center” of a subset of vertices in a graph? [closed]

Cross-post from StackOverflow. I have an undirected, positive-weighted, connected graph with vertices V and edges E. I also have ...
1
vote
1answer
25 views

Distinguishability given black box access to the distribution

Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. We are not given an explicit description of $D$: we are only given black-box access, ie,...
0
votes
0answers
34 views

How does AlphaGo perform when increasing the size of the board?

I recently watched AlphaGo, a documentary on the recent defeat by the best human player of Go by a computer, AlphaGo. The commentary the beginning points out this was ten years ahead of schedule (...

1
2 3 4 5
…
181