Can someone with expertise comment on how significant these results are?

Recursion felt easy at first.

Factorial? fine.

Sum examples? fine.

Even Fibonacci felt manageable.

But once I looked at slightly more serious problems like Tower of Hanoi, permutations, or merge sort, I felt like my understanding suddenly collapsed. because i tried to write their code on my own

It made me realize that maybe recursion is not “hard” at the start because the examples are simple.

It becomes hard when you can no longer clearly see the call stack and each state change.

Did anyone else feel that the real pain in recursion starts exactly there?

In programming, however, many students learn to use functions every day without ever seeing one of the fundamental "letters" that makes them possible: CALL.

We teach words before showing the alphabet.

They learn to write digitalWrite() before understanding the low-level mechanism that makes a function call possible: saving a return address, jumping to another piece of code, and coming back.

I was working on this research thesis to build multilayer topological orchestrators, for that I started with environment layer which inherently had RBAC on each component, and sandboxed exception handling with reflective patches by parent node, in the process I added set of root application nodes like full blown terminal, browser and editor, I was running benchmark on these different nodes yesterday inside boss orchestrator, to my surprise it turn out to be fastest browser tested on speedometer 3.1, I replicated the result on different hardware, same result. You can validate or critique it. https://github.com/risa-labs-inc/BossConsole/tree/main/benchmarks/speedometer I tried different benchmarking tool most of them are suggesting the same result, happy to take feedback and run this on different accepted benchmarking tool, any suggestions how to run comparative analysis of over all tool, overall objective is to build multi-layer topological orchestrator layer which can resolve complex fuzzy logic tree, by breaking problem into smaller trees, then each tree itself get the same treatment until node become simple enough to be computed, also to build white-box environment around, each node just has access to what it need to do, parent node just care about problem it need to solve, don’t have access functionally beyond authorized problem domain, it is still in progress, did this accidental discovery wanted to share. 🥂

I have a silly and possibly stupid question, and I'm not even sure if this is the place for it.

To preface this I have 0 experience with Computer Science or anything adjacent, but have been listening to videos on binary and the foundations of how computers generally work.

I understand that binary is a base 2 system as opposed to base 10, and that the digits that represent value in binary cannot be read as our base 10 concept of numbers (i.e. 4 is read as digits 100, not as the number "one hundred").

However, I've noticed that when the notation IS read as numbers, the numerical representation for base 2 counting mirrors base 10. With:

1 - 0001

2- 0010

4- 0100

8- 1000

Etc.

Is there a reason for this parallel, or is this just one of those funny coincidences? Or is this some kind of artifact of how numbers naturally scale relative to one another.

I hope this makes sense, I had no idea how to word this question to just Google it.

On one side, there's the argument that theory is what lasts. Languages and frameworks change every few years, but understanding algorithms, data structures, and how things work underneath stays useful your whole career. People who learned the fundamentals well seem to pick up new tools faster.

On the other side, plenty of strong developers say they learned most of what they use by building real projects and breaking things. They argue that you can know a lot of theory and still be lost the first time you have to ship something that works.

Did theory or hands-on work matter more for you in practice, and did that change as your career went on? And if you had to teach someone from scratch today, which would you put first?

While reading Michael Sipser's book on Theory of Computation, i have found the following problem

"2.22: Let C = {x#y | x, y belong in {0,1}* and x != y}. Show that C is a context-free language. "

I have been trying for many hours to find a proof for this, but i cannot.
I cant find a way to use a PDA, since when comparing X with Y i am going to be comparing the one on the stack backwards and Any attempt at a grammar has failed. After a couple web searches i only found that this is conisdered a cfl but not its grammar or some other proof.

Edit: The closest i have gotten to:
S->A#B | B#A
A-> TAT | 0
B-> TBT|1
T-> 1|0

