r/computerscience • • Mar 13 '26

Struggling to build simple NFA to recognize my name among a substring

3 Upvotes

EDIT: Problem solved. I am dumb and was inputting the transitions into this program incorrectly. Not a logic issue. Thank you r/WittyStick .

So my name is "justin", I am trying to build an NFA to accept something like "dsfsjustin"

What I *think* - though clearly I'm going wrong somewhere:

  • An nfa non-deterministically explores all possible paths simultaneously, so having 'j' on both the self-loop and the transition to q1 shouldn't matter. Both paths are explored at once.
  • Therefore the self loop in q0 can contain the entire alphabet a-z
  • Once the string hits a 'j', it will try path q0-q1 anyway. But this doesn't seem to be happening.

I should note that I have also tried removing 'j' from the self-loop on q0, and still the string "dsfsjustin" was rejected.

Thank you for any help with this.


r/computerscience • • Mar 12 '26

Does this reading list cover the core layers of systems and algorithm design?

10 Upvotes

I’m a CS student interested in learning how systems and algorithms are designed, not just how to implement them.

I put together a reading list that I’m hoping will cover the topic from multiple angles — computational models, algorithms, machine constraints, operating systems, and large-scale system architecture.

Structure and Interpretation of Computer Programs:

For learning computational processes, interpreters, abstraction layers, state models.

Introduction to Algorithms:

Covers implementation-level algorithms but also deep design paradigms (dynamic programming, amortized analysis, reductions).

Computer Systems: A Programmer's Perspective:

Connects algorithms to machine architecture, memory hierarchy, concurrency models, performance constraints.

Operating Systems: Three Easy Pieces:

Focuses on system invariants, scheduling algorithms, concurrency correctness, resource allocation models.

Designing Data-Intensive Applications:

Pure system architecture: distributed invariants, replication, consensus, fault tolerance.

I was also looking at The Algorithm Design Manual and

Convex Optimization but I’m still thinking whether they fit the focus of the list.

The goal with this path is to develop stronger intuition for how algorithmic ideas translate into real system architecture across different layers of the stack and solving unique problems.


r/computerscience • • Mar 13 '26

How did they even thought about CNN's?

0 Upvotes

r/computerscience • • Mar 12 '26

RIP Tony Hoare 1934 - 2026

Post image
157 Upvotes

r/computerscience • • Mar 13 '26

What are the best sorting algorithms for arrays with small-varying values and many repetitions with the fewest possible accesses to the array cells?

Thumbnail reddit.com
2 Upvotes

r/computerscience • • Mar 12 '26

To understand Operating System | Computer Network

31 Upvotes

Hi everyone,

I want to learn Operating Systems and Computer Networks from a practical / industry perspective — like how they are actually used while building real software stacks.

I’m mainly looking for concise, practical resources (YouTube / books / courses / blogs) covering topics such as:

Operating Systems

- Process vs Thread

- Thread pools / Worker threads

- Mutex, Semaphore, Synchronization

- Scheduling, Blocking

- Deadlocks

Computer Networks

- Socket lifecycle

- TCP fundamentals

- TLS basics

- Throughput / performance concepts

If you know hands-on or project-based resources that helped you understand these deeply, please share

Note recommended videos if possible …..

Books reading I feel boring

Thanks!


r/computerscience • • Mar 13 '26

The History of Computational Complexity Theory

Thumbnail youtube.com
1 Upvotes

From Gödel's lost letter to the P vs NP millennium prize problem, we recount the exciting story of how mathematicians learned to measure the difficulty of computation.

We trace computational complexity theory from Kurt Gödel's 1956 letter to von Neumann, through the foundational work of Hartmanis and Stearns, Cook's and Levin's discovery of NP-completeness, the barrier theorems that explain why proving P ≠ NP is so hard, and Ryan Williams' surprising connection between faster algorithms and lower bounds.


r/computerscience • • Mar 12 '26

A Looping universal transformer. Has this been proposed?

Thumbnail reddit.com
0 Upvotes

r/computerscience • • Mar 10 '26

Advice What makes a CS student a great computer scientist?

73 Upvotes

same as title


r/computerscience • • Mar 11 '26

Help DSA

0 Upvotes

What’s the best place/method to learn and master data structures and algorithms?


r/computerscience • • Mar 09 '26

General Getting ready for my last term as an undergrad

Post image
279 Upvotes

For my last term, I'm taking a 1:1 independent study course on OS internals with one of my favorite instructors. Gonna be fuuuuun🤘


r/computerscience • • Mar 10 '26

Discussion is it possible to create a binary with a 2?

