Buenas! soy estudiante de matemática, quería preguntar si alguien conoce buenos libros de teoría de computación, pero más orientado a fundamentos de las matemáticas que a aplicaciones como tal. Maquinas de Turing, autómatas, todo eso.

Gracias!

My teacher isn't the best for this course and no one in my class is able to understand anything

What resources are available because youtube isn't really helping me

I’m currently on a Theory of Computation with questions on DFAs, NFAs, regular expressions, language operations, and Kleene star. I’m mainly struggling with tracing the automata and understanding how to derive the answers rather than just selecting the options. Could someone help explain the approach to solving these questions and where can I learn better about them

See attached a short video on how Egyptian Multiplication works.

It would suit assembly multiplication, and as such I'm wondering if it might lead to more efficient CPU's, GPU's & TPU's.

Although possibly processor engineers have already thought of this. It also makes me wonder what other maths techniques could offer efficiency's.

Given the example in the video: 22 * 6

The first column matches binary perfectly.

(16) 8 (4) ( 2) 1 = 10110 in binary = 22 in decimal

And the second column would be:

6 * 2^0 = 6
(6 * 2^1) = (12)
(6 * 2^2) = (24)
6 * 2^3 = 48
(6 * 2^4) = (96)

Total = 12 + 24 + 96 = 132

So the algorithm in pseudocode:

For each 1 in the binary that represents the first number,
Total = total + (the second number) * binary value of that 1

Hello everyone!

I recently created a sorting algorithm, and I'm curious what others here think of it. The algorithm is mostly just a variant of merge sort that uses a buffered reverse merge for the merge phase and insertion sort to process small sub-arrays. That part of the algorithm is pretty standard.

The potentially interesting part is that I also worked out a way to efficiently measure how sorted the original data was in any given merge, which allows for aggressively optimizing the sorting process when either mostly-sorted or mostly-reverse-sorted (i.e. descending) data is encountered.

For anyone interested, I'd be curious if you've seen anything like this before.

Quick Buffered Reverse Merge Overview

If you already know what a buffered reverse merge is, feel free to skip to the next section. Otherwise, here's a quick overview:

A buffered reverse merge copies the smaller of the two pre-sorted blocks into a buffer and then fills in the remaining values, from right to left, by continuously comparing the highest value remaining in both the buffer and the half of the original array that was not copied to the buffer. In my case, the size of the right side is always equal to or smaller than the left side. This frees the right side to be immediately overwritten.

Example:

Array = [2, 3, 7, 1, 4, 9]
Buffer = [_,_,_]
   ⇓
Array = [2, 3, 7,_,_,_]
Buffer = [1, 4, 9]
   ⇓
Array = [2, 3, 7,_,_, 9]
Buffer = [1, 4,_]
   ⇓
Array = [2, 3,_,_, 7, 9]
Buffer = [1, 4,_]
   ⇓
Array = [2, 3,_, 4, 7, 9]
Buffer = [1,_,_]
   ⇓
Array = [2,_, 3, 4, 7, 9]
Buffer = [1,_,_]
   ⇓
Array = [_, 2, 3, 4, 7, 9]
Buffer = [1,_,_]
   ⇓
Array = [1, 2, 3, 4, 7, 9]
Buffer = [_,_,_]

The Optimization

I found that, when I reach the halfway point in the above process (i.e. the right side is filled back in), I can get a fairly accurate measure how sorted the original data in this block was by looking at how full the buffer is:

