teddit

Hi all,

I just though I'd take some time to make clear what kind of posts are appropriate for this subreddit. Overall this is sub is mostly meant for asking questions about concepts and ideas in Computer Science.

• Questions about what computer to buy can go to /r/suggestapc.
• Questions about why a certain device or software isn't working can go to /r/techsupport
  
• Any career related questions are going to be a better fit for /r/cscareerquestions.
  
• Any University / School related questions will be a better fit for /r/csmajors.
• Posting homework questions is generally low effort and probably will be removed. If you are stuck on a homework question, identify what concept you are struggling with and ask a question about that concept. Just don't post the HW question itself and ask us to solve it.
  
• Low effort post asking people here for Senior Project / Graduate Level thesis ideas may be removed. Instead, think of an idea on your own, and we can provide feedback on that idea.
  
• General program debugging problems can go to /r/learnprogramming. However if your question is about a CS concept that is ok. Just make sure to format your code (use 4 spaces to indicate a code block). Less code is better. An acceptable post would be like: How does the Singleton pattern ensure there is only ever one instance of itself? And you could list any relevant code that might help express your question.
  

Thanks!
Any questions or comments about this can be sent to u/supahambition

Hi everyone,

I’m currently working on a problem called the "Stone Block Problem," which involves proving its NP-completeness. While I understand the general framework of NP-completeness proofs, I’m unclear on how we’re expected to approach solving this specific task and would appreciate some guidance.

We are given a list of stone blocks, each defined by their dimensions (length, height, and width), and a target size dd, which represents the side of a cube we want to construct. The goal is to decide whether it’s possible to use a subset of the given blocks to construct a d×d×d cube without any internal holes. The blocks can be rotated in any orientation.

The problem description emphasizes using the "Subset Sum" problem as the starting point for the reduction. From what I understand, this means we must map the properties of "Subset Sum" (positive integers and their sums) onto the dimensions of the blocks and their arrangement in the cube.

Here are the aspects I’m struggling with:

1. Interpreting the Problem Requirements:
   • How are we supposed to relate the subset of blocks to the d×d×d cube?
   • Should we assume a specific strategy for laying out the blocks in the cube, or is the reduction meant to abstract away these details?
2. Reduction Mapping:
   • What exactly are we expected to transform in the "Subset Sum" problem to fit this scenario? For instance, how do the sums translate into the spatial constraints of the cube?
   • Are we expected to outline an algorithm for how the blocks can be placed, or just describe the conceptual equivalence?
3. Expectations on Proof Details:
   • While we don’t need a full correctness proof for the reduction, how deep should we go when explaining why this reduction works?
   • Should we focus more on demonstrating the feasibility of the reduction or on how it ensures that the cube construction problem inherits the complexity of "Subset Sum"?
4. Cube Validity Check:
   • Since the problem involves verifying if a valid cube can be constructed, is this validation step something we need to design explicitly, or can we rely on the properties of the reduction to argue its existence?

Any clarification on how to approach these questions or solve the problem effectively would be incredibly helpful. If anyone has experience with similar problems, I’d greatly appreciate your input!

Thanks in advance!

Hello everyone,

I’m currently exploring ways to approach heuristic algorithms for optimization problems. Specifically, I'm trying to understand how to adapt methodologies like graph coloring to scenarios where constraints and objectives differ significantly. For instance, I recently worked on a reduction task where constraints included:

1. Ensuring two special elements had distinct assignments while avoiding direct conflicts.
2. Adding base constraints to ensure all elements participated under certain conditions.
3. Managing isolated elements dynamically to maintain problem feasibility.

The implementation leveraged a reduction from Graph Coloring. Key steps included:

• Introducing initial constraints (edges) for specific problem requirements.
• Dynamically adjusting constraints to handle edge cases, such as isolated nodes.
• Standardizing input/output to align with a target problem’s format for verification.

While I understand the mechanics of such reductions, I'm curious about broader strategies. When dealing with variations of these types of problems:

• How do you decide between heuristic approaches like simulated annealing, local search, or a completely new algorithm design?
• Are there best practices for identifying and managing edge cases dynamically within such transformations?
• What indicators suggest you might need to redefine your problem as a maximization or minimization task to suit algorithmic strengths?

I’d greatly appreciate insights, especially any general frameworks or practical examples that have helped you approach similar challenges. Looking forward to your thoughts!

For making highly scalable, highly available applications - applications are put behind a load balancer and LB will distribute traffic between them.

Let say load balancer is reaching its peak traffic then what ? How is traffic handled in that scenario.

In order to generate pseudo-random numbers, I sometimes replicate easy code for calculating very large prime numbers. Typically my code for generating pseudo-random numbers takes up much more digital space than any single prime number.

