# All Questions

44,851 questions
Filter by
Sorted by
Tagged with
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, ...
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 ...
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: ...
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 ...
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. ...
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.) ...
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 ...
• 101
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 ...
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 ...
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. ...
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 ...
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 ...
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: ...
1 vote
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 ...
• 453
39 views

• 237
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
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 ...
• 143
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 ...
• 101
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 ...
• 101
22 views

...
• 175
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 ...
• 41
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 ...
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] ...
• 41
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.