All Questions

Filter by
Sorted by
Tagged with
2 votes
1 answer
34 views

What role does an asterisk serve in Backus–Naur Normal Form?

Suppose that you were reading some production rules for a context-free grammar in Backus–Naur Normal Form What does the asterisk (*) mean? In the example below, ...
user avatar
0 votes
1 answer
16 views

How can we escape the pipe character in Backus–Naur Normal Form?

Suppose that you were writing down the syntax rules for something like C++ as a context-free grammar in Backus–Naur Normal Form How can you distinguish between the pipe character as symbol in C++ or ...
user avatar
0 votes
0 answers
17 views

What is an example of some production rules which would allow parentheses, curly braces, and square-brackets to be interchangeable?

In computer programming, there are many different ways to write a for-loop. Some examples are shown below: ...
user avatar
0 votes
0 answers
14 views

How to do signed 16-bit arithmetic on an 8-bit processor?

For example, to add two 16-bit numbers on my 8 bit machine, I add the low bytes together, then the high bytes together, and then add the carry flag to the high byte of the output. This strategy falls ...
user avatar
0 votes
0 answers
51 views

Find a range of values to subset the rows to maximize the objective function

I have searched around for some time but couldn't find a similar example to my problem. It looks common enough that I would expect it to be solved. It lies between search and optimization/regression. ...
user avatar
0 votes
0 answers
44 views

How to go about solving this induction?

The terms Lm and L′m for each natural number m are defined as follows. (Note that n and c are variables whereas m stands for a number or its Church encoding.) ...
user avatar
0 votes
1 answer
20 views

How to find a crticial edge in a flow network?

The complete question is as follows: An edge of a flow network is called critical if decreasing the capacity of this edge results in a decrease in the maximum flow. Give an efficient algorithm that ...
user avatar
  • 101
2 votes
0 answers
25 views

Create a Turing machine for this interactive game

Given two players $A, B$ and some natural number $n \ge 2$, let $\#(A,B,n)$ denote the following algorithm: $A$ thinks of some number $a \in \{1,\ldots,n\}$ Until the game ends: $B$ thinks of some ...
user avatar
3 votes
2 answers
76 views

Rank in a Convex Combination

Given vectors $A, B \in \mathbb{R}^{n}$, $w \in [0,1]$ and $x \in \mathbb{R}$, let $$ Rank(A,B,w,x)=\sum_{i=1}^{n} \boldsymbol 1 \{w A_{i} +(1-w) B_{i} < x\} $$ denote the number of elements in the ...
user avatar
0 votes
0 answers
44 views

What are optimizations that can be made after the type checker has completed?

So I am implementing a statically typed version of solidity. I have a type checker built. I am working on User defined aliases currently. ...
user avatar
0 votes
0 answers
76 views

What are Funges?

I am currently reading up about esoteric programming languages and came across a COS theory question stated as follows: Esoteric programming languages can be categorised in a variety of different ...
user avatar
  • 1
0 votes
1 answer
47 views

Complexity of solving two different LP problems

I have one LP problem (LP1) to solve, where a term in a constraint is to be substituted after solving another LP problem (LP2) (with a different variable vector). Suppose I call the dimension of the ...
user avatar
0 votes
1 answer
71 views

compute cache miss rate by given code

I have been trying to solve questions like this before but I have stumbled in difficulty to track the the space of the cache. so there is an example of a question like this: Given the code: ...
user avatar
1 vote
1 answer
30 views

Is there a hypothesized "complete" class of problems between P and NP-hard?

For now, assume that P != NP. Is there a "complete" class of problems between P and NP-hard, and if so, what is it called? The two key words here are between complete By between, I mean ...
user avatar
  • 453
0 votes
1 answer
39 views

Is this PDA correct or an erratum? (Sipser example 2.14)

I don’t understand this state diagram. What if $n=0$? Then our input string is the empty string. We begin at $q_1$, push \$ onto the string, move to $q_2$ but then fail. So the language recognized by ...
user avatar
0 votes
0 answers
24 views

Why does it have that amount of stalls

I'm doing an exercise about the MIPS pipeline with the following characteristics: -Branches and Branch targets are calculated in the E-stage. -There is forward logic from the output to the input of ...
user avatar
  • 1
2 votes
1 answer
19 views

