r/compsci Jan 01 '21 Silver Helpful Hugz

CompSci Weekend SuperThread (January 01, 2021)

95 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 Wholesome Hugz Helpful

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

521 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 7h ago

Boids: An artificial life simulation of a bird flock

Enable HLS to view with audio, or disable this notification

110 Upvotes

r/compsci 7h ago

3 Quick Questions from the Hardest Math Test in the World

Thumbnail medium.com
27 Upvotes

r/compsci 5h ago

Is it normal for an IT rep to send me to Logmein123.com and request control of computer?

0 Upvotes

Sorry if this does not belong here. I called IT at the hospital I work at and I’ve called three times before but this time it was different. They asked me a bunch of questions about my computer, sent me to logmein123.com, asked me to download the software, and then sent a request to take over control of my computer remotely. Is this normal? The guy wouldn’t tell me why he needed to do that and was being kind of weird.


r/compsci 5d ago

Is there such a thing as non-asymptotic analysis of algorithms for small n cases?

131 Upvotes

I am reading lecture notes on a data structures and analysis of algorithms course and I find it interesting but I find two things annoying:

  1. Compiler implementations and hardware specific details and runtimes are omitted.

  2. All run time analysis is asymptotic, even though no computer can run infinitely long. Nothing in the course worries about real world usage and real world optimization in finite time for everyday usage.

I'm concerned about realistic scenarios like the efficiency in the first hour of use, for example. I'd rather reduce area under the run time curve at finite times far less than infinity, than worry about what the worst possible case is. Worst possible case is not good enough for me, I want to also optimize better than worst possible cases I want to optimize in good conditions so that it is even better and perfectly synced up to the hardware it is using.


r/compsci 10d ago

What are the chances are that quantum computers capable of breaking current cryptography already exists with one or more countries and is kept secret and probably weaponised like the British did during World War 2

314 Upvotes

During the world war 2, the British team lead by Alan Turing, created Bomba, by improving techniques of polish bombe, to secretly breaking cryptographic messages of the Nazi Enigma machines. They kept it secret and didn't act on the decrypted intel until the D-Day.

That brings me to this question.

The information that quantum computing can eventually break all cryptography algorithms that is in use today, is in public domain. Definitely, that is a threat most defence experts are likely working on a priority. So how likely is that one of the defence research group of the world already have it and probably breaking into anything they want?


r/compsci 12d ago

Similar probabilistic algorithms like Hyperloglog?

109 Upvotes

Just recently learned about the Hyperloglog and I was wondering if you have any other cool probabilistic algorithms that I should look into. Also, if you have ever used them, I'd love to know in which scenarios.

For those who doesn't knew HyperLogLog, I wrote very basic notes to myself here -> https://adriacabeza.github.io/2023/03/15/hyperloglog.html


r/compsci 22d ago

Lang based on Computability Logic? What might this look like?

Thumbnail self.AskComputerScience
50 Upvotes

r/compsci 25d ago

Google reveals another experimental operating system: KataOS

Thumbnail theregister.com
265 Upvotes

r/compsci 26d ago

Warning: CSCE - the latest sketchy CS conference by Hamid Arabnia

247 Upvotes

I'm a CS professor and lately, my academic email account has received multiple Call for Participation emails from "IEEE CPS - Computer Science, Computer Engineering & Applied Computing" CSCE'23 conference. My colleagues noted they got the same emails and were wondering about it so I did a little investigating because their CFP looked eerily familiar.

Allegations about these conferences (including on the previous reddit threads as well as elsewhere) are that there is no real peer review happening and it is a predatory conference that just accepts anything and cashes in on registration fees. Many legitimate researchers have complained that they were duped by the conference and when they attended it (always in Las Vegas, as far as I can tell), there were some real research presentations but it was obvious that there was no meaningful peer review being conducted to assure that the research was sound.

update - after filtering "@american-cse.org" as spam, I'm now getting daily emails for the same CFP from "@world-comp.org" addresses.


r/compsci Mar 01 '23

The Implementation of the Coordinate Hash Trie

Thumbnail github.com
85 Upvotes

r/compsci Feb 28 '23

A Trie Variant Balancing between Time, Space, and Simplicity; And a C Implementation of the Aho-Corasick Algorithm Based on It

107 Upvotes

I think this sub is a suitable place to share my work.

The approach is called coordinate hash trie.

The idea is very simple. We use a global hash table to store all edges in a Trie. Each edge is stored as a dictionary item (from, symb)->to.

We use a special hash function:

h(from, symb) = (from*m + symb) mod H

, where m is the size of the alphabet, and H is the number of slots in the hash table. For a trie with n states(nodes), we take H = (n-1)/alpha where alpha is the constant load factor. No rehashing, resizing, or reallocation is required.

We could prove that the time complexity of transition from one state to another, is O(1) for the average case and O(m) for the worst case. The space complexity is O(n), unrelated to m.

Comparing to other compressed trie variants like double array trie, or using n hash tables each for a state, this variant provides stable space consumption and is very easy to implement.


r/compsci Feb 26 '23

