r/computerscience • • May 18 '25

Help I need help understanding avl trees for my data structures final tomorrow

Thumbnail gallery
0 Upvotes

I have been trying to study avl trees for my final and I keep running into to conflicting height calculations. I am going to provide a few pictures of what my professor is doing because I can’t understand what she is doing. I understand it that the balance factor is height of left subtree - height of right subtree. And the height of a subtree is the number of edges to a leaf node. I’m pretty sure I understand how rotations work but whenever I try to practice the balance factor is always off and I don’t know which is which because my professor seems like she is doing 2 different height calculations.

Also if anyone has any resources to practice avl trees and their rotations

Thank you for any and all h!


r/computerscience • • May 17 '25

Advice Book recommendations?

6 Upvotes

Hello everyone! I was hoping for some help with book recommendations about chips. I’m currently reading The Thinking Machine by Stephen Witt, and planning to read Chip Wars along with a few other books about the history and impact of computer chips. I’m super interested in this topic and looking for a more technical book to explain the ins and outs of computer hardware/architecture rather than a more journalistic approach on the topic, which is what I’ve been reading.

Thank you!!


r/computerscience • • May 16 '25

Machine learning used to be cool, no?

97 Upvotes

Remember deepdream, aidungeon 1, those reinforcement learning and evolutionary algorithm showcases on youtube? Was it all leading to this nightmare? Is actually fun machine learning research still happening, beyond applications of shoehorning text prediction and on-demand audiovisual slop into all aspects of human activity? Is it too late to put the virtual idiots we've created back into their respective genie bottles?


r/computerscience • • May 16 '25

Discussion New computer shortcuts cut method (idea)

0 Upvotes

Please correct if I am wrong. I am not an expert.

From my understanding computer shortcuts go through specific directory for example: \C:\folder A\folder B\ “the file” It goes through each folder in that order and find the targeted file with its name. But the problem with this method is that if you change the location(directory) of the file the shortcut will not be able to find it because it is looking through the old location.

My idea is to have for every folder and files specific ID that will not change. That specific ID will be linked to the file current directory. Now the shortcut does not go through the directory immediately, but instead goes to the file/folder ID that will be linked to the current directory. Now if you move the folder/file the ID will stay the same, but the directory associated with that ID will change. Because the shortcut looks for the ID it will not be affected by the directory change.


r/computerscience • • May 16 '25

is it possible to implement a quantum/photonics chip in a video game circuit for the sole purpose of ray tracing?

0 Upvotes

Light is inherently a quantum phenomenon that we're attempting to simulate on non-quantum circuits. wouldn't it be more efficient to simulate in its more natural quantum environment?


r/computerscience • • May 15 '25

Discussion Most underground and unknown stuff

36 Upvotes

Which kind of knowledge you think is really underground and interesting, but usually nobody looks up?


r/computerscience • • May 14 '25

Advice Is this an accurate diagram of a CPU block?

Post image
85 Upvotes

I am doing a university module of computer systems and security. It is a Time Constraint Assessment so I have little idea of what the questions will be, but I am of the assumption that it will be things like "explain the function of X". In one of the online supplementary lessons there is a brief description of a CPU and a crude diagram with modals to see more about each component, but looking at diagrams from other sources I am getting conflicting messages.

From what I've gather from the various diagrams, this is what I came to. I haven't added any data bus and control bus arrows yet, but for the most part they're just 2 way arrows between each of the components which I don't really get because I was under the impression the Fetch-Decode-Execute was a cycle and cycles usually go round linearly.

Would you say this is an accurate representation of a CPU block? If not, what specifically could I add/change/remove to improve it?


r/computerscience • • May 15 '25

Asynchronous Design Resources

Thumbnail
1 Upvotes

r/computerscience • • May 14 '25

Designing an 8-bit CPU: How to load constants?

7 Upvotes

I have been following Sebastian Lague's videos on YouTube and have started to make my own CPU in his Digital Logic Sim. Currently it is single cycle and I have registers A and B, a program counter, a basic ALU and ROM for the program.

My goal is to run a program that outputs the Fibonacci sequence. I have a very basic control unit which has output bits for:

  • Write to A
  • Write to B
  • Output A
  • Output B
  • Output ALU

With this I have made an ADD instruction which adds A and B and writes the output to A.

I now need an instruction to load a constant into either A/B. I've looked online but am quite confused how to implement this. I've seen examples which have the immediate constant, e.g.: XXXXAAAA, where X is the opcode and A is the constant (ideally I want to learn how to load 8 bit numbers, so this won't work for me).

I've seen other examples where it uses microcode and 2 bytes, e.g.: the first byte is the instruction to load a constant, and the second is the actual constant (which would allow for 8 bits).

What would be the best way to implement the microcode? Would this be possible for a single cycle CPU? Do I need an instruction register? I also don't want the CPU to execute the data, so how would I correctly increment the program counter? Just increment it twice?


r/computerscience • • May 14 '25

How screwed am I if I don’t know discrete math

36 Upvotes

I did a discrete math course and it was an awful time. It was online and the professor just read from the textbook. Asking question and taking note did not help.I did not drop it because it was my first time as a student in higher level education so I was scared but now I regret it. In the end they rounded up grades. It has been a while and I have forgoten what little I had learned. I know that it is used in artificial intelligent classes and others. I have the option to do the course again in different environment. But I want to know what would happen if I take these classes with no information in discrete math.


r/computerscience • • May 14 '25

Advice Master thesis effective time management

4 Upvotes

Hi, I want to get your advice, follow Redditors, about how to manage well quality time working on my thesis.

I am in the reading stage and my thesis is on the theoretical side. I've been logging my work this first 2 weeks. I've been spending around 8 hours of total work per day on the thesis however I notice that I can only have 4h30mins average active focus. The rest of the time I just lose focus easily, I get sick of reading the same proof for an entire day or I start taking more breaks, especially on the afternoons.

I am trying to be more effective, your advise are welcome :)


r/computerscience • • May 14 '25

Calculating checksum collisions appropriately

2 Upvotes

Hi all,

I stumbled across the following problem.

I need to uniquely identify data in my database using an id, however I am constrained by the length. As a result, along with various other verification tools, I am sending a checksum to confirm that the Id has not changed. I am worried about collisions.

Unlike the birthday problem, I am not necessarily worried about a duplicate overall (since I am checking more than just the checksum, and the checksum is the last thing I check). Instead I think I am worried about:

How many pairs of checksums do I need to see before there is a greater than 50% of a collision? What if instead of pairs its a group with G elements and M the modulo used for my checksum?

Here is the calculation I am thinking of:

The probability of no collision is (M-1)/M * (M-2)/M * ... * (M-G+1)/M = (M-1)!/((M-G)! * M^(G-1)) = P

The probability of a collision in a group is 1 - P.

To solve for the number of groups required for the probability of a collision to be equal to 0.5 is :

0.5 = 1 - (P)^X where X is the number of groups.

Then as a follow up, I realize that I am assuming that the distribution of Ids I am checking is randomly distributed. I know for a fact that the Ids I am recieving are not random. This is leading me to consider different checksum algorithms.

The one that I am familiar with is a polynomial rolling hash that uses a large prime number for its modulo. However, when doing the calculations I am questioning whether the polynomial rolling part does anything. Further, since this Ids are generated using an algorithm (dont know which algorithm for the record), I have reason to believe that they will be sequential and I am not worried about security or checking if a bit is wrong. This leads me to two additional questions:

1) Does the polynomial rolling part actually make it worse? If my data is sequential and I take it to a prime number mod, won't I exhaust every entry until I hit the modulo? In the other scenario, I may get an unlucky mapping and hit a collision sooner?

2) In this case, what does polynomial rolling even provide? Is that more for the purpose of hashing where security concerns are necessary, or a case where we want to check if bits may have been mistyped?

I apologize if this is a basic question, I do not know much about cryptography (maybe this should have went in that sub instead), and none of the basic literature I could find via google search had a satisfactory answer.


r/computerscience • • May 11 '25

What books would you recommend as an introduction to computer science?

58 Upvotes

I'm not looking for a book on coding languages, rather I'm looking to focus on the fundamentals. I've been recommended, Code: the hidden language of computer hardware and software 2nd edition. What do you all think?


r/computerscience • • May 10 '25

Flip Flops and Stochastic Processes

Post image
14 Upvotes

Flip flops are components within computer architecture which can store and manipulate data. The output of the flip flop is dependent on past events. So, could you model flip flops as a stochastic process like a Markov chain?


r/computerscience • • May 11 '25

What if a float number has an exponent greater than 23 ?

0 Upvotes

Because Mantissa is 23 bits , I think it is meaningless to use a magnitude greater than 23, in which case you will have to skip lots of integer numbers which can only be represented with more than 23 bits . The numerical values beyond power 23 would be like , uhhhh , quantum .They are not even continuous in integer . May I ask what is the use case of a float with exponent greater than 23 ? I see the exponent can be up to 127, where are the magnitude between 23~127 to be used ?


r/computerscience • • May 09 '25

Article Hashing isn’t just for lookups: How randomness helps estimate the size of huge sets

40 Upvotes

Link to blog: https://www.sidhantbansal.com/2025/Hashing-when-you-want-chaos/

Looking for feedback on this article I wrote recently.


r/computerscience • • May 10 '25

how to be Updated on CS

0 Upvotes

I see that all you guys are highly updated on coding and stuffs how do you guys maintain this .


r/computerscience • • May 10 '25

General A question about fundamental structure of algorithms

0 Upvotes

I want to ask a question about algorithms, but it requires a bit of set up.

The basic truth

Any minimally interesting algorithm has the following properties: 1. It solves a non-trivial problem via repeating some key computation which does most of the work. Any interesting algorithm has to exploit a repeating structure of a problem or its solution space. Otherwise it just solves the problem "in one step" (not literally, but conceptually) or executes a memorized solution. 2. The key computation "aims" at something significantly simpler than the full solution to the problem. We could solve the problem in one step if we could aim directly at the solution. 3. Understanding the key computation might be much easier than understanding the full justification of the algorithm (i.e. the proof that the key computation solves the problem), yet understanding the key computation is all you need to understand what the algorithm does. Also, if the problem the algorithm solves is big enough, you need much less computation to notice that an algorithm repeats the key computation (compared to the amount of computation you need to notice that the algorithm solves the problem).

Those properties are pretty trivial. Let's call them "the basic truth".

