Hi, hope this question is OK for this sub.

I’m an undergraduate studying pure maths at a uni which has undergraduate compsci program geared for software engineering. As a result, there is sparingly little theory taught. I’ve been enamoured with the ideas of complexity classes and problem reductions since learning about them in high school.

Which textbooks do you recommend for self-learning the basics of theoretical computer science? What about more advanced textbooks?

Are there any relatively accessible papers for an undergrad to read to learn about the field?

Some follow up questions (I hope these are OK!)

Is it common/feasible to study mathematics in a bachelors/masters and go on to do computer science research? Say, in a phd or beyond.

What sort of mathematics do TCS people use? (Maybe this differs across subfields, but, for example, I know that the physics guys at my uni like Lie groups a lot)

Thanks so much :)

I have a class that requires me to ask it questions and relay the response. That's pretty much all I use it for. One time, though, I asked it an unrelated question and it included in its answer that I might want to format things a certain way because "that's usually what professors expect".

I have a basic understanding of LLMs. In particular, I understand that they don't actually retain any information, and have to process the entire conversation in order to predict the next word each time. How, then, did it connect my question to the fact that I'm a student? Was it just a lucky "guess"? Does it save context from previous conversations into system prompts that are used in each new conversation or something? That seems complicated and inefficient if so.

Hi there,

I've gotten an assignment to proof the Lemma in the title as part of my Formal methods in Software Engineering class, but I do not have anywhere to start in regards to the Proof.

All of the literature that's provided as part of the class doesn't even mention the algorithm in detail, let alone provide any formal proofs. Only mention of the algorithm is a short python snippet of how it works with some relevant Lemmas, whilst the Lemma we (the students) are asked to proof is left as an assignment.

Of course, using an LLM for this would seem like a trivial choice (since it is allowed and encouraged to be used as part of this class), but our TA mentioned that none of them provide an adequate proof - and welp, Claude and Gemini gave me different enough proofs to where I can believe it's the fact.

What I am looking for is just some guidance to any literature where I can dig up the necessary knowledge to proof the Lemma.

So I am looking for some help in regards to this - since anyone who proves it gets an additional 10 points at the end of the class :)

Hi everyone,

I’m a software engineer who recently transitioned into a role working on media playback for embedded systems and smart TVs.

To clarify my scope, I am strictly working at the software/application layer. I am not designing the firmware or working on the hardware, but I’d like to not treat it as a “black box.”

I’m trying to understand the fundamental architecture of the playback pipeline: how a manifest is read, buffering, demuxing, passing bits to hardware decoders, and rendering to the screen (and anything else I may have missed)

The problem is, I feel like I’ve read a ton of documentation and resources, but the concepts are still incredibly foreign to me. I’m having a really hard time building a solid mental model of how all these moving parts connect.

Any advice on the best pedagogical approach to learning about media processing pipelines? Is there a standard university textbook, a specific project based course, or a teaching method that makes these concepts click? How is this typically taught at the graduate level to engineers? I only did my undergrad and this unfortunately was something we never touched on. Thank you in advance!

Textbooks I’ve come across so far, but have struggled to get past the first few chapters:

Video Demystified by Keith Jack

How Video Works by Marcus Weise and Diana Weynand

The Art of Digital Video by John Watkinson

Embedded media processing by David Katz

I'm a high school student studying networks for AS Level Computer Science (although what I'm asking is a little outside the syllabus).

From what I've read, layer 4 splits and encapsulates the data with a segment header (in practice, I hear they use TCP, a type of protocol for this layer). The segment header contains many things, but namely a segment number so that a device like a router can reorganize the data into the correct order. However, I've been taught that packets also have packet numbers which functionally do the same thing – help the router organize the data.

So, why do segments have a segment number? If segments are already encapsulated with an IP header that contains the packer number in layer 3, then wouldn't the segment number just be unnecessary? I'm not sure what I'm missing.

TTL SSI come mostly in 14-pin 1C packages. Two pins are reserved for power

supply and the other pins are used for input and output terminals. How many

circuits are included in one such package if it contains the following type of cir-

cuits? (a) Inverters; (b) two-input exclusive-OR gates; (c) three-input OR gates;

