# All Questions

44,812 questions
Filter by
Sorted by
Tagged with
13 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 ...
4 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 ...
10 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 : ...
10 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 ...
18 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 ...
• 121
11 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 ...
12 views

### Why 7/7 [==============================] - 0s 26ms/step is coming in output for my Deep Learning Code? [closed]

I write a Deep Learning (DL) code for my project purpose. I have taken help from many websites and youtube to assemble the code so that it can serve my purpose. However, I find a strange issue while ...
• 168
37 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 ...
• 101
30 views

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?...
• 215
506 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 ...
• 143
1 vote
22 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 ...
58 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. ...
• 123
45 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!
17 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 ...
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 ...
• 4,440
29 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 ...
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.
16 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 ...
13 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/...
• 1
1 vote
38 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$, ...
• 113
26 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 ...
1 vote
25 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 ...
• 111
31 views

...
• 127
1 vote
25 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'|\;\;\...
24 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 ...
15 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|...
• 1
44 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$, ...
• 215
63 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
85 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 ...
• 133
33 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
43 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 ...
20 views

...
• 175
32 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 ...
28 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
13 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.
33 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.
25 views

### RSA public and private key

Alice signs messages using RSA with a public key (e,N) and a private key d. Alice chooses d in the range N power 0.25 < d < N power 0.5 What is the time needed for Alice to calculate the ...
1 vote
34 views

### What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?

First Few Iterations of the Algorithm We have an algorithm in which a squirrel visits the nodes of a directed graph. Our graph has two colors of edges: black and white. Initially, the graph has black ...
30 views

### What is an expression language?

Recently I came across with the package manager Nix. According to wiki: It is also the name of the tool's programming language. As I understand there is a programming language called Nix. But, ...
• 209
25 views

### Confusion about NP vs. LINSPACE

I am working through Sipser, and have come accross the following claim, "any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$", which can be proven by looking at the upper ...
• 215
27 views

### Tiling a simple polygon with hexagons

Let $T$ be a hexagonal tiling of the plane and assume we are given a simple polygon $P$ (we define $P$ as the union of the points on its boundary and its interior). The task is to find the subset of \$...
22 views

### Persona matching algorithm

I have a project to match two groups of people. Under insurance, if the initial sales agent leaves the insurer, their customers will become so-called “orphan customers”. I've given a big data set ...
• 1
75 views
+150

### Prove: Self-organizing list that uses Move-to-Front is 2-Competitive

Preparing for my finals in my "advances algorithms" course. Usually there is a question to prove one of the theorems that was given over the course. I'm currently trying to write a full ...
• 209
39 views

### Any ideas for Parallel Computing Project?

I have to make an application as my Parallel Computing university course project. The application should make use of parallel processing. Any ideas or examples for these kinds of applications ??
32 views

### Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation

I'm trying to identify an algorithm to solve this computational problem Input: Bipartite graph (V, W, E), with E ⊆ V×W A fixed ...
• 53
1 vote
21 views

### Are there systems in computer science where we have several logic systems working all at once and without isolation?

Are there systems in computer science where we have several logic systems working all at once and without isolation? I am thinking there are system where subsystem A uses Paraconsistent logic, ...
• 111
7 views

### Reference/notes for introduction to (von Neumann) architecture

I am interested in understanding what we mean by a von Neumann architecture and need something at a very introductory level. Does anyone know of any good and readable references or notes that will ...
• 101
22 views

### Black Box Optimization

I want to find the maximum possible value of an unknown function on a rectangle. What is the optimal method of doing this? Do I need to use simulated annealing?