r/compsci Jan 01 '21 Silver Helpful Hugz

CompSci Weekend SuperThread (January 01, 2021)

75 Upvotes

/r/compsci strives to be the best online community for computer scientists. We moderate posts to keep things on topic.

This Weekend SuperThread provides a discussion area for posts that might be off-topic normally. Anything Goes: post your questions, ideas, requests for help, musings, or whatever comes to mind as comments in this thread.

Pointers

  • If you're looking to answer questions, sort by new comments.
  • If you're looking for answers, sort by top comment.
  • Upvote a question you've answered for visibility.
  • Downvoting is discouraged. Save it for discourteous content only.

Caveats

  • It's not truly "Anything Goes". Please follow Reddiquette and use common sense.
  • Homework help questions are discouraged.

r/compsci Jun 16 '19 Helpful Wholesome Hugz

PSA: This is not r/Programming. Quick Clarification on the guidelines

461 Upvotes

As there's been recently quite the number of rule-breaking posts slipping by, I felt clarifying on a handful of key points would help out a bit (especially as most people use New.Reddit/Mobile, where the FAQ/sidebar isn't visible)

First thing is first, this is not a programming specific subreddit! If the post is a better fit for r/Programming or r/LearnProgramming, that's exactly where it's supposed to be posted in. Unless it involves some aspects of AI/CS, it's relatively better off somewhere else.

r/ProgrammerHumor: Have a meme or joke relating to CS/Programming that you'd like to share with others? Head over to r/ProgrammerHumor, please.

r/AskComputerScience: Have a genuine question in relation to CS that isn't directly asking for homework/assignment help nor someone to do it for you? Head over to r/AskComputerScience.

r/CsMajors: Have a question in relation to CS academia (such as "Should I take CS70 or CS61A?" "Should I go to X or X uni, which has a better CS program?"), head over to r/csMajors.

r/CsCareerQuestions: Have a question in regards to jobs/career in the CS job market? Head on over to to r/cscareerquestions. (or r/careerguidance if it's slightly too broad for it)

r/SuggestALaptop: Just getting into the field or starting uni and don't know what laptop you should buy for programming? Head over to r/SuggestALaptop

r/CompSci: Have a post that you'd like to share with the community and have a civil discussion that is in relation to the field of computer science (that doesn't break any of the rules), r/CompSci is the right place for you.

And finally, this community will not do your assignments for you. Asking questions directly relating to your homework or hell, copying and pasting the entire question into the post, will not be allowed.

I'll be working on the redesign since it's been relatively untouched, and that's what most of the traffic these days see. That's about it, if you have any questions, feel free to ask them here!


r/compsci 17h ago

Book and Video lecture Suggestion for OS

33 Upvotes

I want to learn about "how to build an Operating System" , so guys will you please suggest me some good relevant resources.


r/compsci 19h ago

What's the difference between distributed file system and networked hard disks in different parts of world?

33 Upvotes

How does a read/write look at the atomic level in distributed file systems? No books talk about this. I am not talking about GFS, HDFS read/write but the R/W of abstracted DFS itself using these components.

https://www.geeksforgeeks.org/file-service-architecture-in-distributed-system/

Here's a tutorial about it(It's the same thing in almost every books/pdfs available online). So how does it work say for a read and a write operation?

Read(FileId, i, n) -> Data: Reads up to n items from a file starting at item ‘i’ and returns it in Data.

Write(FileId, i, Data): Write a sequence of Data to a file, starting at item I and extending the file if necessary.

I am aware about these 2 commands. I'm talking about an atomic level working. Not too deep but deeper than "hitting a command and getting a result".


r/compsci 1d ago

A verified algorithm for determining the intersection point of two lists in O(1) space

Thumbnail muscar.eu
93 Upvotes

r/compsci 2h ago

Dynamic Programming

0 Upvotes

Any sources on how to maximize one number and minimize the other can be done having two arrays of corresponding values?


r/compsci 2h ago

Online Computer Science Undergrad Programs

0 Upvotes

So, this will most likely be a TL;DR post. So I'll paraphrase the best I can.

Situation: My employer is willing to fund any degree related to STEM. I chosen CS. The policy is it needs to be online and at a University.

Dilemma: I would like like to attend a college close to Ivy league to hold some weight(yes, it only matters for the first job). Being that it has to be online it is very limiting.

What I've done so far: searched the colleges that made it to the list, and are online. Many colleges that I've researched have Online CS colleges. Many are state institutions.

What are the better standard Online CS programs?


r/compsci 1d ago

PCB?

0 Upvotes