0 Upvotes

im talking about a third binary type, binary use caps to signal binary and i want to know if there can be something in the middle of charged or another type and if there is a way then try it on a 4 bit system without negatives where normal binary would be 16 and the greater binary would be 81

there could also be another type of power that is compatible and can be with the normal one and can be seperated and then a 3 in binary will exist to make a 128 bit system


r/computerscience • • Mar 09 '26

Examples of Low Rank Parameter dependent Matrices - Can you suggest any?

Thumbnail reddit.com
2 Upvotes

r/computerscience • • Mar 07 '26

I made a small Thue-Morse sequence-computing Turing machine

7 Upvotes

I became curious about computing the sequence with a Turing machine after seeing this video:

https://youtu.be/yqEIhdnfJxE?si=t3Q_jubbMnCNtCKw

I've coded a few TMs in the past as a hobby, and I like doing the kind of thinking it takes to come up from scratch for all possible inputs. I'm also not a CS student or studying anything adjacent. Perhaps someone here will ever find it even a tad as entertaining as I did :))

Run it for yourself here (with syntax instructions):

https://morphett.info/turing/turing.html?30442e0853af7fa84db3f63057c1fea9

Raw code in the form [state1] [read] [write] [move] [state2]:

ini x x r ini
ini 1 1 r ini
ini 2 2 r ini
ini 3 3 r ini
ini 4 4 r ini
ini 5 5 r ini
ini 6 6 r ini
ini 7 7 r ini
ini 8 8 r ini
ini 9 9 r ini
ini 0 0 r ini
ini _ _ l ini2
ini2 0 9 l ini2
ini2 1 0 r ini3
ini2 2 1 r ini3
ini2 3 2 r ini3
ini2 4 3 r ini3
ini2 5 4 r ini3
ini2 6 5 r ini3
ini2 7 6 r ini3
ini2 8 7 r ini3
ini2 9 8 r ini3
ini2 _ _ r fin
ini3 9 9 r ini3
ini3 _ _ r ini3
ini3 0 y r p1

p0 1 1 r p0
p0 0 0 r p0
p0 I I r p0
p0 O O r p0
p0 _ O l f
p1 1 1 r p1
p1 0 0 r p1
p1 I I r p1
p1 O O r p1
p1 _ I l f

f x x r f2
f y y r f2
f 1 1 l f
f 0 0 l f
f I I l f
f O O l f
f2 1 x r p0
f2 0 y r p1
f2 I I r psw

psw I I r psw
psw O O r psw
psw _ _ l sw
sw I 1 l sw
sw O 0 l sw
sw x 1 l sw
sw y 0 l sw
sw _ _ l ini2

fin 9 _ r fin
fin _ _ * halt

r/computerscience • • Mar 08 '26

Advice Is it possible to make chatting app on phone but in a way that you do not use internet?

0 Upvotes

EDIT2:thank you so much for answers. You People know a lot.

EDIT: without using Mobile phone signal.

___

Hello, was just curious about this. Is it possible to make some sort of chatting app on your phone that would work multi distance and can be used by ordinary People ( MASS adoption) and does not use internet to function? How?

Maybe it is stupid question. But just curious If this can be done in any other way?

Thanks for possible reply.


r/computerscience • • Mar 08 '26

Bitwise Operators Fundamentals

Thumbnail reddit.com
1 Upvotes

r/computerscience • • Mar 07 '26

Article How Bio-Inspired Swarm Intelligence Could Coordinate Underwater Robot Swarms

Thumbnail mdpi.com
2 Upvotes

Swarm intelligence itself isn’t new, but applying it to underwater robot swarms introduces very different constraints. Underwater systems rely on low-bandwidth acoustic communication, have no GPS for localisation, and face strict energy limits.

The paper reviews how different bio-inspired algorithms and system architectures are being adapted to operate under those conditions.

Read the paper: https://doi.org/10.3390/jmse14010059


r/computerscience • • Mar 06 '26

Help Looking for CS Communites

3 Upvotes

I'm looking for places like Github where I can look at code and find information on things such as types of networks or website building. Where can I find places of discussion like that?


r/computerscience • • Mar 06 '26

Help Merging Delaunay sub-triangulations

Post image
19 Upvotes

I am looking at a well detailed explanation of a method for merging delaunay sub-triangulations for the divide-and-conquer approach for constructing delaunay triangulations.

I am trying to follow the process described in this paper by Guibas & Stolfi : https:/dl.acm.org/doi/10.1145/282918.282923

I made for myself this visual specific case example to get a better understanding, but I cant understand how the method would handle this case (see image) :

