Drop some interesting algorithm problems

[u/Homaderuvas]

Hi guys please kindly share some interesting algorithm problems in the comment section. I did solve many algorithm problems on platforms like codeforces, atcoder, luogu and code chef etc.. looking for some unique ones that are quite challenging and interesting at the same time but kindly don't share open problems .

[u/Magdaki]

Given a sequence of symbolic data produced by some process, infer a grammatical computational model (ideally the simplest) that produces the data.

If you find anything, then let me know and we'll publish a paper together.

[u/Humble-Captain3418 → u/Magdaki]

Can you elaborate this problem a little further? Especially what "grammatical computational model" means. I should be fine reading literature on the matter, too.

[u/Magdaki → u/Humble-Captain3418]

Suppose you have some process that produces data, i.e. a generative process. You've replaced the data with a sequence of symbols in a problem specific representational way. The question is: is some underlying grammar that describes the developmental sequence and if so what is it?

For example:

ABA
ABABBBABA
ABABBBABABBBBBBBBBABABBBABA

The grammar (in this case an L-system) that describes this developmental sequence is A -> ABA and B -> BBB.

For deterministic cases, there's already good algorithms for inferring this, although they could be improved (I have a paper being written right now on just such an improvement). The really challenging case is when there are errors in the strings, missing strings, or non-determinism.

E.g.

ABA
ABBABBBABA
ABABBBBABABBBBBBBAABABBBAA

This is much harder. My RAs and I are currently working on this type of problem. We recently also cracked the non-visual problem too (same paper as above). That's a bit hard to describe so don't worry about it.

This is my core research area.

Even trying to reproduce my work on this without looking it up would be good algorithms practice.

By the way, the solution need not be an L-system. Recently (well ok a few years ago), my research group branched out into other types of grammatical inference. So feel free to pick something else too. The core of it is given some data produced by (or believed to be produced by) some type of grammar, infer the grammar.

[u/AbleActuary5795 → u/Magdaki]

I assume the interesting part is identifying the minimal grammar that contains exactly all (or some error-free subset) of the outputs of the original system. Does the non-determinism come into play where some particular rules only occur with a given frequency? 

W.r.t. errors, for any sufficiently large sample of system outputs of size n, you could construct G* as your initial minimal grammar. You can then identify the rules that are only used for k<<n items in the sampled output, eliminate those rules and construct the refined G**. Repeat until no rules are removed.

[u/Magdaki → u/AbleActuary5795]

With errors you can always infer a non-deterministic system. So my goal is to infer the underlying deterministic system.

[u/Achrus → u/Magdaki]

Really interesting work! I love this kind of stuff. Is this strictly for context free grammars? Also, will mapping the sequence to the grammar always result in “compression” of the sequence?

My immediate thoughts went to using an MLM to infer the higher order structure like for proteins or the Chinese character problem. To handle errors At least. Or like a fuzzy, hierarchical BPE where you could set bounds on expected error rates and how lossy the “compression” is.

[u/Magdaki → u/Achrus]

No, I do inference of context free & sensitive, stochastic, parametric, and graph grammars currently. Always branching out.

In fact, I'm writing a theory paper in a "newish" grammar formalism that will be useful for general purpose inference. If I ever get the time to work on it. Which is never. It has been half done now for 1.5 years. LOL

[u/Humble-Captain3418 → u/Magdaki]

I am kind of curious, wouldn't both cases be matched by A->ABA and B->BB?

[u/Magdaki → u/Humble-Captain3418]

Unless I made a typo, it shouldn't.

[u/Humble-Captain3418 → u/Magdaki]

Oh, I see it. There's a couple AA substrings. Shouldn't be trying to do things when sleepy.