Cache Oblivious Algorithms

Thumbnail jiahai-feng.github.io
118 Upvotes

r/compsci Feb 24 '23

Gradient Boosting with Regression Trees

57 Upvotes

Hi guys,

I have made a video on YouTube here where I explain what gradient boosting is and how it works.

I hope it may be of use to some of you out there. As always, feedback is more than welcomed! :)


r/compsci Feb 24 '23

Techniques for Scaling Applications with a Database

Thumbnail thenewstack.io
20 Upvotes

r/compsci Feb 21 '23

MINIX is an awesome way to learn a wide range of CS concepts

Thumbnail github.com
188 Upvotes

r/compsci Feb 20 '23

Man beats machine at Go in human victory over AI

Thumbnail arstechnica.com
511 Upvotes

r/compsci Feb 19 '23

Odd Sketches

Thumbnail pncnmnp.github.io
10 Upvotes

r/compsci Feb 12 '23

Dijkstra Comparing Computer Science to Alchemy (1989)

Thumbnail cs.utexas.edu
262 Upvotes

r/compsci Feb 13 '23

Voting Preference Sorting a list

4 Upvotes

A list of eight items to be sorted s = {a, b, c, ... h}. Fifty voters each contribute their ordering preferences in the form of a three-item priority list: preferences = {first, second, third}

What method sorts the eight items according to the set of fifty 3-item preferences, without the introduction of any sort of arbitrary weighting?

What have I tried:

  • A 3-dimensional count seems to leave me with three lists of counts, one for first, second, and third preference. That problem space looks to me like a partial set of permutations.
  • Start with only one vote, which leads to a count of votes per item in the set. What happens when instead I specify a preference for the ordering of two items? Which looks to me a like a relationship between nodes, rather than just the nodes.

r/compsci Feb 10 '23

Mathematicians Complete Quest to Build ‘Spherical Cubes’ | Quanta Magazine | s it possible to fill space “cubically” with shapes that act like spheres? A proof at the intersection of geometry and theoretical computer science says yes.

Thumbnail quantamagazine.org
182 Upvotes

r/compsci Feb 10 '23

Starting now: Reading group for "The Joy of Abstraction" by Eugenia Cheng

Thumbnail topos.site
25 Upvotes

r/compsci Feb 10 '23

How do I traverse every point in a 3D area without backtracking and minimizing the least amount of turns possible?

10 Upvotes

Alright, let's say I have an array of discrete 3D points that make a rectangle of x, y, and z length. I want to visit every point in the least amount of turns possible without backtracking. Let's say that to visit a point you can only increase x, y, and z by +-1 or 0. The pattern ends up being a snake-like pattern where the axis is traversed in descending order to minimize the number of turns. Though getting this to happen in code eloquently has been a real fucking bitch.

So far, I've generated the area with no care in which order they're put in. Then I sort so the longest axis is moved through first, then I go through once and create subsets for every time two axis values have been changed (xChange && yChange) || (xChange && zChange) || (yChange && zChange) and add every one of those elements back to a new list where every other subset is in reverse order. Then I do that again but create a subset this time when every axis value has been changed (xChange && yChange && zChange). This cant be a novel problem, right? I can't find anything online about this.

Example input: https://pastebin.com/JbXx19rf Example output: https://pastebin.com/sWsfXq3G


r/compsci Feb 06 '23

The story behind the Packing Chromatic Number paper

Thumbnail bsubercaseaux.github.io
84 Upvotes

r/compsci Jan 30 '23

Normalization for multimodal type theory. "We prove normalization for MTT, a general multimodal dependent type theory capable of expressing modal type theories for guarded recursion, internalized parametricity, and various other prototypical modal situations." [abstract + link to PDF, 39pp]

Thumbnail arxiv.org
109 Upvotes

r/compsci Jan 28 '23

Don't fear the spin lock

53 Upvotes

It's a common exercise in programming to synchronize access to data between threads. A simple mutex or other critical section tool will do the job. But sometimes, performance matters.

The problem with mutex's, or regular locks in high level languages, is that the waiting thread may be put to sleep since it cannot access the resource it wants. And this behavior is usually desirable - except when it isn't.

There is a time cost associated with putting the waiting thread(s) to sleep and waking them when the resource is ready.

A simple heuristic can be used to determine whether you should try to upgrade regular wait locks to spin locks. A spin lock is where the thread actively tries to access the shared resource and doesn't go to sleep.

(h): if the shared resource is guaranteed to be locked for a sufficiently short period of time.

While working in Orvina, performance increased dramatically with a careful selection of locks to upgrade to spin locks - and the effort was less trouble than what was expected.

There are likely many programs out in the wild that would experience real world benefits with more diligence in the choice of locking mechanism implemented. It would be quite the feat if compilers could deduce or suggest a specific lock type and insert the correct one. Perhaps that's one improvement AI will contribute to.

https://preview.redd.it/c9t2dpu1ctea1.jpg?width=768&format=pjpg&auto=webp&v=enabled&s=ef75d8d723f8a9ed6c025f5047e644b99c92ccd6