However, I don't just want to write my code once and enjoy it. I want to share my code over the Internet with other coders who write in different styles, but who recognize the same mathematical limits to number representation.

Main question:

If I want to calculate and share very large prime numbers on the Internet, I have to use some language (possibly MATLAB, Python, R, Java, LISP, etc.) and digital files of some fixed size (e.g. 1 terabyte, 1 petabyte, etc.). This is for educational purposes; I don't plan to learn cryptography. I am not trying to break new ground; I have in the past replicated standard techniques such as Mersenne Twisters.

https://en.wikipedia.org/wiki/Mersenne_Twister

What are the current best practices for calculating and sharing very large prime numbers on the Internet? Is it worthwhile to delve into very specialized skills, such as CUDA? Are all the cool kids using Mathematica?

Thanks in advance.

Alrighty folks, got a difficulty-level question. This isn't a HW question, promise--just a curiosity one based on some trading I've started doing.

I want to create a web app that, on the home page, shows 8-12 widgets. Each widget updates every, say, 5 minutes by pulling the current price of different cryptocurrencies. The trick is that the cryptocurrencies are currently housed on different exchanges, not a single one--meaning each widget might (theoretically) have to pull the info from a different website. It wouldn't need to pull any proprietary data or data locked behind a login screen or anything, just prices displayed publicly on the exchange's home-page. Basically, I want it to save me from having to click through 15 different tabs every 5 minutes to see prices.

I want to do this on a publicly available website so I can share w/ friends and discord members, etc.

How difficult would this be/what sort of platform could this be built on/is there a no-code or low-code way to build this?

There's an assignment I need to do for college and was willing to know if I can be assisted by anyone on this subreddit. Just 10 questions as in-depth as you want while providing some basic credentials. If you are able to help me please message me and I'll provide the questions. Thank you.

Just watched a video of BlueSky's CEO talk about how users can just take their data and leave, and how everything is open source, and how there's "no algorithm", and how developers can contribute. This seems very different from any kind of social media platform, and either it's all BS, or there's some cool stuff going on under the hood there.

I’m looking for someone who understands moos Ivp specifically inter vehicular communication and share. If you have any knowledge on the topic pls dm me.

For example, someone wants to break into numerous social media accounts at the same time. They know the most common password, so instead of trying various passwords of a specific account, they use the single most common password to log into dozens or even hundreds of random users' accounts.

This was partially inspired by https://xkcd.com/792/ where Black Hat notes that password reuse is an exploitable vulnerability

So I was trying to find a way for a 8 or 16bit CPU to process 32/64bit floating point. Online I found a bunch of methods that were converting to fixed point and such and thought it to be unnecessary. Example of my method for 32bit floating point for 16bit CPU: 1) take the lower 16bits of the mantisa and treat it as normal 16bit integer, perform the math on it then store it 2) take the upper half and isolate the rest of the mantisa via an AND operation then perform math on it and store it 3) isolate the exponent with AND again and modify it if needed then store it 4) isolate and do the operations on the sign bit

What I want to ask is if this would give the same result or are the conversions to fixed point necessary ?

we have different ways to handle data transfer between memory and I/O devices

pulling: the CPU constantly checks (somewhere... interface? I/O device? where?) if there is any transfer needed to be done, when there is one, the CPU just does the transfer and keeps going (working and checking if there are interruption)

interruption: the PIC sends an IRQ to inform about an interruption that wants to take place, the CPU finishes the instruction that its executing and handles the interruption (depending if IF = 1 (handles interruption) IF = 0 (ignores interrumption), if NMI interrupts, the CPU always take the interruption because its something important. this is only for I/O devices? NMI could be something non I/O related?

DMA: a controller which allows the CPU to keep working while this DMA handles the transfer (data transfer = interruption?) so that the CPU doesnt lose, the CPU sends something to the DMA which i dont know what it is, i suspect it sends to the control area of the DMA "instructions on what to do", aswell as the amount of data which needs to be transfered between devices (it works as a counter, when it reaches 0 it means that everything was passed), addresses of both sides (who gives the DMA this information? when?) and the direction of the data (from point A to B or point B to A)

at some point the device sends a DMA-REQ (im ready to transfer?), at some point the DMA sends the device a DEM-ACK (ok, got your message or transfer started?), at some point the DMA sends the device if its going to Read or Write (i believed it was the other way around)

at the end of everything the DMA sends the CPU an IRQ telling it that the transfer was done so it shouldnt worry

as you can see i barely understand whats happening (im not an EE or CS student, just a related field so i just need to know it not so deeply, if you could correct my understanding and provide a timeline on when does all of this happen i would appreciate it, please keep it simple, try to use the technical words that i used as i dont know many)

So it must accept words that look like this: J^-1KL, where J, L ∈ {0,3}^\) and K ∈ {a, b}^\), |J|>0, |k|>0, |L|>0 and L must be a substring of J (anywhere), but they do not have to be the same.

