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
2 answers
29 views

Compare list of parameters with each other and sort them from most to least selected

I want to sort the list of parameters (p1, p2, p3, p4, ..., pn) according to their importance. All parameters have to be compared with each other at best once, but not less than once. The person will ...
0 votes
1 answer
20 views

Directed graph of bank balances and transactions, how to process transactions?

I'm working on a game where there are several different entities represented by nodes. Each node has a starting balance, and directed edges show where money is owed from one account to another. One ...
1 vote
1 answer
74 views

What is the proper way to approach a competitive coding problem?

***Climbing Stairs Problem: https://leetcode.com/problems/climbing-stairs/ 1) Take the "***Climbing Stairs" Problem for instance: If I was given a problem like this on a test after mastering ...
0 votes
0 answers
22 views

Algorithms And Research in Pure Strategy Nash Equilibria

Full Disclaimer: I asked a similar question Math Stackexchange here, but I think that this forum may be better suited to this type of question. I'm reading many articles in Nash equilibria with ...
  • 1
1 vote
1 answer
50 views

If the heuristic $h(n)$ is the estimated cost from node $n$ to the goal, then why would we want a heuristic that has a greater cost?

I am currently studying the concept of heuristics in search algorithms. I recently asked this question about the so-called "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\...
0 votes
1 answer
40 views

Is there any Algorithm to check a vertex\node's partial order in terms of other vertices\nodes for a given graph?

For the given figure, let's consider vertex v3. For v3, v0 has a higher partial order,v1 & v2 has the same partial order, and v4 & v5 have lower order than v3, e.g., higher: {v0}, same: {v1,v2}...
  • 1
0 votes
0 answers
27 views

Efficiently counting correctly ranked pairs

The problem: Given a set of measurements $x_1, x_2, ..., x_n$ and corresponding labels $y_1 <= y_2 <= ... <= y_n$ that designate the desired ranking, count the number of pairs that are ...
0 votes
0 answers
41 views

How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?

I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following: Greedy search minimises estimated path-cost to goal. But it's ...
1 vote
1 answer
44 views

Divide-and-Conquer Algorithms: What exactly is $a$ and $b$ here?

Chapter 2.3.2 Analysing divide-and-conquer algorithms of Introduction to Algorithms, fourth edition, by CLRS, says the following: A recurrence for the running time of a divide-and-conquer algorithm ...
2 votes
0 answers
34 views

Effecient algorithm to build a linear order on a set of states of automaton