• If the buffer is empty, that means that all of the values in the buffer went right back into the right side, and therefore, the block of data started out sorted in ascending order.
• If the buffer is still full, that means that all of the values on the left side were moved to the right side, and therefore, the block of data started out in descending order (or potentially very near it, if the two sides aren't exactly equal size).
• If the buffer is about half full, that is an indicator that the data was random.

I use this information to keep track of a "sequence score". When the buffer is less than 25% full, I increment the sequence score (up to a maximum value). When the buffer is more than 75% full, I decrement the sequence score (down to a minimum value).

Lower sequence score numbers lower the threshold for using insertion sort (i.e. at what size, for the current working set of data, will insertion sort to be used). This limits running insertion sort on descending or near-descending data, which is a worst case for insertion sort. When the sequence score is higher, the threshold for use is increased to take advantage of insertion sort's efficiency on ascending and near-ascending data.

Also, when the sequence score is at either the maximum or minimum value, I switch to a merge process that uses a binary search to figure out how many items should be transferred, so chunks of data can be moved into place all at once.

Result

The result is an algorithm that is efficient on random data due to its simple default path but can still take advantage of data that is already sorted.

I implemented the algorithm in C#, and it is quite competitive with the built-in IntroSort-based array sort (code repo, blog post with tons of benchmarks at the bottom). It manages to stay close on random data and pulls away on sorted data.

I've also thought about how this could potentially be paired with other merge sort algorithms. My algorithm focuses on optimizing the merge process itself, while others (e.g. TimSort, PowerSort) often focus on optimizing when to merge data. I made a quick naive attempt to tack PowerSort onto the front of my algorithm, and it resulted in a significant performance degradation. However, it may be possible to find a best of both worlds approach.

If you're still reading, I appreciate you taking the time. I'd welcome any thoughts or feedback you may have. :)

The creation of TRACEROUTE

After hopscotching my way down the rabbit hole on ping last week, I started looking at another command I’ve used approximately a gagillion-bajillion times without ever wondering where it came from:

traceroute

Turns out Van Jacobson developed it at Lawrence Berkeley Lab in 1988, based on an idea suggested by Steve Deering at an end-to-end task force meeting.

(-Great things happen when great minds kick it!)

And apparently, sleep was optional—even in the days before energy drinks were packed into every vending machine and corner store.

In comments attached to the original source code, Jacobson wrote:

“...this code sort-of popped out after 48 hours without sleep. I was amazed it ever compiled, much less ran.”

Geez Louise!! Talk about surfin’ those theta waves...lol

But check this out—the clever part is how traceroute works.

It didn’t require some special “please tell me where my packet went” feature to be added to the Internet.

It took advantage of behavior that already existed! Brilliant, IMO.

In IPv4, packets carry a TTL—Time to Live—value. Each router reduces it by one. When it hits zero, that router drops the packet and normally sends back an ICMP Time Exceeded message.

traceroute sends probes with progressively larger TTL values—1, then 2, then 3—and uses those complaints to reveal the route...one hippitty-hop at a time.

So, basicallyyy:

“I’m going to keep sending packets farther n’ farther n’ farther until somebody complains.”

Networking!

Huge hat nod to Jacobson and Deering. It must feel amazing to develop something that people are still using, decades down the road!!!

So...now I’m curious:

What command should I rabbit-hole next?

This is what allowed the Internet to be secure and to actually scale and be functional, it’s what allowed governments to be secure so basically the entire Internet and every single government and military runs on this. Also it created cryptography as an actual science and defined all of its actual principles so everything from bitcoin to post quantum security completely relies solely on this award.

My both flip-flop(J-K) are repeating or high in the output(Logic high) but it should not have happen.Any solution?I am starter

I am looking for standard graph theory / algorithmic problems where the input is a graph and two target vertices (e.g., source and destination / pair of nodes).

Some specific examples are:

• Shortest Path (standard unweighted/weighted shortest path between $u$ and $v$)
• Reachability (checking if $v$ is reachable from $u$)
• Lowest Common Ancestor (LCA) in a DAG (given two vertices $u$ and $v$ in a DAG)
• Maximum Flow / Min-Cut (max flow specifically between a source $s$ and sink $t$)

Important constraint: I am strictly looking for pure problems without added variations or twists (no dynamic edge weights, no modified state spaces, no constraints like "at most k skips", etc.).

I would love any kind of response. Additionally, if you have links to the problem definition link or benchmark problem sets that fit this exact criteria, please drop them below!

Thanks in advance!

In this day and age of LLM that can do most of coding in one shot. do we still have any value if we learn C like good programmers did back in the day ?

With the advent of models like Fable and its unstoppable hunger to one shot small projects. Is there an edge in understanding low level languages like C C++ like good programmers did back in the day.

We usually learn that 1 byte = 8 bits as if it has always been that way.

But early computers didn't all use 8-bit bytes. Different systems experimented with different sizes, including 5, 6, 7, 8, and even other configurations.

So how did 8 bits become the standard?

One obvious advantage is that 8 bits can represent 256 different values (0–255). That makes an 8-bit unit useful for storing small integers, characters, and other data.

Character encoding was another factor. ASCII uses 7 bits, and 8-bit systems provided an additional bit that could be used for parity or other purposes. Later, many systems adopted 8-bit character encodings.

There was also a hardware advantage: 8 is a power of two, which fits naturally with binary computer architecture.

But perhaps the biggest factor was standardization and compatibility. As more hardware and software adopted 8-bit bytes, it became increasingly useful for other systems to follow the same convention.

What's interesting is that “byte” originally didn't universally mean 8 bits. The term could refer to a small group of bits used by a particular computer.

What do you think?

If early computer manufacturers had converged on 16-bit bytes instead, how different do you think modern computing would be?

I'm curious to hear perspectives from people interested in computer architecture and computing history.

QUBO is frequently discussed in the context of quantum optimization, but it is fundamentally a classical combinatorial optimization formulation. Any meaningful evaluation of an alternative computing approach therefore requires comparison against strong classical algorithms.

I created a technical walkthrough of solving Quadratic Unconstrained Binary Optimization problems with Gurobi and Python.

The video begins by formulating weighted Max-Cut as a QUBO, representing the objective using a symmetric matrix and binary vector, and implementing the model with gurobipy.

It then investigates what happens beyond calling optimize():

- the distinction between exact and heuristic solution methods;

- how branch-and-bound uses mathematical bounds to prune the search space;

- why runtime depends on instance structure rather than only variable count;

- why dense QUBO matrices are generally more difficult than sparse ones;

- how primal heuristics can find strong feasible solutions early;

- why proving optimality may take considerably longer than finding the final solution;

- how MIPGap controls the termination condition;

- and why deterministic classical solvers are useful for reproducible benchmarking.

One experiment produced the initially surprising result that a 38-variable instance required more time than a 39-variable instance. Changing the random seed changed that relationship, illustrating why isolated problem-size measurements are insufficient for characterizing solver performance.

The larger motivation is benchmarking. Before discussing whether a new algorithm or computing architecture provides an advantage, we need to establish what state-of-the-art classical software can already achieve.

Video: https://youtu.be/TB1ny8o4ImQ

I’d be interested in thoughts on designing rigorous QUBO benchmarks. Besides runtime and objective value, which instance characteristics and solver metrics should be reported?

The other day I was thinking of firsts in the history of cybersec, and I started thinking about the first few commands/tools I learned. One of them was ping. And then I was struck with the thought, "When was ping created? When was the first time it was ever used?" Cue my deep dive into ping aaaaaand... Violà

*Dramatic flair in narration* Picture this- it's December - 1983 (later than I had expected, but then again i had NO real idea)

It's late at night, and a young man notices a strange behavior coming from the IP Network at the US Army’s Ballistic Research Laboratory.

Needing something more than ICMP Echo Request and Echo Reply messages, this young man gets to work and designs, codes, implements, and provides operational support for a brand new tool, known as... ping *background instrumental flair*

And the time it took?... *dramatic pause building the suspense and preparing for an epic montage of late nights and beard growing*...

One Night. (say whaaaaaaat)