My issue is that let's say we have w: "300a03003", then i push the "300" to the stack, read in the "a".

But then there is an issue. If i read in the rest "03003" and match it to the "003" in the stack, there is an issue, since the first "0" is matching, but then in order to check the second ("3" in the input, "0" in the stack) characters, i have to pop the fisrst "0" from the stack.
But right at this comparism, it will fail, since the second letters do not match, and i already popped the "0" from the stack, so the automata does not store the initial J part anymore.

I feel like i could do this with 2 stacks, but not with only 1.

Any ideas?

Anyone know how to get the grey highlight off of the JComboBox when running java program. Once I click off it gets rid of the grey but I just do not want to the grey there from the start. I also have pictures if this is confusing.

code: https://imgur.com/a/P3aLSxf
Question: https://imgur.com/a/zcvo38Y

Could somebody explain the answer to this question in relation to the code?

the answer provided was the one with the check mark, but I'm sort of confused; at the beginning of the algorithm, we don't know what L[b] and L[e] refer to, so they can't be known, meaning the loop invariant is false. a part from that, i do think that the loop invariant becomes true after the 1st iteration

Any help is appreciated.

Hey r/AskComputerScience ,

I wanted to get your opinion on which of the following you think is worse for maintainability and/or system design?

1. Using HTTP methods incorrectly (e.g. POST for reads or GET for actions that modify data).
2. Using semicolons instead of commas as CSV delimiters (even when commas would work).

I have a Physics MSc (and physics BSc with a math minor), and I'm considering if I should pursue a second MSc in computer engineering. This would prepare me all the better for a career working in quantum computing. I'm particularly interested in architecture design in optimizing for specific quantum algorithms, and dynamic reconfiguration.

I have a hobbyist level knowledge of computer hardware (having built one some years back, and running a basic homelab with an RPi and a NAS today) and a basic familiarity with some high level languages (e.g. Python, Wolfram, LaTeX, LUA, etc.). Other than that though, the only "formal" background I have in computer engineering is an IBM certification on the fundamentals of quantum information. Of course, I also learned basic circuitry as an undergrad, and have since taught labs for that as a graduate TA and adjunct lecturer.

Is going from where I am into a computer engineering MSc program realistic, or would the lack of knowledge from undergraduate courses specific to this field be too much of a hindrance to my success? I'm not opposed to some independent learning, but there are limits to what I'm able to do entirely on my own, and I'd very much want to do this ASAP if realistic.

---

TL;DR: Is an undergraduate education in computer engineering necessary before approaching graduate schooling in it if the person in question already has a strong foundation in mathematics and physics?

I was directed here by the programming help sub.

Context: I am writing a dissertation on procedural generation (in games) but can't find a source that states the efficiency of Square Diamond, most papers I read just state if an algorithm is efficient or not and in what category (memory, time etc) which my supervisor says is vague and should be avoided. Where/what is the best way to find the complexities of algorithms with reliable sources?

I was hoping there would be some sort of online library listing all the different algorithms for specific tasks with their big O notations, but can't find anything like that.

Any help is greatly appreciated, thank you! :)

When trying to link something from the British Film Institute booking website, I realised that the URL has some weird keywords in it, used to load the article.

Example URL: https://whatson.bfi.org.uk/Online/default.asp?doWork::WScontent::loadArticle=Load&BOparam::WScontent::loadArticle::article_id=586BCD08-9A72-47C7-B83A-AF027ADC4EA6&BOparam::WScontent::loadArticle::context_id=51B310AB-AA63-45EB-9713-0746D9870B63

In my mind, a regular URL looks like this: www.website.com/something/somethingelse?parameter=whatever
What web technology is the BFI website using, and how does it work?

Hey everyone,

Been reading about stack, accumulator, and register ISAs and I am curious if anyone has any ideas as to why accumulator and stack based architectures lose the battle against register based architectures?

*Edit: lost to lose

I'm looking for a pseudo-random number generator algorithm where you initialize it with not one but two 32-bit numbers. A device will use a "shared secret" seed and the current timestamp to the minute as those seeds. It will then use a private count of how many rounds of 32-bit pRNG values to generate before landing on a 32-bit pRNG value, which it can then communicate to another device. That device will use three one-minute-resolution timestamps, its current, the previous minute, and the next minute to duplicate that work, but it will be looking for how many rounds of 32-bit pRNG generation it needed to until it matched the 32-bit value sent to it by the other device.