Strategy for searching for elementary cellular automata (cyclic boundary conditions) that repeat

I am looking for elementary cellular automata rules and initial conditions that give rise to interesting cycles (Cyclic boundary conditions, such that the leftmost entry is the neighbour of the ...
user avatar
0 votes
0 answers
18 views

Help regarding evaluating the expression? [closed]

int main(int argc, char const *argv[]) { int a = 1; int b = (++a) + (a++); cout << b; return 0; } My approach : ...
user avatar
0 votes
0 answers
14 views

Understanding heuristic function (Berkeley AI Project 1)

Cheers, I am playing around with Berkeley's AI Project 1 (Pacman) (link here) and I am trying to find a good heuristic function for the foodHeuristic function (Question 6). While playing around with ...
user avatar
4 votes
1 answer
89 views

Formal grammar of MIU system

The MIU system, famous from Douglas Hofstadter, is a semi-thue system with the following rules: Xi → Xiu mX → mXX XiiiY → XuY XuuY → XY and a start axiom "mi" I have tried to find a formal ...
user avatar
  • 143
0 votes
0 answers
14 views

Viterbi algorithm for object tracking

I want to solve a problem of object tracking along time. The problem is - I have a sequence of images, and I need to find and track the creation of the objects, than their movement, and than their ...
user avatar
  • 1
0 votes
0 answers
46 views

What are the methods to prove the correctness of an algorithm?

I want to know the major methods to prove the correctness of a program/algorithm. Recommendations on books are appreciated too. This is a general question. TIA. Edit: I'm not looking to detailed ...
user avatar
  • 101
1 vote
1 answer
43 views

Turing machine read time

Suppose I have a Turing machine that takes as input any string of length $n$, where $n$ is odd, and the Turing machine returns the middle character of the string. What time complexity class is this in?...
user avatar
8 votes
3 answers
1k views

Efficient sampling from all positive integers

Let's say we want to find the smallest positive integer x for which some property A holds. We know that such an integer exists. However, we have no knowledge about the scale of x (i.e. x could be 7 or ...
user avatar
  • 183
1 vote
1 answer
25 views

shortest path increases monotonically => a bound on the length of one iteration of Edmons-Karp is then O(E) ... Convince me this is true

I was reading the proof of time-complexity for the Edmonds-Karp algorithm here (https://brilliant.org/wiki/edmonds-karp-algorithm/). Everything in the first part of the proof (The section ...
user avatar
2 votes
3 answers
69 views

Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical

My algorithm homework revolves around matching 4 "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical. ...
user avatar
  • 123
3 votes
1 answer
54 views

Given two strings ABC and CBA, find A, B and C

Given two strings ABC and CBA, find A, B and C. Input: abcacab, cabcaab Output: ab, ca, cab The time complexity of brute force is O(n^3). Are there any better algorithms to solve this problem? Thanks!
user avatar
0 votes
1 answer
20 views

Algorithms for finding closest graph node within set of nodes

Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$? Furthermore, say we are doing many ...
user avatar
0 votes
0 answers
13 views

Comparing two poses of a point cloud

I have an unstructured point cloud for which I determine pose information described as a similarity transform (rotation matrix and translation vector). In my setting, several independent poses are ...
user avatar
  • 4,601
-1 votes
1 answer
31 views

questions on set? [closed]

I am not able to understand this code, if we are using find() method and passing the value 'e' that means we are searching whether the element 'e' is present or not? After checking we can directly ...
user avatar
-1 votes
0 answers
7 views

How do I show undecidability of this language using ALLCFG?

I used ALLCFG to show undecidability of EQCFG previously which was straightforward but the "or" condition in TRIVIALCFG is throwing me off. I don’t know a way to reduce TRIVIALCFG to ALLCFG.
user avatar
0 votes
1 answer
28 views

Does a random phenomenon have a pre defined probability distribution? what does it mean for something to be random?

While studying Shannon's notion of perfect secrecy I came upon the idea that a bit is perfectly random if it happens to be 0 or 1 with an equal probability. What does this mean? Also, what can we say ...
user avatar
0 votes
0 answers
14 views

What is the best SAIS algorithm implementation/variation as of now?

During the past few weeks, I have been learning about the SAIS algorithm and the different variations/implementations. Here is the most recent paper I have read: https://synergy.cs.vt.edu/pubs/papers/...
user avatar
  • 1
1 vote
1 answer
46 views

Data structure and optimal algorithm for modeling reachable outputs given a set of inputs

Given the following: A set of input types $I$ = {a, b, d, ...} A set of functions $F$ (With associated costs, and possibly identical signatures) = {($c_1$, a -> d), ($c_2$, (a,b) -> e), ($c_3$, ...
user avatar
  • 113
-2 votes
1 answer
29 views

Inversion array of a given array

Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i ...
user avatar
1 vote
1 answer
35 views

Is the executable always loaded to the same place in the text segment?

I am reading a book about data architecture, and I am wondering about the text segment and the memory adresses. In one example(assembly using ARM) where the code was compiled there were adresses to ...
user avatar
1 vote
0 answers
27 views

Getting something wrong while building parse table for the grammar

Task Build the Parse Table Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} E &\to TE' \\ E' &\to +TE'\; |\; \epsilon \\ T &\to F T' \; \\ T' &\to *FT'|\;\;\...
user avatar
0 votes
0 answers
26 views

What is this standard of text display called?

I hope this is an appropriate site for this question. In the RINEX documentation http://acc.igs.org/misc/rinex304.pdf (RINEX is a file exchange format for GPS data), it gives an example of a RINEX ...
user avatar
0 votes
0 answers
16 views

Is this Pumping Lemma proof correct? L = {{ca^ndb^m | n >= m >= 1}

Let L be = {ca^ndb^m | n >= m >= 1} Let x be the word = ca^nd^m with |x|= 2n>=n. Look at x = uvw with |V|>=1 and |UV|<=n. We have u= ca^kdb^k, v= b^l, w=b^m-k-l with |v| >= 1 and |uv|...
user avatar
  • 1
2 votes
1 answer
48 views

Are there any problems which are known to be both NP-complete and EXPTIME-complete?

Are there any problems which are known to be both NP-complete and EXPTIME-compelte? My guess is no, because we know that $P$ is not equal to $EXPTIME$ and EXPTIME-complete problems are not in $P$, ...
user avatar
-3 votes
2 answers
66 views

Is frontend slang term is it used in teaching in univ

I have a question : is the term front-end in this context phpmyadmin is frontend for mysql slang is it taught in academy in this context I don't want to use slang term
user avatar
3 votes
3 answers
94 views

Are there absolute reasons to prefer row/column-major memory ordering?

I've heard it said that "fortran uses column-major ordering because it's faster" but I'm not sure that's true. Certainly, matching column-major data to a column-major implementation will ...
user avatar
  • 143
0 votes
0 answers
38 views

Longest shortest path between two classes of nodes

(larger context at the end) My view of the problem I have an undirected graph whose nodes can be categorized into three classes depending on some metadata (I have a function that can tell me the class ...
user avatar
  • 101
-1 votes
2 answers
52 views

How to prove feasibility?

Let's say I have a optimization problem P1, where the constraints are linear but the objective function is not. Let's say I have another optimization problem which is linear in constraints and linear ...
user avatar
  • 101
0 votes
1 answer
22 views

Why is this code for dining philosophers deadlock free?

...
user avatar
2 votes
1 answer
35 views

Must the evaluation strategy for a language be specified in order to apply the Church-Rosser Theorem?

The Church-Rosser Theorem [0] states that the Lambda Calculus (LC) is confluent: between a source expression S and target expression T, the latter in normal form, for any given P, a sequence of ...
user avatar
  • 41
0 votes
0 answers
14 views

Canonicalizing Arbitrary EBNF Expressions

From what I understand, LL and LR parsing require a grammar to be in "canonical form", i.e. only productions of the form A -> b1 b2 ... bn, where ...
user avatar
2 votes
1 answer
35 views

Is there a hierarchy of computational expressivity that is sensitive to evaluation strategies?

Various computational hierarchies describes the relative expressivity of different classes of languages, machines, or other models of computing, with the classic progression for Automata Theory [0] ...
user avatar
  • 41
-1 votes
1 answer
16 views

Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?

I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
user avatar
-2 votes
0 answers
40 views

How to build an 4 bit width AND gate

I was trying to build an AND gate of 4 bit width. It doesn't work and I don't know how to fix it. This is what I did. But the truth table is wrong. How can I fix it? Thanx for the help.
user avatar

15 30 50 per page