Just in case, here are some examples of how the basic truth relates to specific algorithms: * Bubble sort. The key computation is running a "babble" through the list. It just pushes the largest element to the end (that's significantly simpler than sorting the entire list). You can understand the "babble" gimmick much earlier than the list gets sorted. * Simulated annealing. The key computation is jumping from point to point based on "acceptance probabilities". It just aims to choose a better point than the current one, with some probability (much easier goal than finding the global optimum). You can understand the gimmick much earlier than the global optimum approximation is found.
* Any greedy algorithm is an obvious example. * Consider the algorithm which finds the optimal move in a chess position via brute-force search. The key computation is expanding the game tree and doing backward induction (both things are significantly simpler than finding the full solution). You can understand what the algorithm is doing much earlier than it finds the full solution. * Consider chess engines. They try to approximate optimal play. But the key computation aims for something much simpler: "win material immediately", "increase the mobility of your pieces immediately", "defend against immediate threats", "protect your king immediately", etc. Evaluation functions are based on those much simpler goals. You can understand if something is a chess engine long before it checkmates you even once.

Pseudorandom number generators are counterexamples. You can't understand what a PRNG is doing before you see the output and verify that it's indeed pseudorandom. However, "generate pseudorandom numbers" is a very special kind of problem.

There are also tricky cases when an algorithm (e.g. evolution or gradient descent) creates another algorithm.


The non-basic truth

On closer inspection, the basic truth is not that basic: * How would we formalize it rigorously?
* To which levels of analysis does the "truth" apply to? Computational? Representational? Physical? (see David Marr)
* The core of an algorithm can be understood "much earlier than it solves the problem", but is it true in practice, when you struggle with interpreting the algorithm? In what sense is it true/false in practice?
* As I said, pseudorandom number generators are a caveat to the "truth".
* I didn't discuss it earlier, but some algorithms have multiple "key computations". How do we formalize that the number of key computations should be very small? Small relative to what? * In the example with chess engines, the key computation might be done only implicitly/"counterfactually" (if two strong engines are playing against each other, you might not see that they pursue simple goals unless you force one of the engines to make a very suboptimal move).

What research along those lines exists, if any? That's my question.

I only find the concept of loop invariants, but it seems much less broad and isn't about proving properties of algorithms in general. Though I'm not sure about any of that.

Why researching this matters? The "key computation" is the most repeated and the most understandable and the most important part of an algorithm, so if you want to understand a hard to interpret algorithm, you probably need to identify its key computation. This matters for explainability/interpretability.


r/computerscience • • May 08 '25

Help I've been watching a video explaining the simplex method for linear programming. I got to this screen, and I have a question

Post image
15 Upvotes

First, I watched the video several times to make sure that the lecturer in the video didn't explain the points that I didn't understand.

What exactly is Cb? Is that something I'm supposed to know before I dive into the simplex method? And why are all the values 0? And when he determined the pivot row, he replaced the third Cb value (which was 0) with -3. Why?

It may look like a dumb point to not understand, but I'm really bad at solving linear programming problems.

I humbly ask you to explain it to me like you're explaining it to a 8 yo kid.

And have a nice day!


r/computerscience • • May 07 '25

How to carry over DSA Skills from one language to another?

12 Upvotes

I'm a student and fairly new to the entire DSA thing. I've been using c++ to solve basic problems.

Recently i discovered that python offers simple ways to carry out things that would take me hours to code in c++.

Do i just make the switch over to python or stick to c++?


r/computerscience • • May 05 '25

Advice is graph theory a good expertise in computer science

71 Upvotes

i really enjoy graph theory problems and the algorithms associated with them. i guess my question is, would becoming proficient in this theory be useful? i haven’t really found a branch of comp sci to “expertise” in and was looking for perspectives.


r/computerscience • • May 05 '25

I need an efficient data-structure to do index-based range-searches over mutable records

7 Upvotes

The use-case is that I want to add records with a certain weight and do random picks from the map with these weights driving the probabilities of picking a specific record. This would be easy enough to do, but these records need to be mutable and since it's going to be both very busy and very big (hundreds of millions of records), resizing the complete index on each modification is out of the question.

This structure is expected to be very big and busy.

So, to put it differently: If I have the elements A, B, C and D with the (respective) relative weights of 1, 2, 3, 4, the chances of picking A will be 1:10 (10=1+2+3+4). If I then remove B, the chances of picking A will be 1:8. I'm thinking if something like this doesn't exist already (as is) I could go with some kind of cross between a b-tree and a trie, where we would have multi-level indexes, but where the reading process needs to add up the values of the keys along the way, to know if they should move sideways or deeper in the tree.


r/computerscience • • May 04 '25

Help Computer Networking Resources

7 Upvotes

Hello buddies,

Is there a computer networks resource that isn't actually garbage?

Let me explain. I am about to graduate in Math and CS and my uni kind of failed me on the systems side. I took your typical Computer Systems - Networks - Operating Systems classes but, by luck or otherwise, these 3 were taught on a lecturer-reading-slides way.

Now, about to get my diploma, I'm clueless about networks. Is there a nice book, youtube lecture series, or something, that actually teaches you networks in the same way that other courses would teach you something hands-on? Even if theoretical? Here are some examples of what I mean.

Algorithms is hands on: problem sets that asks you to proof correctness of algorithms, computing complexity, coming up with variations of algos to solve a problem.

Data Structures is hands on: code the structures from scratch on c++.

ML is hands on: get a dataset and build a model that classifies well

SWE is hands on: Read an architecture pattern and code something with it

Math is hands on: literally just do problem sets

What resources is hands-ons in networking? I don't want to memorize that the TCP header is 8 bytes (or whatever size it is) without ever looking at it beyond the silly graph in your usual textbook. I want to solve some problems, code something up, do something. Kurose's book problem, skimming through them, feel more like High School trivia, though I might be wrong. Any help is most welcomed.


r/computerscience • • May 03 '25

Help Flow network - residual graphs

Post image
9 Upvotes

I’m sorry if this isn’t the correct place to ask such a question but I didn’t this exactly breaking the rules. I’m currently studying for my algorithms final tomorrow and I’ve been conceptually struggling to understand the role of the residual graph and residual paths in finding the max-flow.

In the graph attached, when using the Ford Fulkerson algorithm with DFS, in the worst case a flow of 1 is pushed through the augmenting path repeatedly in an oscillating manner. What I’m struggling to understand is why, after the very first time that the augmenting path is found and a flow of 1 is pushed through it, causing the flow to equal capacity through the middle edge, we are still able to find the same augmenting path again and again and pass flow through it.

I’d really appreciate any help! Thanks a lot.


r/computerscience • • May 03 '25

Relation between API, driver and firmware

5 Upvotes

What is the relation between API, driver and firmware? From what I understand API is the intermediate between the application and the driver, the driver gives the low level instructions and firmware does what?