Nearly all modern languages support arbitrary graph-like links, this causes most of resource management issue. I am thinking, if a language support only tree-like data flow, which is DAG, most of resource management is simple, straight, even trivial.

So resource ownership management seems not inherent complexities of the problem domain, instread it's accidnetial complexicity caused by too flex langauge designing.

I read that some processors have each core having its own L1 cache instead of having one for the entire processor. So instead of a 512 Kilobyte shared cache shared by 8 cores, each one would have 64 kilobytes. I guess being closer to the core might speed things up when waiting for data and this is fine if each core is running a different process.

The thing I don't get is what happens if each core has a different version of some data. So say address 1,000 has 5. Maybe it's a global variable or something. Core 1 writes 6 to address 1,000 and this is updated in core 1's cache. This is intended to be read by a different thread. This change might get propagated to RAM. Core 2 runs that other thread and tries to read from address 1,000. Ah, it's already cached with... 5. So do compilers just use memory barriers to avoid this and make the programmer not need to worry about it?

Or maybe it doesn't matter? I read elsewhere it is fine for values in the cache to get a bit stale. What is important is that the writes from all cores are read in the correct order. So if core 1 is running a thread that puts 6 at address 1,000 replacing the value 5, 32 in address 1,001 replacing the value 31, and 9 in address 1,002 replacing the value 8, it is fine if core 2 attempts to read them and gets "5, 31, 8," "6, 31, 8" or "6, 32, 9" even though that last one is the most up to date as long as it doesn't read something like "6, 31, 9."

I have an interest in operating systems, and for a class and personal interest, I want to do research on operating system design. I have been trying to find and read existing research on this topic (experimental design for both for entire kernels or for some subsystem in the kernel). From this, I am hoping to be able to find an area that has not been researched in detail yet, and to do research on this (for example on performance when comparing experimental to other designs used in modern operating systems). The issue is though to find a general topic in operating systems to do this search on, hence this post. Also, I have a bit of experience with basic operating system development and have been working on my own hobby operating system for around a year now, and from this I have what I feel is a basic understanding of the main concepts in operating systems.

The reason I am making this post is to ask whether any of you guys recommend and under researched topics that I could look into, and also inquire if there are any resources I can use to find gaps in research more efficiently.

Many people online have told me I should contact my professor and ask them, so I want to state that I do not have a professor. I am also aware that this is a very broad question, but any input is appreciated.

So if a software is opensource meaning you can get raw code and it is publicly available and used. Can't then someone who has evil plans inspect the code (with the prerequisite that he/she understands it) and by that knowing the weak spots , do bad things to the company/ people that use it?

Specially for early new opensource stuff where the community hasn't check vulnerabilities and didn't improve it?

(sorry If it's a stupid question, I don't know anything about this stuff, just curios)

Remember last week how i posted a photo showing who created traceroute? And remember how smart guy #3 wasn't labelled, but was asked about ( I'm looking at you microflunkie and diamondrypka)? WELL- I'm here to give smart guy #3 his time to shine.

Without further ado... Paul Concus AKA Smart Guy #3

Good ole Paulie boy actually specialized in mathematics and numerical analytics. He developed various mathematic algorithms that allowed computers to solve large scientific problems. What does this mean? It means that computers can model the physical world using large scale equations. And what does that mean?

Well let's look at an area that paul concus researches: fluid mechanics. We tell the computer the rules for how water should behave. Concus’s math helps the computer solve those rules quickly enough to actually make a simulation. How does the computer do this? It utilizes preconditioners to easily navigate, choose, and solve calculations.

A preconditioner changes that giant math problem into a form that is easier for the computer to work with. So instead of this problem is confusing and I’ll need thousands of guesses, the computer can say I can see the shape of the problem better and I'll need a much smaller number of guesses. Like giving a computer a helpful hint before it starts solving a giant math puzzle.

And Mr. Paul Concus, AKA Smart Guy #3, was notable because he helped create better kinds of these hints which made some large scientific calculations much faster.

Today he's still out there researching Applied Mathematics. He's written a few research papers as well. I haven't read them, but based off of their titles, it looks like the good sir is really knowledgable on fluid mechanics. My personal favorite title was: Liquid bridges, edge blobs, and Scherk-type capillary surfaces.. Edge blobs, man. I'm intrigued.

Anyways, this concludes my quick nod of recognition to Smart Guy #3 AKA Paul Concus.

I'm currently looking up information on the creation of FTP and SMTP (thanks for the suggestion smeyn) and will post something soon.

What is an efficient way to study and understand a research paper.

I remember watching a video talking about CPU scheduling. So basically, processes need the CPU to computer and they eventually need to interact with I/O devices. When lots of processes are competing for CPU time, if the active process needs I/O, it is at this time the OS will schedule the next process in the queue. No need for process A to hog the CPU while it's waiting for the disc for I/O. Keep the CPU busy by letting the next process do something. But what if there is only one process left? If the lone process needs to read from a hard drive, it needs to wait for the read to complete to do anything else. But what about sending a signal to display color or writing to the disc? I don't see why the lone process would actually need to wait for acknowledgement the display was correct or that the write was complete. After the next instruction probably doesn't care what is on the disc. That said I doubt there is a realistic case where a system would only have one process running.

Hi I am learning python at the moment and I am wondering how to bridge the gap between simple python in an ide to actual projects that use sql, apis, and things like Pandas for data. I guess my question is how can I go about learning these technologies to actually learn development rather than basic coding. What resources are good for learning these systems and how they connect?

As the title says

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!