All Questions

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 ...

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 ...

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 ...

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 ...

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?

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?

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 ...

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 ...

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 ...

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 ...

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 \} $$ ...

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

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

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 ...

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 ...

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 ...

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 ...

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

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 ...

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 ...

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 ...

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 ...

Consider two problems as defined here. Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases: The number of satisfying assignments for $f(...

Consider a string 'ABBAA' Possible substrings with even number of characters are $4$ 'ABBA' : Count of 'A' is even and 'B' is even 'AA' : Count of 'A' is even and 'B' is even - ($0$) Similarly 'BB' ...

Recently I encountered an interesting problem while studying discrete mathematics: Give the pseudo code to judge whether a poset $(S,\preceq)$ is a lattice, and analyze the time complexity of the ...

I am currently trying to send Get requests to a website, and it takes longer to find the IP address than to just use the hostname. I've been told this is better but why?

I am a little stuck at attempting to give an NFA for the regular expression $0^+(10^+0)^∗$ , where the alphabet is ${0, 1}$. I have tried to construct multiple NFA's state diagram and the closest I ...

While there's an algorithm for solving the stable roommates problem, I understand that the three-people-per-room version of that problem, sometimes called the "threesome roommates problem", ...

I'm trying to prove that in-order tree traversal prints the keys in sorted order. it's shown here, but what I want is to prove correctness using ordinary induction. Claim: For any n-node subtree, ...

I have a directed graph which has edges between every vertices $i$ and $j$ such that $i < j$ and the edge is from i->j and every vertex needs to be visited. I need to divide the graph into two ...

I cant find the grammar to prove it is context free but. I also tried a PDA but couldnt make it. Can someone suggest a grammar for this?

i need help for a specific problem i have at work. You have N number of rows in an array, each with some distribution of Numbers that range from 0 to N.Given an array of size 1000: Row 1 might look ...

I took an exam today and it had a question on A* tree search version, we only briefly skimmed over this on the material, focusing more on the graph search version. In the example in the question text ...

What is a regular expression for the language $C=\{wtw^r \mid w, t \in \{0 \cup 1\}^+\}$? Here $w^r$ is the reverse of $w$.

I need to binarily encode/decode small integers (around 10 bits), in such a way that the hamming distance of the encoded number grows monotonically with the (absolute value) arithmetic distance of the ...

#include <stdio.h> #include <stdlib.h> #include <string.h> #define SIZE 5 struct Grocery { char itemName [20]; int qty; float unitPrice; float totalPrice; }; struct Grocery shop; int ...

Assume we have a language L={111}. Prove no DFA with four states can accept L. Can’t a DFA with 4 states accept L?

My teacher recently assign my class a assignment for us to calculate the mean, median and mode. I would need to write a 100 numbers between 1 to 100 to a file call "data.txt" in 10 rows of ...

There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others. P=NP BPP=NP in simple words means "any cipher can be deciphered by a ...

For the stack implementation of the infix expression (A+B+C), where A, B, C are addresses, which one of the following postfix expressions is superior/better? ABC++ PUSH A PUSH B PUSH C ADD ADD POP ...

So, I have some data to a time capsule project of mine. But the thing is, I need to know the best media on long-time scale to use as storage unity. The time range is 120 years. Now, I've been thinking ...

I'm studying a configuration model of building $d$-regular graphs and reading the following article. And I'm stuck on the following step each simple labelled $d$-regular graph on n vertices has the ...

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 ...

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 ...

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. ...

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 ...

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 ...

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 <...

I am trying to implement knight tour using Warnsdroff algorithm and this is what I have tried to implement. ...

If I start with 4 threads when I run my code and increase thread number each time I run it, my run time decreases as you would expect. However, my run time for 1 thread is significantly smaller than ...