Questions tagged [theory]
Programming-language-agnostic Questions that focus on the theoretical aspects rather than the actual implementations.
1,776
questions
1
vote
1
answer
18
views
Does Cs50 make mistake when it calls an input a problem to solve?
So in week 0 of Cs50 course. They present computer science as problem solving.
Afterwards they show picture of input going into box that represent algorithm and coming out as output.
And they define ...
0
votes
0
answers
20
views
Confused about what exactly is value and what exactly is data?
I cant really connect those two concepts correctly.Because my understanding is weak since im just trying to understand from google and wikipedia and it seems i cant get good understanding that way. I ...
-3
votes
1
answer
27
views
What happens when i declare reference type with no datatype on after sentence's inequality symbol '<>' JAVA [duplicate]
I recently restarted coding and declare reference type like below
Map<Integer,Integer> cnts = new HashMap<>();
cnts.put(1,0); //no error, just for test
cnts.put("2",0); //error, ...
0
votes
0
answers
19
views
Is it a bad practice to write an interactive step on a unit test?
From what I understand the main purpose of unit testing is to automatize testing.
But consider the following example:
I have an application that needs the user to read a QR code. When the user reads ...
2
votes
0
answers
41
views
Why do I need to change floating point numbers to integers?
I have a theoretical question. Why do we need integers in Python if we can always use floating point numbers? For memory saving? I wonder if there are more reasons.
0
votes
1
answer
30
views
NFA for the star of a language (01 U 001 U 010)*
Problem from page 5 of this pdf.
Give an NFA that recognizing the language (01 U 001 U 010)*
I think this is wrong because there should be an additional start state (accepting) going to state 1 for ...
1
vote
2
answers
39
views
Is there a mathematically optimal way to parallelize a given algorithm?
Let us say we have an algorithm with multiple steps and each of those steps can be parallelized. Given a certain number of CPU cores, is there a mathematically optimal way to split things up on the ...
1
vote
1
answer
22
views
Is the empty string a subset or element of all alphabets?
I'm having trouble understanding when the empty string (epsilon) is a subset or element of an alphabet? My understanding was that epsilon was only part of a language, but my TA in the class said it ...
-2
votes
2
answers
60
views
How to duplicate value in functional js?
I have couple of functions, first of which is "expensive" getter:
function getter() {
return {
a: "foo",
b: "bar",
c: "should be intentionally ...
0
votes
0
answers
20
views
Derivation of Total Variation Norm?
I have attached an image of the TV norm. Can anyone show me the proof of derivation I totally confused? I have knowledge of backward difference and partial derivative things. But I was not successful ...
0
votes
1
answer
31
views
Greedy resolution to constructing Huffman codes: question on greedy-choice property proof
I am reading The Introduction of Algorithm by Thomas and Charles, 3rd Edition.
when coming to the greedy algo section for Huffman codes - Correctness - greedy-choice property - Lemma 16.2:
Let C be ...
-1
votes
1
answer
25
views
Windows DLL Loading : Load A 64 Bit Dll Into a 32 bit Process, Is It Possible?
Most people would say that 64bit under 32bit on windows is impossible. However as far as I'm aware Wow64 works by loading a 64bit ntdll, then a 32bit ntdll. Calling the 64bit dll to issue syscalls.
...
-2
votes
1
answer
35
views
return outside if/else statement (Python)
When you have the following code:
def func(a) -> Optional[S]
if len(a) == 2:
x = "bla bla bla"
else:
if a.state is True and len(a) == 3:
s = "...
0
votes
0
answers
21
views
Deep Learning equivalent Machine Learning
The question seems simple, can we find a neural network for every classical Machine Learning model?
For example:
Linear regression is a perceptron.
PCA is an auto-encoder with a single intermediate ...
0
votes
1
answer
22
views
Is there a particular use case for fold() function
When accumulating a collection (just collection, not list) of values into a single value, there are two options.
reduce(). Which takes a List<T>, and a function (T, T) -> T, and applies that ...
0
votes
0
answers
26
views
Can bitwise operators be used to quickly find a value from a permutation?
Let's say that I have two metrics: Age (1-20) and size (SMALL, MEDIUM, LARGE) and I want to find what the relative oldness (Young, Adult, Senior, Very Old) is? (Think "1 year old mouse vs 1 year ...
-1
votes
1
answer
29
views
Are there alternative computing models out there other than Von Neumann and Turing? (+ some other basic questions that puzzle me) [closed]
I am a beginner.
What's so special about Turing and Von Neumann models?
Are they art or science?
Are they akin to the fundamental laws of nature or physics or more like convention?
If other models ...
0
votes
0
answers
22
views
Overfitting with epochs Mean squared error
If i am training my model and attempt to minimise MSE, if over a few epochs the MSE increases,
say
epoch 100, mse = 0.0992
epoch 101, mse = 0.0992
epoch 102, mse = 0.0994
epoch 103, mse = 0.0993
epoch ...
0
votes
0
answers
23
views
theoretical question about search algorithms and data structures
I have a list of N-dimensional features called M. I want to find in that list the matching feature to a query feature F. Comparing my features is not based on popular metrics (L1, L2, etc.): for ...
0
votes
0
answers
39
views
Is there an efficient algorithm to verify that a finite code is uniquely decodeable?
Is there an efficient algorithm to verify that a finite binary code is uniquely decodeable?
Let's say we have an alphabet of symbols A and some encoding of those symbols C. How do we check quickly ...
2
votes
2
answers
137
views
If stack operations are constant time O(1), what is the time complexity of this algorithm?
BinaryConversion:
We are inputting a positive integer n with the output being a binary representation of n on a stack.
What would the time complexity here be? I'm thinking it's O(n) as the while loop ...
1
vote
1
answer
39
views
In Context Free Grammer, do we replace all variable during a substitution? or can we apply substitution rule to only of the variable of same type?
Imagine we have a Context Free Grammer, CFG, as follows:
S -> a ...(1)
S -> SS ...(2)
And i derive a string in the specified language as follows:
S ..start state
SS ..using (2)
aS ......
0
votes
1
answer
71
views
When to use Ø for states in DFA / NFA
I am confused about the usage of "Ø" in the DFA / NFA ( Let's talk about this in the context of DFA to NFA conversion )
Let's say that I have a NFA as follows:
enter image description here
...
0
votes
0
answers
29
views
Lexing "1 -1". How does a lexer decide its 1 - 1 instead of just two numbers next to each other?
I'm new to writing compilers, and I want to know the proper solution to this problem. Currently if there is the possibility of two different tokens I chose the one that is longer - it works, but I ...
4
votes
1
answer
112
views
Are there advantages to asynchronous code on dedicated backend servers with no UI thread?
I had a developer challenge the use of asynchronous server side code the other day. He asked why asynchronous code is superior to synchronous code on a server with no UI thread to block? I gave him ...
0
votes
1
answer
73
views
Transforming grammar for predictive parsing
Is the following grammar suitable for predictive parsing, or is their an algorithm to modify the grammar to make it suitable for predictive parsing?
number = digit digit_or_sep* digit | digit
...
-1
votes
1
answer
45
views
Can keys or hashes trigger an injection attack?
Can hashes or keys generated (either intentionally or accidentally) that would trigger an injection attack? For example, if the hash or key was generated as something like SELECT%0d*%0dFROM%0dWHEREVER,...
0
votes
0
answers
34
views
How does internaly git compose files so quick (just "academic" question)
I have just "academic" question for Git experts.
I could not find anything about how Git actually internaly compose files from all the commits.
I could not imagine that it iterate through ...
0
votes
1
answer
67
views
How to find a sequence of input to drive a system to a certain state?
I encountered a problem and would like to ask what type/class of problem it should fall into in terms of algorithm/computing theory. I’d also like to ask if there’s a smart algorithm to solve it ...
0
votes
0
answers
15
views
set theory composite proof conundrum--not legit because not allowed to make reference to number of elements?
I wrote the following proof to demonstrate the domain of a composition is a subset of the domain of set A, the first set in a composition relation. I hope people can follow this. The instructor and ...
0
votes
0
answers
9
views
Most appropriate data file format for columns with multiple inputs
I am new to data science and I have this data from SO survey: (.xlsx /.csv)
DevType
full-stack
Developer; desktop or enterprise applications;Developer; full-stack
Designer;Developer; back-end
...
2
votes
1
answer
28
views
Why does backprop algorithm store the inputs to the non-linearity of the hidden layers?
I have been reading the Deep Learning book by Ian Goodfellow and it mentions in Section 6.5.7 that
The main memory cost of the algorithm is that we need to store the input to the nonlinearity of the ...
-1
votes
1
answer
84
views
Construct an NFA/DFA/Regular Expression
Hey so im trying to make a NFA/DFA or Regular expression for this language.
l = {Even-length Strings over the alphabet {0,1} of at least length 6 that begin and end with the same symbol.}
This is the ...
3
votes
1
answer
95
views
How to calculate a minimum exchange time among multiple nodes?
This is about developing a distributed consensus.
Let's assume we have N nodes ( N1, N2, ..., Nn ),each of the nodes has a different value( A1, A2, ..., An ).These nodes can communicate with each ...
0
votes
1
answer
63
views
How to find most optimal match between data points given the similarity matrix?
I am stuck on a very simple problem but more I try to solve it the harder it becomes. Or maybe there is no better solution than O(N^2). The problem is simple. I have N data points in first set and M ...
0
votes
0
answers
22
views
Does latency include lost packets?
I was wondering if one want's to measure the latency of a Bluetooth broadcaster application, if the amount of lost packets contribute to the latency?
What of the following options is true?
1.) ...
1
vote
3
answers
35
views
Why some commands cause an error relative to the preceding command?
This is a pandas question.
Try to copy this in Jupyter Notebook:
In [1]: df = pd.DataFrame([[1, 2], [4, 5], [7, 8]],
index=['cobra', 'viper', 'sidewinder'],
columns=['max_speed', '...
0
votes
0
answers
13
views
JAGS model with unknown data points
I'm new at JAGS, and trying to make this model work. My data is an n by m matrix of 1s, 2s, 3s, and empty values where a subject was not presented with the question (currently represented by the ...
0
votes
4
answers
223
views
If both concrete and abstract methods of an abstract parent class can be overridden,what is the difference?
If in a derived class you can override both a concrete method and an abstract method of an abstract parent class,then what's the point of having abstract methods in the first place?
If for example ...
3
votes
3
answers
188
views
An allocation problem of people into groups getting them to meet as little as possible
I have been trying to solve this for quite a while without success.
I have not found (I searched though) theory that could help me on wikipedia.
Here is the problem.
I have a group of n players (more ...
0
votes
0
answers
9
views
find the languages generated by the following grammar S->G/M
find the languages generated by the following grammar: S->G/M,G->0G1/0A,A->0A/,M->0M1/B1,B->B1/epsilon
0
votes
1
answer
80
views
How would you translate a Map to and object for dart
Lets say I want to refactor my code so it's easier to read and I have an object property that is type of Map<String,AnotherObject or dynamic> what is the best way to convert this property to ...
0
votes
1
answer
34
views
Queuing Theory - I am not getting the correct answer to a question related to queuing theory. Please help :)
How come the answer to part (a) of the question (please refer to the link below) is 2.25?
[Question-related to queuing theory taken from the book "Operations Research Second Edition Richard ...
1
vote
1
answer
48
views
Why can't we solve the consensus problem by just enforcing a new leader?
I am going through this lecture series by Martin Kleppman.
In this video at around 1:25, he says you can manually configure the distributed nodes to chose a leader.
If that's the case can't we just ...
0
votes
1
answer
27
views
Would infinitely deep decision tree on a binary classification task guarantee to achieve 100% accuracy?
Would then infinitely deep decision tree on a binary classification task guarantee to achieve 100% accuracy on a training set with N examples such that there is no examples with the same feature ...
1
vote
3
answers
96
views
Trying to understand Amdahl's Law
I am trying to answer a school assignment but i am getting confused to what the question is trying to ask.
A design optimization was applied to a computer system in order to increase the performance ...
0
votes
0
answers
28
views
How to find the number of edges of the complement of a planar graph?
I have just started the topic Planar graphs from Graph Theory and gone through mostly the basics and a few advanced materials.
There is this one question given in my textbook where there is also a ...
0
votes
0
answers
28
views
What is registerCallback in fb authentication and loginManager
I am adding fb login in my App I am Following fb Developer Documentation.i wanna know What does registerCallback Method do(in deep) and why we take permission(setReadPermission) and what is ...
0
votes
0
answers
17
views
Empirical Risk Equal to True Error under condition
I've been working through "Understanding Machine Learning: From Theory to Algorithms", and on pg. 46, after the realizability assumption has been dropped from the defintions of loss/risk, a ...