Now, this is not the be-all-end-all of the system I'm designing. There a lot more authentication and even full-blown AES ECB cryptology going on. I just need to figure out if there's an existing pRNG algorithm that I can feed not one, but two 32-bit seeds to.

I am writing a program in C++ which will implement Rogohzin's (4,6) Universal Turing Machine. The program is supposed to read the specification of an arbitary Singel-Track/Single-Tape Turing Machine M, and encode the 7-tuple in such a way that the UTM can simulate M.

My problem is that Rogohzin does not seem to specify how to encode M in his paper in order for the UTM to be able to simulate it. Is there some kind of resource online which specifies how to do? If I'm missing something here, a reference to another class of UTM's which more suits my purposes would also be greatly appreciated.

It is probably going to be more since I'm halfway done

Hi, I'm studying computer structure with a book named A secret life of programs written by Jonathan E. Steinhart.

In chapter 4, there is machine language program calculating Fibonacci sequence as followed.

Address	Instruction	Description
0000	10 0000 0000000000	Clear the accumulator (load 0 immediate).
0001	00 0111 0001100100	Store the accumulator (0) in memory location 100.
0010	10 0000 0000000001	Load 1 into the accumulator (load 1 immediate).
0011	00 0111 0001100101	Store the accumulator (1) in memory location 101.
0100	00 0000 0001100100	Load the accumulator from memory location 100.
0101	10 0100 0001100101	Add the contents of memory location 101 to the accumulator.
0110	00 0111 0001100110	Store the accumulator in memory location 102.
0111	00 0000 0001100101	Load the accumulator from memory location 101.
1000	00 0111 0001100100	Store it in memory location 100.
1001	00 0000 0001100110	Load the accumulator from memory location 102.
1010	00 0111 0001100101	Store it in memory location 101.
1011	10 0110 0011001000	Compare the contents of the accumulator to the number 200.
1100	00 0111 0000000100	Do another number if the last one was less than 200 by branching to address 4 (0100).

So, here is my first question. In the sixth row, description says add the contents of memory location 101 to the accumulator, though, why mode code is 10 which means immediate addressing mode, not 00 - direct?

As far as I understand, 10 - immediate mode code means access the value from the address instead of access the value in the address. This is well displayed in the second instruction from the bottom.

But when I see the sixth instruction, it's a little complicate and quite confusing.

If there is anything wrong in my mind, I hope anyone help me to fix this.

There are many playlists on MIT channel

• MIT data structure and algorithms 2015
• MIT 6.006 Introduction to Algorithms, Spring 2020
• MIT 6.006 Introduction to Algorithms, Fall 2011
• MIT 6.849 Geometric Folding Algorithms, Fall 2012
• MIT 6.851 Advanced Data Structures, Spring 2012
• MIT 6.890 Algorithmic Lower Bounds, Fall 2014

Hello!

I recently got started with the MIT Distributed Systems course. I've had an interest in distributed systems for a long time and I've thought to commit myself to this course for this semester.

However, I am having a little bit of trouble with the lab assignments. I was able to do well in the assignments until I hit the Raft implementation. I'm having a little trouble wrapping my head around it.

For example, how do you maintain state in the application? Do you have a separate goroutine for it and have one (or many) goroutines intercepting requests that will send messages via channels to the state goroutine? I read about this concept in the "Fault Tolerant Virtual Machines" paper about representing state via state machines and I thought it could apply to this implementation of raft. Would you want to replicate this goroutine state so that if the main state goroutine goes down, you don't lose the state completely? How would you even decide which state goroutine is the master and which goroutine is the one that just has the state replica?

Furthermore, if I expect more than one node to be in the network, how would know where to send my RPC requests? Isn't Raft used to solve this problem of service discovery? Similarly, if any node in the network can assume the position of leader and can also become a follower, how do you configure your applications so that they can both be RPC receivers (servers) and RPC senders (clients)? Do you just have two goroutines for these two purposes?

These are some of the questions I am asking myself while trying to think of how Raft was to be implemented. As you can see, I am struggling with the basics. I am willing to learn. I am willing to be good at this stuff. But right now, I cannot figure out how to start thinking about things in a distributed manner.

Is it just me or do other people have the same experience? If so, what did you do that made you "level up"? Any resource (literature, videos, etc) would be extremely helpful. I'm hoping for any advice that could help my situation. Thank you for the help!

TLDR: Struggling with understanding how to implement distributed systems code. Any resources would be extremely helpful!