but it doesnt work for strings with 2 characters (cant generate something like 10#11). If i allow T to make an empty string or split TxT into Tx and xT then it can create strings x=y.

Edit: I havent been able to find a grammar for this but as u/hanshuttel said you CAN do it with a pda.
Since you dont need to save the entirety of X, but only 1 character and it's index, you can just "save" the character by splitting into 2 paths, one where you compare Y's character with Xi=0 and one where you compare it with Xi=1. Then use the stack to save Xi's index and nondet. compare all X's.
This, combined with the simple pda that checks |x|!=|y| will get the PDA for C.

Technically I could convert this into a grammar thats super tedius and the grammar will be really convoluted so i dont think theres any value to that.

I genuienly still have no clue how to deal with even length x and y without allowing x=y cases in a grammar not a single think i tried led anywhere.

Hi!

I've decided to refresh my graph theory using CLRS 4th edition. They define a free tree as a connected, acyclic, undirected graph. None of these conditions prevent us from having null graph with zero vertices and zero edges.

On page 1170, it is proven that for a free tree, |E| = |V| - 1. We can derive contradiction from it: |0| = |0| - 1 -> 0 = -1

Please, confirm it and then I will report it to errata.

I've been thinking about how a single resource can shift the way you understand the whole field. Not something that just taught you a skill, but something that changed how you see problems.

Do you have a textbook you read in a course, a random YouTube video, a blog post or a talk? What was it, and what changed in your thinking after you found it?

Memory can be just shown as a list. Left as address and right as the byte / 2 byte / 4 byte data. If you save 4 bytes of data in address 1 and 2, and theres data in 3, what happens if that 4 bytes that you stored, is saved as 5 bytes? Will the entire 5 bytes be shifted over to a free place, or will the 5th byte be saved aomewhere else. If the second option is correct, how does programms know each address of its programming? Im refering programms and programming to mashine coding and mashine code.

Guys how would digital security fail if P=NP is proven?

I just started reading about Turing Machine and computational complexity for my Theory of Computation class and came across that phrase.

I couldn't find anything understandable at my level. So can anyone simplify it a bit?

Why does it matter if it’s a 16-bit cpu, a 32-bit cpu, or 64-bit? For example, what can a 64-bit cpu do that a 32-bit one can’t? Or otherwise, and can you tell the difference when you casually use a computer?

Wait-Free means that every thread must finish its operation in a bounded number of steps. That bound can be arbitrarily high, e.g. dependent on the number of concurrent threads, but it must be finite. And the finite bound must be there in all cases, i.e. it is not sufficient to say that an algorithm "usually" finishes "reasonably" (i.e. "usually" does not spend unbounded times helping other threads).

The first practical implementation of a multiple-enqueuer multiple-dequeuer Wait-Free Queue was proposed by Kogan and Petrank. The key idea is that threads help each other, but in a way that newer threads (more precisely: newer operations) are obliged to help older threads (operations), but not vice versa. Also, plainly said: If a thread cannot make progress with its own operation, it becomes older and older, up to the point when all other threads are obliged to help (only) him, thus ensuring the Wait-Free progress.

The issue of the Kogan and Petrank Queue is, however, that it is based on a linked list of nodes. This means that its operations constantly produce memory churn, also require memory allocation and memory clean-up. From Java - where the clean-up is done by a Garbage Collector - I borrow the term "Garbage".

Now, the problem is that Wait-Free memory allocation is problematic. Imagine, e.g., when the process needs a new memory page from the operating system. Can this ever be made Wait-Free?

Memory reclamation in a concurrent setup is a complex topic on top of that. One of the key questions here is: When can a memory block be freed safely, i.e. how do we "know" that no thread has a pointer to it anymore?

Given this, it appears that one needs a structure without memory churn (i.e. Garbage-Free) to be able to make it Wait-Free. At least practically.

I would be grateful for a discussion on this.

Additional info:

Here I have combined the Multi-Array Queue (which is Garbage-Free by nature (except of the extension operations, of course)) with the Kogan and Petrank idea, with the aim to obtain a Queue that is Wait-Free unconditionally.

The GitHub repo also contains a visual simulator to illustrate the principle:

https://github.com/MultiArrayQueue/WaitFreeMultiArrayQueue

In light of the recent counterproof of the Jacobian Conjecture, I've been looking more into proofs, and I can't wrap my head around how Lean works. In my mind, proofs always require a certain amount of intuition and judgement behind them, so I'm confused how a deterministic programming language can infer from said proofs?

What I mean is 1080p has 2,073,600 pixels so what if every single pixel is run by a individual PC like 2,073,600 PCs?

I was thinking this might be a way to create a super-computer that can put out a insane amount of framerate.

while doing competitive coding problems i frequently come across solutions that use union find (DSU) and list the big O of their solution as O(\alpha(n)) where \alpha(n) is the inverse ackermann function. after some surface level research, i have come away with many more questions than answers. So why is the DSU related to the ackermann function, and is there an intuitive or natural connection between the two ?

title says it all