# All Questions

39,483 questions
Filter by
Sorted by
Tagged with
2 views

### Length of PCP Proofs

Suppose a language $L$ has a non-adaptive PCP verifier which uses at most $r(n)$ random coins, and queries at most $q(n)$ locations of the proof, on inputs of length $n$. How can we show that there is ...
3 views

### What is the best way to compare two images for similarity if the brightness of the second image was changed?

I calculate similarity percent between two images. Another image is the same with changed brightness. I've already tried comparing by pixel (euclidean distance for grayscale and 0/1 values), comparing ...
14 views

### Is it true that machine learning is pretty much math than actual programming?

I have recently started reading books about AI and machine learning and this is what I think of it so far: A lot of people have the assumption that AI is just a bunch if ...
16 views

### Time and space complexity of the method?

Could someone please clarify the time and space complexity of this problem? Or if this code is not the most efficient, what would be a way to improve it? Someone did mention the following: Time: Using ...
13 views

### How could i create a multi-threading system in a kernel?

Im trying to figure out if there's an assembler instructions or a bios intruction to get multi-threading in a kernel. In the case that doesn't exist that, how could i set muti-threading in a kernel?
10 views

### How do I compute the power consumption of a DRAM refresh?

Given a DRAM-based memory system with a total capacity of $x$ bytes, $y$ DRAM rows and a refresh time of $t$ milliseconds, how do I compute the power consumption for one DRAM refresh?
19 views

### Assigning keys to the nodes of a Binary search tree given its shape

Let's say I have a Binary search tree with $n$ nodes and know its shape. I also knows each node has a unique key that is an integer between $1$ and $n$ (inclusive). This would make the assignment of ...
18 views

### Is there a standard way to do Debrujin indices for an uncurried language?

With Debrujin indices, variable names are replaced with numbers that indicate which function binds them. This works fine if each function only binds one variable, but what if one's language is not ...
15 views

### Asymptotic bounds of the following operations

I have a very simple question about the best possible big-O bounds for the following data structure: It starts out empty When you add an element, it is inserted, and the index it was at is associated ...
12 views

### Batch scripting

I was trying to make a batch script to remove "" from inputed string and provide the string without "" as output and also give the length of that string. This also works fine when ...
19 views

### Regular languages closed under prefix operation

Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular? $$\mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \}$$ ...
14 views

### PDA for $\{x\#y : x, y∈\{0,1\}^∗∧|x|=|y|>0\}$

How can I construct a pushdown automaton for the following language? $$\{x\#y : x, y∈\{0,1\}^∗∧|x|=|y|>0\}$$
14 views

### Turing machine - definition of program - naive question

In the paradigm of Turing machines what is considered a program? Can't find a definition anywhere. Is it a member of L(M)?
63 views

### Maximum sum after splitting into subarrays taking difference of maximum and minimum of each one

I was asked this in a hiring challenge that I gave today on HackerEarth: Question/Problem statement: Given an array, split them into several subarrays(possibly zero) such that you obtain maximum sum ...
10 views

### What is the meet of two polymorphic function types in “Local Type Inference”

How does one take the meet of two polymorphic function types? The issue I'm finding is that the two function types can have a different number of type variables. Or the same number of variables, but ...
9 views

### Problem on probability given frame sizes and their error correction probabilities in a wireless system

I am stuck trying to solve the following question for a while Bit error rate after demodulation in an wireless system = 1.0e-03. The system has 4 possible frame sizes – 48 bytes, 96 bytes, 72 bytes ...
23 views

### Will artificial neural networks running on gpus be able to achieve artificial general intelligence?

There is no doubt that neural networks underlie the recent boom in AI.A large number of companies and research groups are betting on neural networks to take them to the holy grail of AGI. John Carmack ...
14 views

### Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
33 views

### Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?

In my analysis of algorithms class we were given the following recurrence relation: \begin{eqnarray} T(n) &=& \begin{cases} T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
16 views

### How to analysis the complexity of this LIS program?

I found a pseudocode online and I don't know why the complexity of it is $O(2^N)$, according to the site. Given a fixed curr, the for-loop in ...
21 views

### Theory of Computation

While converting each of the final states of F to non-final states of F to final states =, FA thus obtained will reject every string belonging to Land will accept every string, defined over sigma, not ...
267 views

### Is it possible to wear-level a FAT32 file system?

Because SD cards use flash memory, they should requires wear leveling to avoid significantly shortening the life of the card. At the same time, my understanding is that they usually use a FAT32 file ...
22 views

38 views

### How do HTML parsers work? [closed]

I am coding a web scraper from scratch. This means no BeautifulSoup or Python HTML parser. From the moment you receive the GET requested information from a web page, I want to know how it becomes an ...
20 views

### Batch size of CNN for training

I'm doing CNN with UNet. When training UNet with batch-size of 128, validation_accuracy did not increase, it looks converged around 50 %. But, once I decreased it to 64, training looks fine. What is ...
30 views

### Code trace question in python [closed]

Question= Complete a code trace on the following function call by transcribing the function and noting the values of the important variables at the indicated points in the function. ...
13 views

### What is the meaning of phenotype could be represented by a number of different genotype

I found this sentence in multiple sources but I didnt understand in one thesis With a neutral representation each phenotype could be represented by a number of different genotype and in another ...
15 views

### Is there a concept of probabilistic quantum computers?

Answering my question https://cstheory.stackexchange.com/q/48527/61557 Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above ...
12 views

### Does the reduction of places and transitions in Petri nets bring any benefits for model checking?

I have a process model P and I have transformed it with some rules to Petri net p1 and with some different rules to Petri net <...