Is there an algorithm that help to build a linear order on a set of states of automaton (without output signals), such that this order is compatible with a transtion function of automaton? Let A = (X, ...
0 votes
0 answers
23 views

Randomized-Select Problem

RANDOMIZED-SELECT A = {12, 0, 4, 3, 5, 7, 9, 2, 8, 11} RAND-SELECT(A, p, q, i) -> ith smallest of A[p.. q] If p = q then return A[q] r <- RAND-Partition (A, p, q) k <- r-p+1 then return A[r] k= ...
0 votes
0 answers
33 views

How to assign people to take part in an activity with limited space, with some people having priority over others

I am trying to solve a seemingly straightforward problem, for which a well-known algorithm should exist, but I can't find it. Imagine we have an activity, let's say football/soccer. Obviously, only 11 ...
  • 101
3 votes
0 answers
33 views

TSP algorithm with a good run-time based on properties of the graph (not just based on number of nodes/edges)?

In the worst case, the Traveling Salesperson Problem (TSP) is mostly accepted to take exponential runtime in terms of $|V|$ and $|E|$ (the number of vertices and edges respectively). But for many real-...
  • 483
-2 votes
1 answer
46 views

Loops and Its Time Complexity

Back here with some more doubts, i wanted to understand, how can we formally or may be easily calculate time complexity for such question without getting into "DRY RUN", i mean is there any ...
0 votes
1 answer
41 views

how to get the high 32-bit of the answer of two 32-bit integer multiple?

Recently, I study the instruction set of riscv32 and face a order as "mulh" which tends to multiply two 32-bits signed integers and store the high 32 value into the register. And here comes ...
-1 votes
1 answer
35 views

Inequality about External path length

First of all LPL is Leaf path length & IPL is internal path length. While i was studying algorithm analysis for average complexity of binary search , i saw that inequality. Before that, i proved ...
  • 3
0 votes
1 answer
32 views

Applying merge sort: Would the value in the box with the red cross be $71$? Does it matter whether we start at the bottom-left or bottom-right?

I have the following diagram showing a case of merge sort: I am trying to find the value that would be in the box with the red cross when applying merge sort in ascending order. It seems to me that ...
0 votes
1 answer
40 views

Checking if a graph contains a (not necessarily simple) cycle of length more than k

I'm struggling with question 7-38 from Skiena's Algorithm Design Manual: Let G be a directed graph. We say that G is k-cyclic if every (not necessarily simple) cycle in G contains at most k distinct ...
  • 103
0 votes
0 answers
75 views

How do these search algorithm diagrams work? How am I supposed to interpret them? And what algorithms do those last three represent?

I was shown these diagrams in the context of search algorithms. The green tile shows the initial state, and the orange tile shows the goal state. I am told that each option shows a path each search ...
2 votes
1 answer
97 views

Minimize max subtree weight among spanning trees

Suppose we have an undirected, connected graph $G$ where vertices have positive integer weights. Let $\bar{v}$ be a given vertex in $G$. Take a spanning tree $T$ of $G$ rooted at $\bar{v}$ and define ...
  • 287
2 votes
3 answers
68 views

Best Data Structure For Text Processing

Given a sentence like this, and i have the data structure (dictionary of lists): {'cat': ['feline', 'kitten']} A feline was recently spotted in the ...
  • 121
0 votes
2 answers
25 views

Maximum the result from multiple functions which share an input amount [closed]

I have multiple functions as shown in the image. For a fixed x value, I need to distribute it into f, g, and h functions for getting the maximum output (y). In other words, having a fixed x value, ...
0 votes
1 answer
63 views

Reversible hash function (?)

I am looking at a problem where I have an assembly/collection of items, V, and my goal is to issue an ID to this collection, ...
  • 101
0 votes
1 answer
19 views

Convolutional neural network for non-image data

I am working on a project for the prediction of preeclampsia, and one of the algorithms to be used is the convolutional neural network. I am a beginner in machine learning, and I am struggling to ...
3 votes
1 answer
664 views

Is it possible to randomly allocate items to bins such that each distinct allocation has equal probability?

I'm trying to randomly allocate N indistinguishable items over B indistinguishable bins with unlimited capacity. Each allocation should occur with equal probability. An allocation identifies the ...
0 votes
1 answer
35 views

Randomly build a binary search trees with simple modification

Let $X=x_1,x_2,x_3,\dots,x_n$ be set of $n$ distinct keys. I read this posts about Randomly build binary search trees like this and now I encounter the following question in my mind, suppose we ...
  • 1,418
0 votes
0 answers
14 views

How to prune a tree of selective nodes without recursion, using a stack [duplicate]

I can't solve the following problem without recursion. I get that the solution has to do with making a list of nodes to process but that's where I get stuck. The problem is to remove all nodes from a ...
1 vote
0 answers
16 views

Algorithm for an incremental update to cut vertex set

There is a classic linear algorithm to find every cut vertex (AKA articulation point) in a graph. I have a usecase that does this computation after every time a non-articulation-point is inserted or ...
0 votes
0 answers
36 views

Find the N adjactent unit squares that contain the most 2D points

So, I have a set of 2D points with real valued positions. I want to find a set of N adjacent unit squares that contains the most points possible. If it's easier, this could be a set of N adjacent (or ...
0 votes
1 answer
52 views

Is there an algorithm that causes a straight line and a circle to collide and bounce?

I used a vector to determine the collision between a line and a circle. Here's the way I thought of it in the beginning. 1. When the ball collides with a straight line, it finds a normal line passing ...
  • 1
0 votes
1 answer
41 views

Understanding the logic for finding the count of same-element-pair

There's this problem that I was solving and even though I have an O(n) solution but still trying to make sense of the pattern. The problem being: determine the number of pairs of the same numbers. For ...
  • 129
1 vote
2 answers
110 views

In two unsorted arrays A and B such that all items of A belong to B (A ⊂ B), find the smallest item in B that doesn't occur in A in linear time?

In two unsorted arrays (say $A$ and $B$) such that all items of $A$ belong to $B$ ($A \subset B$), find the smallest item in $B$ that doesn't occur in $A$ in linear time. No hashing or linear time ...
2 votes
1 answer
66 views

Is there an algorithm for this decision problem that is better than brute-force?

Apologies for the vague title. This decision problem has applications to graph coloring but I have not found a name for it in the literature. I am trying to improve my algorithm for a decision problem....
1 vote
2 answers
58 views

Designing an algorithm to choose the minimum number of sets containing line segments

Let's say we have some distinct sets each containing a number of line segments. I want to choose the minimum number of sets such that I will obtain a line from 0 to L with the largest gap being X long....
0 votes
1 answer
80 views

Is a specialized hardware instruction always faster than a software implementation, and if so, is there a general reason?

I started wondering this after reading about the x86-SSE instruction rsqrtss being faster (and more accurate) than the Fast inverse square root. I have also read ...
0 votes
1 answer
48 views

Finding number of combinations of numbers from multiple arrays that add up to a given value

Let $ A $ be an array of $ n $ integer arrays with unknown lengths and $ s \in \mathbb{Z} $ a given number. I want to find the number of combinations of numbers from each array, such that their sum ...
  • 101
0 votes
0 answers
155 views

Halting problem reduction to single digit numbers

I'm thinking of the solution for severaly days, but I'm not sure about my solution is on the correct way. I need to prove that the next problem is undecidable: Input: An N program which requires an y ...
0 votes
0 answers
34 views

Could Radix Sort be used to tackle LCS algorithm?

Could one use the Radix Sort to find the Longest Common Subsequence problem? I am new to algorithms and was wondering if the string was converted to a list and then one was able to apply Radix Sort ...
1 vote
1 answer
92 views

Name for algorithms whose runtime only depends on the problem size?

I'm looking for the name of the family of algorithms whose exact runtime is dependent only on the size of the input. An example of such an algorithm would be naive $O(n^3)$ matrix multiplication. If ...
1 vote
0 answers
31 views

Is there a comprehensive list of searching algorithms for sorted (and possibly unsorted) arrays available anywhere?

Classic searching algorithms such as binary searching and dictionary searching search sorted arrays based on a given element and make estimations on their own. What I'm looking for is a list of more ...
0 votes
1 answer
87 views

Reducing Vertex Cover (or Independent Set) to Vertex Cover and Independent Set at the same time

In order to show that the next problem is NP-hard: Problem: Vertex Cover and Independent Set Input: Graph G and integer k Output: Does G have a vertex cover of k and an independent set of k? The sets ...
  • 3
0 votes
2 answers
60 views

What is a procedure?

Non-computer scientist here, trying to understand what SICP (Structure and Interpretation of Computer Programs) means by a procedure, whether it matches the dictionary definition, and also how a ...
  • 103
1 vote
2 answers
71 views

Matching students with companies based on their preference

I have a list of companies with n timeslots (number of slots may vary from company to company) and a list of students. Each student made a list of their top 3 companies they would like to talk to. Is ...
  • 11
0 votes
1 answer
28 views

Invariant in Kosaraju's algorithm for SCCs

I am studying graph algorithms, and I know that in algorithm theory there has to be an invariant of sorts that stays the same during the algorithm run that makes the algorithm valid and right to use. ...
1 vote
0 answers
46 views

A data structure to quickly maximize a linear function on a fixed set of $k$-dimensional vectors

Let $v_1,…,v_n$ be a finite list of vectors in $ℝ^k$ (with $k ≪ n$, in my case $k≈10$ and $n≈4~000$). I would like to know if I can precompute something so that given a linear form $f : ℝ^k→ℝ$, I can ...
2 votes
2 answers
171 views

Designing a Data Structure that allows both insertion and extracting a number lower than median in amoritzed O(1) cost?

Consider a data structure that has only two functions. extract_lowerthan_median() and insert(). How can we design it in a way that the amortized cost for both the operation is O(1)? Using a 2 tree, a ...
0 votes
0 answers
62 views

Prove that the total number of parenthesizations of n matrices is Ω(4^n/n^3/2)

Is it possible to prove the total number of parenthesizations of n matrices is Ω(4^n/n^3/2) using the Induction Method? Recurrence formula from CLRS book When n = 1, the sequence consists of just one ...
0 votes
2 answers
53 views

What is the meaning of the term "computational process" in the book SICP?

I'm trying to read chapter one of the famous book : Structure and Interpretation of computer programs. The chapter one starts with a mysterious paragraph: We are about to study the idea of a ...
1 vote
0 answers
63 views

Is it true that: $f\notin o(g)$ implies $\exists c>0: f > cg$ infinitely often

My (attempt at a) proof is as follows: $f\in o(g)$ means that $\forall c>0 \exists n_0 \forall n\geq n_0: f(n) \leq cg(n)$. Now taking the complement we get: $\exists c>0 \forall n_0 \exists n\...
  • 11
1 vote
1 answer
35 views

Algorithm/heuristic for large tournament matchup pairings

I'm scheduling a large invitational tournament with the following conditions The event takes place over 8 weeks Teams arrive and depart on different dates/times, so each day of the event will have a ...
  • 111