/r/AskComputerScience
Ask Computer Science Questions And Get Answers! This subreddit is intended for questions about topics that might be taught by a computer science department at a university.
Ask Computer Science Questions And Get Answers!
Before posting please read our rules.
This subreddit is intended for questions about topics that might be taught by a computer science department at a university. Questions do not have to be expert-level - it's perfectly fine to ask beginner questions. We all start somewhere. All we ask is that your questions be on-topic.
If you have questions that aren't directly about computer science, here are some other subreddits that can likely offer you more help:
If your post is off-topic, or violates one of our other rules, your post may be removed.
/r/AskComputerScience
I claim that this grammar is unambigious
<E> ::= <T> | <T> U <T>
<T> ::= <F> | <F> ++ <T>
<F> ::= <S> | ( <E>)| <F>*
<S> ::= [a-z]
I was told that, this is wrong because: The problem with <F> being left-recursive is that it's impossible to choose between the <S> rule and the <F>* rule. This means a parser would need a lookahead as long as the length of the input string to know which rule to 'unfold.
I sort of understand a little bit but can someone make this more clear for me since I don't totally understnad? I mean the program won't match with <F>* unless there is a "*" after the statement so don't get what they mean? BTW "*" is kleene star and not "times".
I’ve read that TT recommends content based on a user’s interest vs user’s network. That should be fairly easy to replicate for YT Shorts and Meta Reels right? If yes, there is no secret sauce with TT’s algo right? If not, do you think they’ve discovered an entirely new ML technique that recommends content better? (similar to transformers for next token prediction).
Hi everyone. I found a way to solve a variation of 3-partition problem (given a list of numbers, can we partition it into triplets that have the same sum? Number of triplets can be anything unlike in 3 way partition problem where goal is to partition the list into 3 parts where sums are equal but can have any number of elements.) where all integers are unique, in polynomial time. Is this version NP-complete or not? Thanks.
Say we have one room with a list of events, and we want to schedule the most number of events with no overlaps. Why does choosing the events with the earliest finish time that don't overlap yield the maximum number?
Hi Redditors, Im writing a paper and want to include three key differences between Turing Machines and Non-deterministic Finite Automata. Id appreciate it if anyone could let me know if these three points are in fact correct:
I'm implementing a board generator for a hexagon variant of Sudoku. The board is roughly in the shape of a diamond, where the first row only has one hexagon, then one below has two, followed by three, etc., until the halfway point, at which point, it decreases again until the last row has one hexagon. The generator will make games of different sizes, where size n means the board has n^2 cells, the middle row has n elements, and each cell can have values 0-(n-1). In this variant, there are no cell clusters, unlike the clusters of 9 in normal sudoku (3x3), but there is the additional constraint that there are two columns to check for uniqueness, not just one, and that only one row has all elements.
When I first began implementing this, I noticed that it is impossible to generate games of sizes 2, 4, and 6. Two is simple enough to visualize. For size four, I worked it out analytically on a board of size 4 using variables to show that a contradiction must eventually be reached. I figured the same, in a more complex way, must exist for 6. However, to my initial surprise, it is possible to generate games of size 8, 10, etc., all even numbers I've tested so far, meaning that 2, 4, and 6 are just special cases.
When it comes to generating boards of even numbers, however, the execution time is significantly higher than odd numbered counterparts. I can generate a board of size 8 in 30 seconds, but then a board of size 9 in 73 milliseconds, despite the exponential grown of this problem as the game size increases. I can even generate a board of size 15 in half the time it takes for size 8.
I'm having a hard time determining both why 2, 4, and 6 happen to be special cases (even though I know why 2 and 4 fail specifically), and even more, why subsequent even numbered boards, while possible, take significantly longer to generate. The only major difference I've noticed is that, while the number of edges is always even, the number of nodes is even or odd depending on the game size, though I'm not sure how this relates exactly.
This difference in execution speed seems constant regardless of the heuristics I use for constraint satisfaction. Currently, I'm using the following:
Here are a few basic stats, if we think about the game as a graph and n as the game size:
If anyone has any insights as to how this relationship between even-ness and difficulty of making an assignment works, even an idea or intuition, please share. I'm also open to hearing other, perhaps lesser known, heuristics I can try to reduce the backtracking overall, especially if it applies to this even / odd problem.
For reference, here's an example game of sizes 3x3, with a valid solution, and 4x4, where I used variables a-d to prove that eventually, an inconsistency must be reached. It also helps visualize what larger versions of the game will look like:
A computer is made up of transistors that hold electricity in a state of ON ( 1 - our interpretation ) and OFF ( 0 ) These numbers 1 and 0 are not physically stored in the hardware, because they are numbers that we use to interpret the electrical state of the transistor. And computer memory - the mechanism is just electricity staying in one state either ON or OFF ( the switch stays in place ). So what do CS mean when they say a computer has storage and memory if a computer hardware is just electricity.
Was reading the Alex Hu System Design Book.
I understand how it helps in making the system robust, and fail proof, by introducing async communications.
But sort of stumbled upon how does it matter particularly in scaling systems. In fact, would it not slow them down ?
Lets say a request made by user goes to the load balancer and then the web server. Now the web server (producer) adds it to a Message Queue, items are then picked from the MQ by the consumer, who eventually fetch the state info and necessary data from DB/cache. Here MQ would be having some size limit as well, and scaling the producer and consumer will only alter the MQ size. Even if we remove the MQ, the web servers were also essentially scaling and doing the same right ?
Is my understanding wrong ?
so ik that it mainly consist of transistors alrranged in ceratin ways representing the AND/OR/NOT,etc.. gates, but how does a flow of electricity with just changing the transistor arrangement make the computer think logically and perform eg arithmetic operations
Hello everyone! I just started studying computer science and for one of the assignments I need to conduct an interview with someone who is actively in the computer science line of work. Personally, I don't have any connections to that specific field, so I figured I would use social networking to find anyone interested. It will be a short interview. Does not have to be over the phone or anything. We can just privately message each other. There will be about 10 questions and I can give them to you beforehand.
If anyone is interested please send me a private message :) Thank you!
Not sure how to solve this. I know we could use BFS but not sure what the time complexity could be. Any tips?
i want to make a class diagram which represents my buttons on a main menu screen. i’m coding this using python and importing tkinter to make my buttons with. i’m so stuck on how to make this and it’s due in at midnight pls help 🙏🙏
I've been trying to wrap my head around how computers work. They can do math, complex algorithms, and can be programmed to do any number of things.
And I haven't gotten a very concrete answer to how they work. I've seen videos explaining the hardware, i've heard people talking about logic gates, transistors, and binary language.
But how does a bunch of circuits and switches, become complex user interfaces, and video games, and operating systems? How does the computer know the difference between 0000001 and 00010000? How does a bunch of simple circuits and electric currents produce computation? What is computation? And why does it make sense? Am i missing something here? It there a massive canyon in my understanding that i haven't been seeing? Other questions i have are: how does binary become any given programming language? And how does the computer know where data is stored? Or even how to do anything? How does one program hardware that has no preexisting programming? Or is it inherent to the hardware?
Im going to stop there. But i hope you guys can answer at least of few of these questions. And please try to be nice
Given the following sample of a segment table: [Segment numbers : 4, 5, 6, A, B, 2001 with corresponding Base addresses: 6000, 5000, 55F0, 59D8, 4A38, 2001 and Lengths: 1000, 500, 7D0, 100, 7D0, 500] for a 28 bit logical address space with a maximum segment size of 32 KB, I am asked to identify the physical address of 0x2111E.
As far as I understand how the process works, I am supposed to find the segment number of the logical address in the table, get the corresponding base address and then add the offset which can be deduced as soon as the segment number is identified to get the physical address. But I cannot find the segment number in this table, hance how am I supposed to get the physical address? I don't ask necessarily for the solution, just a hint at what I am missing here, thanks!
I am in college right now and am planning to minor in CS, and im getting near the end of the first course of computer science needed, but throughout this semester I have had a lot trouble really understanding and applying the material. I have never been bad with anything technical or math related but it feels with computer science I'm barely getting by if I can. Idk if anyone else ever had a similar situation and has an idea of what helped them get past it. It's making me doubt if CS is for me and if it works for me.. It just sucks as if I dont do well on the upcoming exam next week I will need to retake the course. Also experiencing a lot of pressure to take this minor as well.
Let me start off with that I am not an expert in Computer science, so if my questions come off as extremely easy to answer and silly then please forgive me.
I heard that it was mathematically proven that if you can solve one NP problem in polynomial time then you can solve all of them in polynomial time.
So Let’s say that someone hypothetically solved the Boolean Satisfiability Problem (SAT) in polynomial time today thus proving P = NP. I understand that that means all other NP problems can be solved will much less difficultly than previously thought. But wouldn’t there still be some degree of significant difficulty in solving all these other problems or at least some of them?
Will all currently know NP problems be solved before 2025 starts if P was proven to equal NP? Or will there still be some NP problems that will take years to solve even with a proof that shows that P does equal NP and vastly improves computer software?
so I got 2 questions in this topic:
•In a K map, why must the groups be of powers of 2 only
•how can we prove De Morgan's law
Hey guys! I'm coding an AI for Risk: Global dominations which is a popular online implementation of the board game Risk. I'll be writing a symbolic AI which will manually calculate paths for capturing territories and bonuses. Currently I have been stuck on finding a method to find the paths which the AI should take to capture a territory bonus (pics if you are unfamiliar with the game).
I am intending to represent the board as a graph, with nodes representing territories (and their troop/player data) and edges representing the connections between these territories. Examples of the AI pathing to take territories would be this position for the green agent to take Europe, and this position for the pink agent to take Asia. In this problem, we can have multiple starting stacks, with the goal to travel to all unoccupied territories and preferably end with the troops on external border territories to guard from invasion. Note that I am only looking for ways to find these paths from multiple starting points, not the evaluation of them. Also note that each territory can only be visited once, but as shown in the pink agent example, one territory can make multiple attacks off the same territory, it just cannot be recaptured.
Algorithms to achieve this, tips on board representation and fields of study covering similar problems would all be greatly appreciated! Cheers.
I'm taking a Architecture & Assembly course in school right now and we're being taught x86-IA32.
I will say, I rather enjoy it. It's pretty cool learning this stuff, but I am curious if it's like... useful?
I'm sure assembly languages aren't useful for... say web developers... but are any of them useful for anyone?
My specific questions:
Given a set A = {2,3,5,....}
decide if every possible combination with repeated usage of set A makes the following true. Where sum(A) ≠ sum(D)
, where D = every possible combination with repeated usage.
Edit: D must contain at least 2 multiplicities of an element. For example {2,2,3,5,6...}
Edit: A must consist of ONLY distinct numbers > 1. No repeated elements in A
I think this a special case of subset sum and partitioning, but we're allowed to use elements more than once.
Here's an example where the output would be FALSE
When A = {2,4}
, and the counter-result is {2,2,2}
. Notice that {2+2+2} = {2+4}
, as they both sum up to 6.
Since sum(S) = sum(D)
, the expression sum(A) ≠ sum(D
is not true thus the output is FALSE
So this is a question I’ve had for a few years now and since I made a reddit account I can finally ask people. If this subreddit isn’t the right one for this question I’d appreciate someone told me where I should ask.
Onto the actual question: Let’s say you uploaded something, sent a message, searched something or whatever else and then deleted it. I understand companies keep backups but if it were a company with millions and millions of users, do they really keep all of that or do they purge it after a certain amount of time? I don’t know much about how storing data works but I think the storage is limited, meaning they can’t keep deleted data indefinitely forever or they’ll run out of storage. Can anyone explain to me how it works?
I had a professor suggest to me at one point that this niche might be up my alley. Seems worth looking at, at the very least!
What's the difference? I can't understand
Just curious.
And if not, Why does it always start at C?
I want to design and create pinball machines as a hobby. To that end, I'm studying for ETA International's Gaming and Vending Technician (GVT) certification. I'm looking at the list of necessary competencies, and everything seems to be in order until I see the following entry:
4.2.3 Perform Hex to Funny Hex conversions
...what the hell is Funny Hex? I've never heard of it and the internet has so far come up empty. Can anyone here please enlighten me?
SOLVED: The president(?!) of ETA International replied to my email to say the following: "After speaking with someone from the R&D department, it seems that the item slipped into the competencies from a SME’s training material (e.g. 61453 from decimal base 10 to hexadecimal base 16 is F00D). I checked the exam and confirmed 4.2.3 is not on it. We have submitted this for an update and will remove the item."
Greetings dear Scientists. Yesterday I study Analytical Geometry. And find an interesting formula. ( At least its interesting to me.) Which is Dividing a Line-Segment in a Given Ratio. For better understanding I describe the formula then asking the question.
If you have point1 and point2 in a rectangular coordinate system and you want to segment the line which point1 and point2 it holds you should use this formula:
point1(x1,y1)
point2(x2,y2)
segment ratio => m1:m2
pointSegment(x3,y3)
x3 = (m2*x1 + m1*x2) / m1+m2
y3= (m2*y1 + m1 *y1) / m1+m2
if you choose segment ratio 1:1 than its the center of the line.
x3 = (x1+x2) /2
y3 = (y1+y2) /2
I thought this formula can be using virtual memory locations to be better paging. ( I know in paging methods you cant use segmentation method. Because paging needs to be doing in flat memory model. But I don't know why it cant be by using this way)
Thank you for giving a time.
hi, I'm working on my A level coursework on the testing section, my program is a game and I'm not sure what to put as the test type for some of my tests (normal/erroneous/boundary). so for example, part of my game involves remembering a sequence of characters (eg. a2k2k) and inputting them. if I do a test on the user inputting an incorrect string and in the test say to enter 'aaaaa' would this be normal or erroneous data? because I thought it might be erroneous but then I was thinking that erroneous data might actually be using incorrect data types like '!' or inputting a 'backspace'. I hope this explanation made sense and I apologise if this is just me being a silly (I've been working on this thing for too long)
I'm no expert.(Just curiosity)
After testing with some examples, I believe that this algorithm should work, but my proof relied on the assumption that the number of back edges equals the number of cycles, which is wrong, since the existence of a back edge only indicates whether there's a cycle or not. Any hints on where to proceed?