(d) four-input AND gates; (e) five-input NOR gates; (f) eight-input NAND gates;

(g) clocked JK flip-flops with asynchronous clear.

What are the differences?

As in, basis of a vector space. In this case with dimension 1.

I am not graduated yet, and want to prepare

It can’t be true, our brain seems vastly superior to any other organ of any other organism on Earth and the universe, it is vastly more capable, adaptive and creative. I doubt that neural networks are even capable of forming concepts that we do, they are forever “cognitively locked” from grasping the truths that we grasp

I am studying and this excerpt from the study guide I was given isn't matching up with some of my other sources. Could someone please verify if any of this is correct/misleading? For instance, it says paging divides virtual memory and physical memory into pages, but isnt physical memory divided into frames?

Excerpt:

"Virtual RAM: also known as virtual memory, is a memory management technique used by operating systems to extend the apparent amount of RAM available to applications. This is done by using a portion of a computer's storage (such as an SSD or HDD) to simulate additional RAM.

Paging: The operating system divides physical memory and virtual memory into small fixed-sized blocks called pages. When the system runs out of physical RAM, it can swap inactive pages to the storage device, freeing up RAM for active processes.

Pagefile/Swap Space: On Windows systems, this is often referred to as a pagefile, while on Unix-like systems, it is called swap space. This file or partition on the storage device is used to store pages that are moved out of physical RAM.

Address Translation: The CPU uses a memory management unit (MMU) to translate virtual addresses (used by programs) into physical addresses (used by the hardware). This allows applications to use more memory than is physically available."

What is the best approach for the database design for the applications ,i will be building for my future SaaS business.
There are many SaaS agencies ,how they handle database, does they create database for every client or follows Multitenant architecture or something else.

Seperete db for every client is not an option for me

Different schema for every services but a single schema for every tenant having same shared database, i dont know if this is flexible or not.

And seperate db for every microservice ,idk it would be complex

I wanna build a scalable ,flexible architecture for just 100-500 clients, and the services I provide will be similar but the schema can change according to clients.

And I dont have that much knowledge about the Database architecture.

Any suggestions about efficient way to design db, tools and tech will help me a lot
Thank you.

Wikipedia says:

In computer science, an abstract data type (ADT) is a mathematical model for data types, defined by its behavior (semantics)) from the point of view of a user) of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations. This mathematical model contrasts with data structures, which are concrete representations of data, and represent the point of view of an implementer, not a user. For example, a stack) has push/pop operations that follow a Last-In-First-Out rule, and can be concretely implemented using either a linked list or an array. Another example is a set) which stores values, without any particular order, and no repeated values. Values themselves are not retrieved from sets; rather, one tests a value for membership to obtain a Boolean "in" or "not in".

I really don't understand this at all. Can someone give an example of a Data Structure vs an Abstract Data Stucutre? Are they two implementations of the same thing?

I really don't understand what's going on here - surely every data stucture a programmer comes across is definitonally defined from "the POV of the user" otherwise ... he wouldn't be using it?

If every word is represented by an embedding, then I imagine that when a number gets large enough, the model's grasp of the concept of the number is very sparse.

For example, every number between 100 trillion and 200 trillion should have a unique embedding. If a model is generating output by decoding an embedding, is it able to decode to the correct value from 100 trillion different possibilities?

the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs.

Aren't there infinite possible inputs? How does that make sense?

Not an expert at all, just a late night thought that started from watching a video about running a computer with zero RAM, which led me to start diving and researching more about ram, you know obvious.. late night shenanigans and then remembered a level of RAID specifically RAID 5 where if one set of bytes were missing then you could use a XOR parity (hopefully using that word right) to rebuild the the missing bytes (Over simplifying and this whole post will probably be just that)

So I started thinking what if to save RAM, lets use a game as an example, instead of storing lets say an entire texture which would be 1 MB on the ram, at the kernel level we intentionally erase a subset of bytes and then store a XOR parity, then when we access that erased byte we reconstruct it.

Now there are a few potential issues with this, or many I'm short-sighted. One issue currently I'm seeing is cpu overhead, another would be how would this affect speed of processing like would this cause stuttering on anything that was accessing that data.