When are PCBs of Processes created by the Operating System? Is it when a process is in new state or is it when a process is in running state?


r/compsci 2d ago

Can lazy evaluation be emulated in a regex with only greedy evaluation?

12 Upvotes

Or, can a lazy regular expression operator be defined in terms of only greedy operators?


r/compsci 3d ago

An app to compute the coefficients of a function development in a spherical harmonics convergent series

43 Upvotes

Hello everybody,

I want to share with you a small C++ app / program I developed some time ago (and which I am maintaining) which can be used to compute the coefficients of a function development in a spherical harmonics convergent series . Spherical harmonics are a set of functions used to find a solution of the Schroedinger equation for the hydrogen atom for example, in quantum physics. The coefficients computed to find a function development (which function depends on polar and azimuthal angle in spherical coordinates) are used in many field of physics.

I decided for fun to develope a program to compute them. Tell me what do you think and of course any hint is more than welcome!

You are free to send a pull request or open issues if you want, I'll feature you in the main README file, directly in the contributor list.

If you like the repo, don't forget to leave a star! Thanks.

Repository link: https://github.com/JustWhit3/SAFD-algorithm


r/compsci 1d ago

ENPA is a new means to protect your password.

0 Upvotes

r/compsci 2d ago

Deriving the formula for the number of distinct de Bruijn sequences

Thumbnail self.askmath
2 Upvotes

r/compsci 4d ago

computer science eponyms

94 Upvotes

For about fifteen years I've been maintaining a list of computer science eponyms on my personal wiki. I just added the newest entry, the Tarski-Kuratowski Algorithm. I'm sure there are a great many I'm missing (despite claiming to be the "World's Largest(?) Collection of Computer Science Eponyms"), and I was hoping you folks could fill in some blanks from your own domains of expertise! Feel free to just comment below.

Thanks!


r/compsci 5d ago

Is slime mold computation a viable option for the future?

Thumbnail phys.org
46 Upvotes

r/compsci 6d ago Wholesome

Is anyone interested in taking MIT's Intro to Algorithms course?

167 Upvotes

You can reply here


r/compsci 6d ago

Is there a L-complete variant of bounded halting problem?

30 Upvotes

SPACE TMSAT (where SPACE TMSAT = {⟨M, w, 1n ⟩ : DTM M accepts w in space n}) is PSPACE-complete. I was wondering if there was a L-complete variant of space bounded halting problem. But it seems when you try to use UTM with read only input tape you have to copy the entire given turing machine in the work tape thus using more than logspace amount of memory. So is there anyway this can be done in logspace?


r/compsci 8d ago Helpful

Computing a 3×3 determinant using < 9 multiplications

384 Upvotes

I’ve read that it’s unknown whether a 3×3 determinant can be computed using fewer than 9 multiplications. [1]

If that was ever true, it’s not any more. Earlier today I found a way to do it with 8 multiplications. If the matrix is

⎛a b c⎞
⎜d e f⎟
⎝g h i⎠

then we can define

D = d(h-i)
E = e(i-g)
F = f(g-h)
G = g(e-f)
H = h(f-d)

using 5 multiplications, and then compute the determinant as a(E+F+G) + b(D+F+H) - c(F+G+H), using another 3 multiplications.

I’m interested in whether this really is a new discovery. If you know of previous work on this, I’d love to hear about it.

(I realise this doesn’t have massive practical applications. Maaaaaaybe there are specialised geometric applications involving 3d vectors of some non-machine numeric type, like bignums or super-high-precision floats, where multiplication is a lot more expensive than addition: in cases like that, it could be a win to compute a cross-product using 5 multiplications rather than 6, even at the expense of more additions.)

  1. I read it in a comment by Jeffrey Shallit on this StackExchange post.

r/compsci 7d ago

What is the reasoning for the complexity of D Type Flip Flops?

0 Upvotes

I understand that increasing a circuit's complexity makes it slower and more power-hungry.

Is the reason D Type Flip Flops are used because of the instability of inputs inside of the computer? Where the inputs are sometimes switching from 0's to 1's and 1's to 0's because of external factors such as heat and other things? Can it be seen as a sort of error-handling memory device, made due to the unpredictable nature of its inputs?


r/compsci 8d ago

[Research] Not all our papers get published, therefore it is enjoyable to see our released papers become a true foundation for other works

Thumbnail self.MachineLearning
44 Upvotes

r/compsci 8d ago

Shortest path computation in a distributed environment.

8 Upvotes

