Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
1answer
99 views

Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance) $\alpha$ denotes the start and end vertex of ...
0
votes
0answers
20 views

Is it possible to build an algorithm that can 'web crawl' to build questions and produce answers?

I'm building a revision based app and one of the ideas that occured to me was a section that tested knowledge of a given subject (let's say data mining) by using the web to create questions the user ...
-1
votes
0answers
14 views

How to use backtrack for bakery code challenge?

I tried to use backtrack to implement bakery code challenge. The question is here So far I got this ...
1
vote
0answers
32 views

Is my universal hash function of factor 2?

Imagine that we have a simple family of Hash functions $H=\{h_a\mid a\in[p],\, a\neq 0\}$, where $h_a(x)=(ax\bmod p)\bmod n$. Let's assume $p$ is a prime number between $u$ and $2u$. I want to show ...
0
votes
0answers
26 views

A two person balls and bins game

There are infinite balls of $n$ distinct colors and a tray consisting of $k<n$ slots. A human can place $k$ balls in the tray, with each color occuring atmost two times and give it to the Oracle (...
-1
votes
0answers
28 views

Knapsack problem picking each item from a different set

2 down vote favorite 1 I have an understanding of the basic 0-1 knapsack problem and its solution. I am trying to reason through a variant of the 0-1 problem where instead of being able to select any ...
0
votes
0answers
15 views

Does string have duplicated characters? Best Conceivable Runtime (BCR) vs Best Case Scenario (BCS) of the algorithm

Writing an algorithm for "Does the given string have duplicated characters?" I'm confused about BCR and BCS. At first I guessed that BCR for this specific problem is O(n). However while implementing ...
0
votes
0answers
22 views

Transforming bin packing problem into weight distribution problem

I am working on a problem and need help to iron details and help to move it forward. P1: There are $n$ items with weights $w1, w2, .., wn$ and $K$ people ($p1, p2, .., pk)$ needs to carry these ...
0
votes
1answer
65 views

Sorting n elements in worst case of $\sqrt{n}\log n$

Can $n$ elements be sorted in a worst case time of $\sqrt{n}\log n$? Why or why not? I've seen algorithms being sorted in the worst case of $n\log n$, so why can they be or cannot be sorted in $\sqrt{...
1
vote
1answer
35 views

A* Search Algorithm Implementation with Priority Queue

I've got a question regarding the A* search algorithm's implementation. According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to ...
0
votes
0answers
15 views

Is there a polynomial time algorithm to computer number of isomorphic groups of a given order

Here is a link for the number of groups of a given order. I'm wondering if it is possible to write a polytime algorithm to compute the number of isomorphic group of a given order. Here is the link: ...
3
votes
2answers
96 views

Efficiently shuffling items in $N$ buckets using $O(N)$ space

I’ve run into a challenging algorithm puzzle while trying to generate a large amount of test data. The problem is as follows: We have $N$ buckets, $B_1$ through $B_N$. Each bucket $B_i$ maps to a ...
0
votes
1answer
38 views

Sum of zero nim sum series

The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\...
1
vote
0answers
28 views

Counting on a matrix

I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$. If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are ...
2
votes
0answers
35 views

Is the data-centric “push” model for SQL evaluation nonsense?

The traditional way to implement a SQL database is to parse the query, create a parse tree, and then evaluate it using the "volcano" model. In this model you call .next() on the root node of the tree ...
1
vote
1answer
31 views

Subset sum problem, given that a valid subset exists

I have a problem at work. I need to find a subset of a set of positive integers that sums to a certain value. I know there is a subset but I need to find it. Is this new problem the same as the ...
0
votes
1answer
70 views

What is the difference between “algorithm,” “process” and “program”?

I am currently studying algorithms and algorithmic design, and I am confused those terms. What is the difference between them? Thank you.
1
vote
0answers
20 views

Algorithm for first-price, sealed bid simultaneous auctions for distinct items and budget-constrained bidders

Context: I play in a simulated online basketball league (a la the NBA) where each human player controls one of the teams. When each simulated basketball player is a free agent (that is, their previous ...
3
votes
1answer
49 views

Algorithm for minimizing the number of “inversions” in a graph

Given the following graph: With the assumptions below: A node on the left is linked to several nodes on the right Nodes on the right are paired together: one is black, one is white Each pair of ...
0
votes
0answers
6 views

Determining the max frequency of a cycle with flip flops

The following cycle is given and i need to determine what is the max frequency possible for it. The cycle has 3 positive D-edge Flip Flops and some logic gates. i calculated the time it takes for ...
1
vote
0answers
30 views

Possible Distribution of coins

We are given a set of $n$ coins with denominations $v_1,v_2,\ldots,v_n$ and a number $x$. The coins are to be divided between to persons, with the restriction that each person's coins must add up to ...
2
votes
1answer
72 views

Listing all prime numbers less than an integer N

I am trying to solve this problem listing all prime numbers less than an integer but using the smallest amount of memory. Is it possible to solve this problem using a smaller amount of memory? <...
-1
votes
0answers
8 views

Count distict 2-dimensional subset sums

Given a set $S$ of $n$ 2-d points, I'd like an algorithm to count how many subsets $A\subset S$ of cardinality $k$ there are such that the $k$ points of $A$ sum up to $(x,y)$. Can this be done in ...
-1
votes
0answers
34 views

Clustering in a metric space

Can anyone help me to solve this question.i am in confusion using which algorithm. Cristina is interested in a metric space (X, d), where all distances d(x, y) are either 0 (in which case x = y), 1 or ...
0
votes
0answers
32 views

Modifying Dijkstra’s algorithm such that it finds a path whose longest edge is as short as possible

I want to modify Dijkstra’s algorithm such that it finds a path whose longest edge is as short as possible. My idea: ...
0
votes
1answer
42 views

Confused about constructing the “failure table” in Knuth-Morris-Pratt algorithm

I'm trying to learn how the "failure table" is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $O(k)$ time (where $k$ is the length of the ...
0
votes
1answer
17 views

algorithm for correctly rounded floating point radix conversion

Is there any generic algorithm which implements a floating point radix conversion? Lets say we have a $p$-digit FP number $A = \sum_{i=0}^{p-1} A_i \beta^{e-i}$ in radix $\beta$ and with $0 \leq ...
0
votes
0answers
21 views

Bellman-Ford shortest path [duplicate]

I've been trying to prove that if I'm given a directed weighted graph with no negative cycle, then there exist an order on the edges such that after the first iteration I will get the shortest paths. ...
2
votes
1answer
21 views

Find pair of complex numbers with maximal sum

Given two lists of complex numbers, is there an efficient algorithm to choose one element from each list such that the magnitude of their sum is maximal?
0
votes
0answers
38 views

In a directed graph G, detect if there is a path that visits each node at least once

I'm trying to prove that Given a directed graph G,we can't detect if there is a path that visits each node at least once, I’m trying to use the fact that: detecting if a directed graph has a Hamilton ...
1
vote
1answer
43 views

Behaviour of Dijkstra in Case of Negative Edge Weight [duplicate]

I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss. For the given below graph What should be the Cost to reach Node G from Source Vertex ...
-1
votes
0answers
57 views

Sorting from a Magnetic Tape

How would you design an efficient algorithm to solve this problem, with these constraints: A file, on a floppy disk, of distinct 2-Byte integers in the range 1 .. 16000 needs to be sorted. The ...
2
votes
0answers
58 views

Balls in Bins with Pairwise Distance

Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
0
votes
1answer
24 views

Determining cycle time and and hold time in logic circuits

First I have general question. In a circuit with both logic and D edge flip flop does hold time have to satisfy $t_{hold} < t_{setup}($D-FF$) + t_{pd-min}$(Logic), or is it enough that $t_{hold} \...
2
votes
2answers
48 views

Checking if sequence is almost strictly in ascending order

This was part of my interview questions. Given a sequence of integers as an array, I have to determine whether it is possible to obtain a strictly increasing sequence by removing no more than one ...
1
vote
1answer
43 views

Algorithm Design for Linear Programming

I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing. I am working on the following problem: Suppose you are consulting ...
0
votes
0answers
19 views

How does single pass in-memory indexing work?

I don't understand how single pass in-memory indexing works in the field of information retrieval since doesn't the postings list in an inverted index have to be sorted? As far as I understand, the ...
1
vote
1answer
16 views

The time complexity of the Wikipedia version of Pollards $(p-1)$ algorithm

I am trying to understand the runtime of Pollard's $(p-1)$-algorithm as presented on Wikipedia. There the author writes that it takes $\mathcal{O}(B\log B\log^2n)$ time, but I do not see why. Here ...
5
votes
1answer
108 views

Find a strategy to evade hungry lions on the real line for the longest time

This is an interview question I was asked, which I don't know how to approach. I would appreciate pointers to algorithms I should look up. You are placed on the real line, and there also are $K$ ...
3
votes
0answers
15 views

Power of 2 assumption in Divide and conquer [duplicate]

Currently doing an Algorithms course in my 2nd year of university (I am a maths student, but thankfully at Warwick University, we have quite a flexible degree). One of the topics we cover is the ...
1
vote
1answer
28 views

Why does Radix sort require stable digit sorts?

I'm reading the CLRS book and have a question about the following quote from the book. In order for radix sort to work correctly, the digit sorts must be stable. Why is stability required? Wouldn'...
0
votes
1answer
15 views

Placing a point between two nearest ones

I have a closed 2D shape expressed as a list of points, like that: [ {0, 5}, <-- {x, y} {10, 5}, {15, 6}, ... ] The user has a canvas: each time he ...
2
votes
1answer
79 views

What is the best way to compress a string with only numbers and commas in it?

I have a string like this: 11,512,64,23,46,12,67,85,84 And I'm sure it's following these rules below: Only , and ...
1
vote
2answers
22 views

Question related to vertex cover

The definition of vertex cover is as is: Set of vertices such that each each has atleast one endpoint in that set. In the above example, why can't we consider all vertices as vertex cover since all ...
1
vote
1answer
45 views

Algorithm for Even Fitting

I'm trying to design an algorithm for evenly fitting decimal numbers into a decimal number. Say I have a set $N$ of decimal numbers ($N_1$, $N_2$, ..., $N_n$) and a target value $Y$. I'd like to see ...
0
votes
0answers
22 views

Can any recursion implementation be written into a bottom-up DP implementation?

Can any top-down recursion implementation be written into a bottom-up DP implementation?
0
votes
1answer
322 views

Compound interest with varying compounding frequency

Here is the problem I have attempted to solve. Given original principal $n$ and aggregate rate $r$, find the maximum final principal that can be yielded. Though I know that the higher the ...
1
vote
1answer
45 views

proving correctness of algorithm about graphs with DFS

I need to prove/disprove the correctness of the following algorithm: Let G be a simple, undirected and connected graph. The task is to find if the graph contains an odd cycle. The algorithm goes that ...
0
votes
0answers
20 views

Algorithm for gaps in coverage of half-closed intervals

I have a collection of pairs of half-closed intervals of reals (actually datetimes, but fairly close to continuous). I need to determine if there are any gaps in the coverage of that datetime. They ...
0
votes
0answers
20 views

Optimizing with diminishing marginal utility

Let $M$ be the integer number of dollars available, and let $P$ be a set of products to buy. Assuming that for each product its marginal utility decreases as you buy more of it. How to find the ...