/r/algorithms
Computer Science for Computer Scientists
Computer Science for Computer Scientists
Other subreddits you may like:
Does this sidebar need an addition or correction? Tell me here
/r/algorithms
I’ve written a L-BFGS optimizer and I’m now trying to incorporate bounds. I compute the inverse hessian approximate from a list of spatial and gradient differences, s_k and y_k, of which there are no more than m (limited memory algorithm). My issue is that all the literature and implementations of the L-BFGS-B algorithms I’ve found form the hessian approximate in memory and take expensive inverses of it to find the generalized Cauchy point and perform subspace minimization. I’m trying to figure out if this is actually necessary. Does anyone have experience with this or a resource to look at? Also, this is my first time posting here, so if there’s a better place to ask about this, just let me know.
B-trees can be seen as a generalization of AVL-trees with multiple elements per node. (See Wikipedia for details.)
Does someone know of a similar generalization of AVL-trees?
I recently downloaded Tinder and was wondering how you approach dating apps? Since the app makes wanna with keeping us on it as long as possible, I was asking myself if there are any strategies to subvert the algorithm? Personal anecdotes would be fun too!
I've seen questions about games and AI on this subreddit, such as https://www.reddit.com/r/algorithms/comments/17zp8zo/automatic_discovery_of_heuristics_for_turnbased/?sort=confidence so I thought this would be a good place to ask a similar question.
I'd like to understand from a computational/mathematical point of view why hidden-information games are harder for AI than otherwise (Stratego is often cited as an example). Isn't the set of possible numbers for a given piece just one part of branching factor? For instance, suppose a perfect-information game had pieces with different relative strengths but those numbers could be altered after a piece moves; the AI would know the values for a current turn but could not predict the opponents' future decisions, so on any rollout the branching would be similar to the hidden-information game. Mathematically the game complexity seems roughly similar in both cases.
Imagine a Stratego variation where information was not actually hidden -- both players could see everything -- but numbers can be dynamically reassigned, so the AI doesn't know what value the opponent will choose for a piece in the future. I don't understand how that perfect-information scenario isn't roughly equivalent in complexity to the hidden-information case. If future distributions of numbers are each just part of future board states, then why aren't all current permutations of hidden values also just distinct board states -- by analogy, rolling dice is like a "move" made by the dice themselves ...
My only guess is that the issue for AI is not so much the hiddenness of information but the fact that the state of the game takes on multiple dimensions -- boards which are identical vis-a-vis each piece's position can be very different if numeric values are distributed differently (whatever the numeric values actually mean, e.g., strength during potential captures). Perhaps multi-dimensional game trees in this sense are harder to analyze via traditional AI methods (AlphaBeta, Monte Carlo, and reinforcement learning for position-score heuristics)? But that's pure speculation on my part; I've never actually coded game AIs (I've coded board game engines, but just for human players).
I bought Algorithms, 4th Edition by robert sedgewick without knowing that the book is written in Java, I have no experience with Java, and I want to learn the material in C or C++ so should I return the book and buy another one or are the languages fairly similar?
and if you know any other algorithms book to learn i would deeply appreciate your help if you wrote them in the comment
Lets say I have two groups A and B,
every element in group A has some preference (which is calculated according to a function) for every element in B, however every B has a maximum number of connections which it can form (so the number of pairing).
I want to maximise the preference value of group A.
What is this version of the algorithm called and where can I learn more about it
Hey everyone, this might be a bit of an advanced question and I have no idea how to google for such a thing. The problem is as follows:
I have a discrete binary image with multiple circles of different sizes. They are saved as their radius and their centre. The total area the circles cover is available as well, but not marked by which circle (or how many) they are covered. They may overlap, but no circle is a subset of another.
I now want to find out their "own" area, meaning the area that only they cover and no other circle. Is there any way to do that somewhat computationally efficient, or really smart?
Hi everyone, Is there an algorithm for the following issue?
Let’s say you have a museum
There are v visitor groups who visit the museum during a given day
The museum has x different rooms
Each visitor group MUST visit all x rooms
In y of the x rooms visitor groups MUST spend 5 minutes, in z of the x rooms visitor groups MUST spend 10 minutes
Only 1 visitor group can be in each room at any given moment
Visitor groups MUST NOT wait when changing the room (next room must either be already unoccupied or the visitor group who was in the next room must also switch to a free room (or finish its stay))
Sequence of the rooms doesn’t matter
Visitor groups can book their visit in advance through an online tool that shows available starting time slots
-> How can the occupancy rate of the museum be optimized by managing the available starting times and room sequences? Is there an algorithm for that? Are there tools available for such kinds of problem?
Thanks in advance for all pieces of advice!
I feel like sometimes I have a coders block or just can't get past a concept and move on or find a better solution. Especially if its my own projects. For my day job everything seems easy (code wise)... but it is also not finding something new. It's just working within an existing system.
Hard example:
I have a use case where I will have blocks of binary numbers that are equal length.
Say 1023, 2047, 4095, or 8191 bits.
These blocks will have a pop-count of between 45% and 50% ones, always in that range.
I would like to find a -space- efficient way to create a XOR-able pattern to reduce these strings from 45-50% down to 40-45% depending on start point. It is easy enough fo find a 5% pattern to remove, but I don't want to take 10-20% of the string length to represent the pattern.
I was thinking maybe I could just store an index of a prime that had 5% overlap, or a factor... again. I really don't want to spend a ton of bits.
I could say: how about do an 1010...1010 pattern for this span offset / length in this binary string. The offset and length might not take a ton of bits.
It is just hard when you don't know if there is exactly similar work that has already been done. Most stuff I have read concerning hamming distance and similar had a less restrictive use case / solvable problem in mind.
I'm struggling with a binpacking-like problem, but with custom constraints.
BinConstraint = Tuple[Literal["min", "max"], int] | Literal["none"]
# Let's say we have 60 items and we want to pack them in 4 bins
total_items = 60
# Let's define the 4 bins with different constraints
bin_constraints: list[BinConstraint] = [
"none",
("min", 30),
("max", 0),
"none",
]
result = solve_bin_packing(total_items, bin_constraints)
I expect the result to be : [15, 30, 0, 15]
, as it uses the constraints and minimizes the item count in each bin.
I tried solving this with Pulp but I could not find a way to get the solver to return the correct result.
Can anyone help me with this ? Thanks a lot !
What do you guys think? Do you see a way to improve on \mu? https://raw.org/book/algorithms/the-fast-inverse-square-root-algorithm/
I was watching this video on Dynamic Programming using Java on FreeCodeCamp, YouTube by Alvin. The first example finds the nth Fibonacci number. He speeds up the algorithm by using memoization. But then I don't understand how it works. I doesn't seem like the program ever retrieves a value from the memo, it only stores the values of the fib(n-k) values in the memo. I would love if somebody helps me on this.
Given a polyomino (a bunch of squares joined together), I'm looking for an algorithm which can find the best possible split such that the number of rectangles used is the least possible. Rectangles can be any size as long as they fit inside the polyomino.
Since all NP problems can be reduced to NP-Complete (I don't know how that usually goes in practice), does this mean we can use the generic approach to some NP-Complete problem such as the knapsack probem to approximate the solution of any NP problem? I'm thinking there will either be a problem with the fact that we're not really finding solutions, but approximations. Or maybe it's just not something practical since there's no definitive method of converting NP problems to an NP-Complete problem of our choice. I would like to know your insights on this!
I learned more about the formal definition of Big O notation (f(n) = O(g(n)). It tells you that the growth rate of function f does not exceed g.
But Grokking early on says that Big O tells you the number of operations an algorithm takes in its worst case.
Which one is it?
How do you make sure the definition of an operation is the same when you compare two different algorithims? Couldn't the O times change depending on what each person considers an operation
Today, I did LeetCode #1342, and I thought I will share it with you guys, have fun.
What do you think about my solution?
I have experimental data in a dataframe format (each row has n features, 1 output_val) where I can fit the training subset to some blackbox proxy model (e.g. SVM/MLP etc) for 5 folds. Hence there are 5 models and thus 5 optimal feature combinations. Each feature value can be either of [0,1,2,3].There are about 100 rows of combinations of these n features. Each combination yields a output value which we want to maximize, using methods like PSO. The idea is to get the best feature values for all n features. But we cannot simply average the feature output across the 5 folds since it is misleading.
How should I proceed to arrive at some global proxy model/function? And then get these n optimal feature values?
Given a minimum cut (A, B) for a flow network, is it possible to verify that it is, indeed, a minimum cut for the network in linear time? So far, all sources I've checked indicate that the way to do it is simply to solve the network from scratch, i.e., compute a maximum flow using a standard algorithm like Ford-Fulkerson. The problem with this is, 1) it's too much work just to verify, and 2) what if multiple valid maximum flows are possible, then I may not get what I'm looking for, no? What am I missing?
Jw— I’m on incognito and wondering if the obscure recommendation’s are because I’m insanely active and obvious on my main account(s) — idk, random thought & question while stoned I mean— if I watch the same totally specific and relatively obscure video’s that I normally would on my account often — would youtube eventually guess that it is me somehow~~
I created a data structure that reminds me of fibonacci heaps, but it works completely different. Whoever is interested can find more info here: https://github.com/spirosmaggioros/bubble
I have an assignment in a course where we need to code up a few algorithms of our choice. It's mostly meant to help us understand how to go about coding an algorithm systematically. We can choose literally any algorithm as long as it has a well-defined input and output format. There are a lot of algorithms that I already know to pick from, but I wanted something fresh to learn more from. It will be great if you guys can give suggestions for any interesting and fun algorithms you may have come across.
#include <bits/stdc++.h>
using namespace std;
vector<bool> flags(2,false);
int turn;
void task1(int &a)
{
for(int i = 0; i<100000; i++)
{
flags[0] = true;
turn = 1;
while(flags[1] && turn == 1)
{
}
a++;
flags[0] = false;
}
}
void task2 (int &a)
{
for(int i = 0; i<100000; i++)
{
flags[1] = true;
turn = 0;
while(flags[0] && turn == 0)
{
}
a++;
flags[1] = false;
}
}
int main()
{
int counter = 0;
thread t1(task1, ref(counter));
thread t2(task2, ref(counter));
t1.join();
t2.join();
cout<<counter<<endl;
return 0;
}
It still gives the output in the range of 1999xx's, how can I solve this
So this borders on sci fi but is an interesting class of algorithm I wonder if anyone has studied or even has a term for?
Some background. I have a wide background in biology, cs, and engineering. I loved the idea of the protomolecule from SA Cory's The Expanse. As a quick rundown the protomolecule is a type of nano particle that co opts other biological systems to eventually build mega structures for aliens. So obviously I have spent too much time working out how it might work. The most interesting part I have pondered is how would something starting from no more than a dumb inert particle know what to do as it grew.
We can make the assumption that it has an astounding information density, they even imply that some of the information may be stored as things like the distances between molecular bonds and with sensitive enough machinery you can store a lot there. However, I prefer the approach that the system learns its purpose as it grows.
We see this in many biological systems in nature, they start as single cells and build at first based off of DNA but at some point much of their structure emerges from annealing of defined processes as opposed to per-encoded instructions. We even see this in some systems such as AI image generators where a seed (phrase) is used to structure an emergent image. In a way some types of programming are like this as well where a small amount of source code builds a large amount of executable code based on the system it builds in.
So my question is is there a real term for this type of semi emergent algorithm and if so is there anything on the study of this element of these systems. This seems like one off those things where its hiding a large amount of potential. Having math to understand if these systems halt (halting problem) or math for understanding the maximum possible complexity / reach seems interesting. A way to characterize the annealing surface with minimal traversal may also be useful?
Not sure if this is the right sub, but I've been thinking about a twist on the ant colony optimization (traveling salesman problem).
Imagine a 10x10 grid. On this grid, there are 10 humans (1) and one zombie (-1). The goal of the zombie is to infect all the humans on the grid. Once the zombie infects a human, that human turns into a zombie and starts trying to infect other humans. Note: the zombies are aware that once they infect a human, that human also becomes a zombie and starts trying to infect others. Second note: zombies can move one grid space at a time (up, down, left, right).
What I'm struggling to figure out is an algorithm that would return the most optimal path for the first zombie to take. Would it just involve going to the nearest human and then branching out from there? But, unlike the ant colony or traveling salesman problem, this problem isn't static.