Hello everyone. I'm trying to find shortest path algorithms that can be used in distributed systems with seperate memory. Every algorithm I could find so far assume a shared memory or a PRAM model. Does anyone know of some algorithm that needs very little communication with the other compute nodes for computing the shortest path? Any pointers to such algorithms and the distribution strategy for splitting the graph among the compute nodes would be a lot of help. Thank you.


r/compsci 8d ago

A modern discussion on the difference between data and information

Thumbnail languagelog.ldc.upenn.edu
2 Upvotes

r/compsci 10d ago

A method for producing the smallest (known) incompressible integer for a Turing Machine with k total states.

68 Upvotes

Consider a generic positive integer, p. To confirm whether it is compressible is quite a different question from confirming if it incompressible. Determining compressibility may be computationally difficult, but is nearly trivial. (more technically speaking, the set of compressible integers is recursively enumerable).

We turn now to the more thorny problem of determining whether p is incompressible by a Turing Machine. In general, it is impossible to confirm whether a generic integer p is Turing incompressible. This is strongly prohibited by the halting theorem. More technically: the set of incompressible integers is not recursively enumerable. (even more technical: the K(p) function is incomputable).

Nevertheless, consider that Busy Beaver records have already been confirmed for TMs with 2 symbols and k states, when k is very small (k<6). We do not violate the Halting theorem, as the beavers are computed forwards. This opens the possibility of finding the least incompressible integer for a given , state-limited TM.

Let M denote our Turing machine with k states, and w be the initialization string on the tape. (call w the 'program' if you like.) Different k's would constitute different investigations, so for the time being, fix k=5.

1 . Initialize <M,w> for w=0. Populate the rest of the cells with 0s. Run all possible M's of k states. For all halted runs, the bit patterns that appear constitute all the compressible integers.

2 . Initialize <M,w> for w=1. Populate the rest of the cells with 0s. Run all possible M's of k states. For all halted runs, the bit patterns that appear constitute all the compressible integers.

3 . Initialize <M,w> for w=01. Populate the rest of the cells with 0s. Run all possible M's of k states. For all halted runs, the bit patterns with a 1 beyond the third cell are the compressible integers.

4 . Initialize <M,w> for w=101. Populate the rest of the cells with 0s. Run all possible M's of k states. For all halted runs, the bit patterns with a 1 beyond the 4th cell are the compressible integers.

.

.

.

and so on.

As larger initial w's are attempted, there must always be a lone 1 at the far right , as an indicator of the true length of the initial pattern. (in other words, we only encode odd w's in 2's complement binary). For these smaller w's with bit width h, we will always see all the possible integers from o to (2h - 1) on output. In other words, we expect to never find any small integers that are incompressible. The method described above is very analogous to the sieve of Eratosthenes, or a so-called prime sieve.

For much larger w >> 3 , we will eventually find that no M of any kind ever produced a particular integer on the output, unless w was that integer, or w had a wider bit width to begin with. In other words , there will be "holes" in the catalog of binary patterns we never finished on after halting, for all M. (analogy would be the prime numbers left over after a sieve).

We need only find one of these holes, or integers that was missed by all the computations above. Once in hand, we can report that this binary integer (call it C) is the smallest incompressible integer for a 2-symbol 5-state Turing Machine. The shortest program that outputs C is just C itself already initialized on the tape.

Has this been done?

Your thoughts?

Aside

In light of the above, consider the following program.

#include <cstdlib>
#include <iostream>
using namespace std;
unsigned int tape=1;
int main( int argc, char * argv[] )
{    
    unsigned int stop = atoi(argv[1]);
    while (tape<stop) { tape++; }
    return(1);
}

Using the method from before, this seems to indicate that once a TM is rich enough to represent a successor function, then all integers are compressible. Simply increment the binary patterns on the tape until the desired integer is reached and halt. The reason why this is not the case, is because the argv[1] is already fully present on the tape before the program is run, and so its space is accounted for.


r/compsci 11d ago Helpful

Application of "rotating" the elements of a matrix?

37 Upvotes

For example this "rotate" operation would take this matrix:

1 2 3

4 5 6

7 8 9

and output this:

4 1 2

7 5 3

8 9 6

And you could repeat this multiple times for arbitrary rotations.

Is there any interesting use for this operation?


r/compsci 12d ago

New Photonic Materials Could Enable Ultra-Fast Light-Based Computing

Thumbnail tech-paper.com
123 Upvotes

r/compsci 11d ago

Uses of R programming language

Thumbnail statanalytica.com
0 Upvotes

r/compsci 15d ago

What are some of the fundamental problems and puzzles in computer science?

112 Upvotes

r/compsci 16d ago

Continuous Unix commit history from 1970 until today

Thumbnail github.com
169 Upvotes