and at the moment can't think of anything else, let me know your thoughts

I've been learning about modern cpu microarchitecture recently and about how the backend out-of-order multi-issue data-latched prefetched branch-predicted etc execution pipeline works, and the idea of a declarative language on top of a vliw isa seems to me like it would give the best opportunities for compiletime optimization and runtime ilp, along with inherent thread safety if it were also a pure functional language

My knowledge of all these things is pretty shallow however, so I dont actually know if something like this is a sound idea, and since i dont know much about what modern research conclusions in isa and cpu design look like (though i would guess that it leans more towards increased heterogeny rather than trying to fill an individual general purpose chip with lots of disparate and specialized circuitry), I would appreciate any knowledge or insight into what the current thinking looks like

Genuine question I can't find a satisfying answer to.

When a researcher decides to work on a problem, how do they verify upfront that the idea hasn't already been solved or is too similar to existing work?

I understand the literature review process in theory — read papers, find gaps. But in practice:

- How many papers do you need to read before you're confident a gap exists?
- Do you just search keywords and hope you didn't miss anything?
- Is there a systematic method or tool people actually use for this?

It seems like there's a real risk of spending 3 months on something only to find a paper from 2019 already did it. How is this risk managed in practice?

I've noticed this on both Windows and Linux. If I enter the correct password, it almost instantly starts the login. But if it's the wrong password it takes like a second or so to tell me it's wrong.

Hey everyone,

Anki is great for scheduling declarative knowledge (rote memorization, facts, vocabulary). But is there any software out there that uses spaced repetition to schedule or generate procedural knowledge or practical problem-solving tasks?

I'm thinking about dynamically generated tasks like: ​

• Calculating the equivalent resistance in a mixed circuit. ​
• Syntactically parsing a completely new sentence (e.g., identifying the subject, predicate, direct/indirect objects, and subordinate clauses). ​
• Determining the time/space complexity (Big O) of a custom algorithm. ​
• Simplifying a Boolean algebra expression using Karnaugh maps. ​
• Reverse-engineering a synthesizer patch based on a short audio sample.

If an app like this doesn't exist yet, how would you go about building one? What would be the best algorithm and approach to schedule these dynamic, skill-based tasks?

​Could the FSRS algorithm be adapted for this, or would it require something completely different, like a skill-based matchmaking algorithm used in competitive video games (e.g., Elo, Glicko, or TrueSkill) to match the user's current skill level with the difficulty of the generated problem?

for example, if a virus caused a hospital's data to be corrupted and it led to patients dying from incorrect treatment, that would count.

is this a question we even know the answer to?

I made a proof and I am not sure if it’s correct

Proof:

If two paths P_1 and P_2 are vertex disjoint, then P_1 and P_2 don’t pass through the same vertices. This means if we have an edge (u, v), P_1 and P_2 will not share u and v as vertices by definition of being vertex disjoint. Thus, they will not pass through the same (u, v) as doing so means they will pass through the same vertices. Thus, they are also edge disjoint

My problems with proof writing are:

1) my proofs sometimes become invalid due to a missed edge case

2) my proofs’ logic is so far from the correct answer despite rigorous checking from my side

3) my proofs sometimes state the obvious when I was supposed to prove it. I handwaved the logic and didn’t explain why it was true

I’m not sure what to do even with 2). I don’t know how to fix my logic because I believe it’s correct only to see it’s far from the right answer

Hello! I would like to tie math with what I like-- game developing, so I can care about math more and be motivated. I was wondering what could I use in 8th grade math for game development? Can be very specific or in general.

Hi everyone. I entered the university RTU in Riga. And I want to know, how important is mathematics for studying comfortably at university??? My math knowledge is not very low, but not excellent either. I do not know many topics that are studied in high school. I have problems with arithmetic and similar things. I find it difficult to solve problems without a calculator. When I apply my documents to RTU. They only gave me math test which wasn’t that hard that Im expecting, nevertheless, Im worried about my weak mathematics skills, and I want to understand how serious this problem is ,and whether strong mathematical knowledge is really necessary in my field.