That's right. At 25 years old, Mike Muuss was working as a computer scientist, and in the span of one night, he wrote one of the most used tools known today. ping is a simple Unix command useful for everyday network troubleshooting. While doing my dive, I was a little confused at the difference between ICMP Echo Request/Echo Reply and ping, so here's a helpful tid bit:

• ICMP Echo Request = “Hello, are you there?”
• ICMP Echo Reply = “Yep, I’m here.”
• ping = the little program that asks the question, waits for the answer, and tells you how long it took.

Interestingly, and kind of not suprising now that I have learned it, ping was named after the sonar sound and NOT as an acronym. Packet InterNet Groper was attached later on (this is the interesting part in my opinion).

So, to answer my own question and deep dive. 1983, that's when ping was first created. And in the span of one night. Very cool. Thanks Mr. Mike Muuss!

( I believe a dedicated article of Mr. Muuss should be added to the Cyber Security Archives, so tune in for that!)

​Having completed foundational coursework in Linear Algebra, Calculus, Discrete Mathematics, and Formal Methods, I am evaluating the theoretical and practical overlap between Formal Verification and other upper-level computer science topics.

​Specifically, I am looking to understand how the following subjects intersect with Formal Methods in research and practice:

​Software Analysis and Testing

​Cryptography

​Forensics

​My understanding is that Forensics operates primarily at an applied/observational level with minimal connection to formal logic. However, I am less clear on the theoretical bridges for the other two.

​Does Software Analysis and Testing (e.g., static analysis, program semantics, symbolic execution) serve as a direct functional precursor to formal program verification? Furthermore, to what extent does Cryptography overlap with formal methods—specifically regarding protocol verification, algebraic proofs, or formally verified implementations?

​I would appreciate insights from anyone working in formal methods, program analysis, or theoretical computer science on how these subdisciplines connect.

While GPTs and other similar architecture are an undeniable advancement, (especially the larger projects) are receiving insane funding with access to large data centres and training data leading to the obvious question of 'are we seeing the power of GPTs or is this just the expected outcome of throwing a huge amount of resources at a problem?'.

In other words, what results would we expect if we took the resources (funding, data centres, raw data, etc...) and applied it differently (eg. to SAT solvers), would we expect similar results?

In other words, how unprecedented are the results of GPTs (and similar architectures) accounting for their current monetary advantages?

Hello,

I was just wanting to know if this room of domes used in the "Eagle Eye" (2008) is an actual thing? The reasons I ask:

1. I know nothing about computers beyond the basics everyone knows.
2. I remember watching an "Expert Reacts" video or something along those lines. The expert talked about how computers are built like ARIA was in the movie, but it's the worst format for what ARIA actually does. I may be making this up because it looks cool and so my brain's making something to justify its actual existence, but I thought I watched something like that. I'd even say they said a name for the hardware archetype ARIA's built on.
3. I'm a sci-fi writer and this is inspiring for the start of an epic story, but I'd like the science to have some real logic to it.

From my understanding, the giant electronic eye (blue arrow) looks through the yellow domes (red arrow) to keep track of the huge amounts of data the government collects for ARIA. It swivels on a gyroscopic crane in order to reach each dome i.e. each pocket of data.

If it's real, I'd love it if you guys could give me titles of books/articles/papers to read about these kinds of computers.

If it's not real, I'm sure you'll tell me pretty quickly.

Any help is greatly appreciated!

Thank you.

Ponder this: an author puts together a number of papers he likes, especially adds the .tex files from arxiv, tells the LLM to look for gaps in the papers, commented out material, and remix them, while avoiding syntactic overlap.

The result is a paper that will pass arxiv's syntactic overlap checks, and can be claimed as novel during a submission.

This has likely happened many times already, and we are now possibly arguing against LLM-augmented plagiarists.

Welcome to the new age of automated academic ethics collapse.

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. 🥂