# All Questions

29,681 questions
34 views

### Rooted Tree Isomorphism Algorithm

I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture: Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$. ...
49 views

### Are there decision problems outside of NP?

Consider any problem in NP-hard, then it has a polynomial reduction from a problem in NP in polynomial time. Though, it isn't clear by this definition whether there are decision problems in NP-hard ...
32 views

### Prove that $I(A;B|C)=0$ given $I(A;B)=0$

Let $A$, $B$ and $C$ be 3 discrete random variables. If $A$ and $B$ are independent ($I(A;B) = 0$, where $I$ represents the mutual information), how can we prove that $I(A;B|C)=0$? When I draw a Venn ...
25 views

### What do we mean by “spectral domain” in the context of graphs?

What do we mean by the spectral domain in the context of graphs? For example, I have heard that graph convolutions are easiest to define in the spectral domain. When it comes to the word "spectral", I ...
17 views

### Understanding repeatable read isolation level

Wikipedia defines following terms: With a lock-based concurrency control DBMS implementation, serializability isolation level requires read and write locks (acquired on selected data) to be ...
34 views

### Program that can understand/use its own semantics?

Every program has syntax and semantics. But are there programs, which use its own semantics (knowledge and understanding) about its own semantics (not only in the technical sense but in more general ...
74 views

### A special case of the SUBSET SUM problem

Consider the following special case of SUBSET SUM Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary. Encoding: These inputs (...
50 views

### amortized analysis of max heap

Q) Consider an ordinary binary max-heap data structure with n elements that supports insert and extract-max in $O(log(n))$ worst-case time. Give a potential function $\Phi$ such that the amortized ...
33 views

### Edit Distance Algorithm (variant of longest common sub-sequence)

I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming. The problem is defined as ...
28 views

### Min-cut in a network with zero flow from source to sink

The max-flow min-cut theorem guarantees that the min-cut of a directed network equals the maximum flow. And we can compute $S$ and $T$, are disjoint subsets containing source node and sink node ...
44 views

### Find the CFG of $\{a^ib^jc^k \mid i,j,k>=0 , \text{if} \quad j=1 \quad \text{then} \quad i=k\}$

I've tried but I can't figure out any solution. Is there any hint for me to solve the question?
51 views

### Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
83 views

### Deriving lower and upper bounds for T(n) = T(n-1) + T(n-2) + 10

The solution is to find the upper and lower bounds from: 2T(n-2) < T(n) < 2T(n-1) + 10 So I have to find ...
19 views

### A file is sent from host A to client B, the packet passes through router R on its way to B. Calculate the total delay for the file to reach B

This is a question from an old exam that ive been trying to work out: The 40000 bit file is split into 10 packets with a 400 bit header added to each packet The link from A to R is 500 km long and ...
24 views

### Implementing depth-3 circuit for XOR

In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR. I tried for a little bit to figure out how to do this, but couldn't find ...
26 views

### Unifying Accept States in NFA

I recently read the first question and answer in this homework solution https://cseweb.ucsd.edu/classes/sp08/cse105/hw2s.pdf However, I am not sure if for example, you have two accepting states ...
22 views

### Set of DAG vertices disconnecting a vertex from forbidden vertices

Let $v$ be a vertex with in-degree 0 in an (acyclic) DAG $G$, and let $F$ be a subset of $G$'s vertices (the "forbidden") vertices. Now suppose $U$ is a set of vertices such that every path from $v$ ...
19 views

### Is there any specific model/theory that proposes that the universe is an oracle machine? [closed]

Is there any specific (and well known/famous) model/theory that proposes that the universe is an oracle machine? Physicist Roger Penrose said his book "The Shadows of the Mind" It would be just as ...
882 views

### Algorithm to convert a fixed-length string to the smallest possible collision-free representation?

I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which ...
24 views

### Analyzing the encoding of a DFA by a deterministic Turing machine [duplicate]

Define $L=\{\langle D,R \rangle \mid D$ is a DFA, $R$ is a regular expression, $L(D)=L(R) \}$ Is $L$ decidable? Is $L$ decidable in polynomial time ($L \in P$)? I am trying to ask: can a TM analyze ...
37 views

### CRC computation speed vs polynomials features

I tried to find information about how features of a CRC polynomials influence computation speed of implementations. It is obvious that (depending from the CPU architecture the algorithm runs on) ...
21 views

### Given a subset of numbers $1, \dots, n$, find the minimal subset of numbers $1, \dots, n$ sums of every subset of which cover all sums of first subset

Given a subset $A = \{a_1, a_2, \dots, a_k\}$ of numbers $\{1, 2, \dots, n\}$, find another subset $B = \{b_1, b_2, \dots, b_t\}$ of numbers $\{1, 2, \dots, n\}$ of minimal size (that is, minimise $t$)...
24 views

### Object-oriented small-step semantics NOT based on rewriting techniques

I am looking for a formalized (imperative and possibly statement based) small-step semantics of a subset of an object oriented programming language that it is not based on rewriting techniques. (e.g., ...
21 views

### Amortized time complexity for double stack emulated queue

Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many ...
16 views

### In an FSA, can you have more than one transition for the same symbol from a single state?

My textbook asks: Consider the sets of strings on $\{0,1\}$ where the 4th symbol from the right end is different from the leftmost symbol. Construct an accepting FSA. The answer it provides ...
35 views

### How does computer work? [duplicate]

I am not a computer scientist or even a student of CS. I just want to find more information and would like if someone could put if in right direction about how actually computer works. I understand ...
32 views

### Find m smallest elements in an array of size n where m = n/2

So we have an unsorted array, we need to find the first $m$ elements in ascending order (or $m$ smallest elements) where $m = \mathrm{array.size}/2$ (or $n/2$). How would we do this in linear $O(n)$ ...
17 views

### Master Theorem Help - How to make the value of “b” greater than 1 as required by the Master Theorem? What math is involved?

I know how to identify the parts of the Master Theorem, and I know that it is a recurrence relation. I don't understand how to make the "b" value greater than 1. Please see the image. I know the math ...
26 views

### How to achieve Dijkstra's O(X+Y) in time complexity if edge weights always is 1 or 2?

If we were to have a connected directed graph that has X edges and Y vertices and all the edge weights are either 1 or 2. Would it be possible to somehow achieve a time complexity of O(X+Y) using ...
15 views

### Cluster with categorical / ordinal

i have a dataset with movies review. I wish cluster my element but inside i have a categorical / ordinal values. i seen that exist: MCA (Multiple Correspondence Analysis) https://www.utdallas.edu/~...
6 views

### Motivation behind the definition of order-$k$ (edge) expansion?

I'm trying to understand the motivation behind the idea of order-$k$ (edge) expansion for partitions of a graph, defined below: For simplicity, let's focus on $d$-regular graphs. The definitions I'm ...
30 views

Here I have the method for pumping lemma to prove that a language $L$ is not regular: Suppose to the contrary that L is regula, then $\exists$ DFA $A$, s.t. $L(A) = L$. Let $n$ be the number of ...
39 views

### Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences

Knuth has a neat algorithm that uses matrix exponentiation to compute the $n$th Fibonacci number in $O(\log_2 n)$-time 1. However, there doesn't seem to be a lot of resources on generalizing his idea ...
55 views

### Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma

I was wondering whether it is possible to prove $\{a^p \mid p \in \text{Prime} \}$ is a non-regular language without using the pumping lemma. I'm having trouble choosing an alphabet that completes the ...
31 views

### Generalization of Subgraph Isomorphism

I am wondering how to prove that Subgraph Isomorphism is NP Complete. Wikipedia indicates that the CLIQUE problem can be used to demonstrate this, but I can't figure out how. I also found this link ...
28 views

### Algorithm suggestion for ticket routing system using Machine Learning

Background info I'm a beginner in ML, let me start there. I'm trying to implement an intelligent system that can route a ticket (in a ticketing system), to the appropriate place based on a few ...
34 views

### Hoare logic, proving conjunction rule from basic rules, possible or not?

(This is HW.) Suppose I have these following proof rules given. I am currently considering if I can prove the conjunction rule (given below) from the above given Hoare logic rules. My answer would ...
30 views

### Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbors algorithm from ...
64 views

### How to show context free grammar is undecidable?

Consider the following problem: given two context-free grammars G and H, say whether H is an unambiguous grammar equivalent to G. Show that this problem is undecidable. You may use either or both ...
58 views

### How to best maintain a sorted list from a stream of integers?

If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the ...
37 views

### How to judge the searching precision of Particle Swarm Optimization?

As the title mentioned, how can I judge the searching precision of PSO? Is this depending on the velocity of the particles? I would like to give an example to clarify my question: For a 2-D searching, ...
87 views

### Are there lambda-calculus functions which always output booleans, but are not constant functions?

In labmda calculus, true = $\lambda x,y.x$ and false = $\lambda x,y.y$. Is there a term $f$ such that for any other term $x$, $f x$ normalizes to true or false BUT $f$ does not have the same output ...
26 views

Let us call a Boolean formula with n variables simple if it is either unsatisiable or has at least 2^n / n^2 satisfying assignments. Give a probabilistic polynomial algorithm to decide the ...
33 views