All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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?
0
votes
0answers
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?
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-2
votes
0answers
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 ...
2
votes
0answers
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 \} $$ ...
-1
votes
0answers
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\}$$
1
vote
1answer
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)?
2
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
1
vote
1answer
14 views

Efficient cardinality of set overlap relation

Assume that we have a set S of sets s. Every pair (s,s') in ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
-3
votes
0answers
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 ...
0
votes
2answers
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 ...
1
vote
0answers
22 views

Reduction between Parity-SAT and approximate counting

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(...
2
votes
1answer
47 views

Number of substrings possible with even characters

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' ...
2
votes
0answers
49 views

How to quickly determine whether a poset is a lattice?

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 ...
-1
votes
0answers
27 views

Why should you use IP addresses instead of hostnames when using Sockets?

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?
1
vote
0answers
17 views

Constructing an NFA that is equivalent to a regular expression

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 ...
0
votes
0answers
24 views

Is there an approximation algorithm for the three-person stable roommates problem?

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", ...
0
votes
1answer
17 views

prove correctness of in-order tree traversal subroutine

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, ...
0
votes
1answer
66 views

Dynamic programming for graph splitting

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 ...
0
votes
0answers
15 views

L= ${ a^mb^nc^pd^q: m+n<>p+q }$ context free? [duplicate]

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?
0
votes
0answers
48 views

Need help with a very specific Greedy Algorithm. Are there fast solutions?

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 ...
0
votes
0answers
29 views

A* search tree version - Can a node be in the frontier multiple times

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 ...
-1
votes
1answer
25 views

Regular expression for the language $\{wtw^r \mid w, t \in\{0 \cup 1\}^+\}$

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$.
3
votes
4answers
57 views

Is there a binary representation where the encoding distance grows with the arithmetic distance?

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 ...
-5
votes
0answers
29 views

What is the problem with this code

#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 ...
0
votes
1answer
42 views

Prove no DFA with four states can accept L={111}

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?
-4
votes
0answers
24 views

Can someone help me with my turing assigment

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 ...
1
vote
1answer
29 views

What is the “formula” for “any chipher can be deciphered by a quantum computer”?

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 ...
-1
votes
0answers
21 views

Which one of the following stack implementations is superior, ABC++ or AB+C+?

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 ...
3
votes
1answer
33 views

A doubt on best media for a time capsule

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 ...
1
vote
1answer
16 views

Probability of arising of simple graph in configuration model

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 ...
-1
votes
0answers
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 ...
0
votes
1answer
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 ...
-5
votes
0answers
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. ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 <...
-1
votes
0answers
17 views

Knight tracking

I am trying to implement knight tour using Warnsdroff algorithm and this is what I have tried to implement. ...
0
votes
0answers
18 views

matrix product openMP code in C runs slower in parallel than series

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

15 30 50 per page
1
2 3 4 5
790