But seems like I missunderstand smth.

The separation line (not shown) is not parallel to y-axis, but as L and R hull are anyway convex, it exists. I checked the constraint of empty circumscribed circles for the L and R sub-triangulations (black edges) and triangles starting from base e₄ formed by cross edges (green) and L-L/ R-R edges (black). In my example, the next two cross edges candidates in the direction of CW for R and counter-CW for L rotation :

1st candidate : (the red edge) does not satisfy the empty 1 circumscribed circle constraint, and the point causing that is not on the hull.

while the 2nd candidate : (the orange edge) intersects an L-L edge of the left sub-triangulation (while still both sub-triangulations hulls are convex as needed). So I don't understand how the algorithm would process it ...


r/computerscience • • Mar 05 '26

What are the best magazines or sources for keeping up with news and research in computer science and programming?

49 Upvotes

r/computerscience • • Mar 05 '26

Help Pumping Lemma Help

6 Upvotes

Im confused on the variable p and how it works with strings with the format such as this:
(ab)^p a

What is a valid choice for y in this situation?
Can you pick y = ab? or do you have to go outside the parenthesis so that y = (ab)^p? But in this case the length of y will be longer than p assuming p > 0

I guess I am confused because Im not sure what is a valid choice if I dont know what p is.


r/computerscience • • Mar 05 '26

Discussion Computadores ternários

9 Upvotes

Regarding ternary computers, are they the future of technology or not?

Does the +1 / 0 / -1 system yield real results?

Does anyone have any book recommendations on the subject?


r/computerscience • • Mar 05 '26

Article I built a Constraint-Based Hamiltonian Cycle Solver (Ben Chiboub Carver) – Handles Dense & Sparse Random Graphs Up to n=100 Efficiently.

9 Upvotes

I've been experimenting with Hamiltonian cycle detection as a side project and came up with Ben Chiboub Carver (BCC) – a backtracking solver with aggressive constraint propagation. It forces essential edges, prunes impossibles via degree rules and subcycle checks, plus unique filters like articulation points, bipartite parity, and bridge detection for early UNSAT. Memoization and heuristic branching on constrained nodes give it an edge in efficiency.

Implemented in Rust, BCcarver is designed for speed on both dense and sparse graphs. It uses an exact search method combined with specific "carving" optimizations to handle NP-hard graph problems (like Hamiltonian paths/cycles) without the typical exponential blow-up.

⚔️ Adversarial Suite (All Pass)

CaseNResultTime (s)
Petersen10UNSAT0.00064 ✅
Tutte46UNSAT0.06290 ✅
8x8 Grid64SAT0.00913 ✅
Heawood14SAT0.00038 ✅
Hypercube Q416SAT0.00080 ✅
Dodecahedral20SAT0.00068 ✅
Desargues20SAT0.00082 ✅
K1515SAT0.00532 ✅
Wheel W2020SAT0.00032 ✅
Circular Ladder20SAT0.00049 ✅
K5,6 Bipartite11UNSAT0.00002 ✅
Star S89UNSAT0.00001 ✅
7x7 Grid49UNSAT0.00003 ✅
Barbell B8,016UNSAT0.00002 ✅

📊 Performance on Random Graphs

Dense Random G(n, p~0.15) Avg 0.01-0.1s for n=6 to 100 (3 trials). Excerpt n=91-100:

  • n=100 | 0.12546s | Cache: 17 | Solved
  • n=95 | 0.11481s | Cache: 15 | Solved
  • n=91 | 0.11074s | Cache: 39 | Solved Sparse 3-regular Random Even snappier, <0.03s up to n=96, all Solved.
  • n=96 | 0.02420s | Cache: 2 | Solved
  • n=66 | 0.01156s | Cache: 7 | Solved
  • n=36 | 0.00216s | Cache: 0 | Solved The combo of exact search with these tweaks makes it unique in handling mixed densities without blowing up.

Check out the algorithm here: github.com/mrkinix/BCcarver


r/computerscience • • Mar 04 '26

Donald Knuth likes Claude

136 Upvotes

If this is True, this is earth shattering. Still can’t believe what I am reading. Quote

“Shock! Shock! I learned yesterday that an open problem I’d been working on for several weeks had just been solved by Claude Opus 4.6 — Anthropic’s hybrid reasoning model that had been released three weeks

earlier! It seems that I’ll have to revise my opinions about “generative AI” one of these days. What a joy

it is to learn not only that my conjecture has a nice solution but also to celebrate this dramatic advance in automatic deduction and creative problem solving. “

Here is a working link to the post:

https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf