All Questions

1
vote
1answer
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$. ...
1
vote
1answer
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-1
votes
0answers
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 ...
3
votes
0answers
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 (...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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?
3
votes
1answer
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? (...
1
vote
4answers
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 ...
0
votes
0answers
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 ...
2
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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$ ...
1
vote
0answers
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 ...
2
votes
3answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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) ...
1
vote
0answers
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$)...
0
votes
0answers
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., ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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)$ ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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/~...
2
votes
0answers
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 ...
2
votes
1answer
30 views

Confused about pumping lemma

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 ...
2
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
1answer
30 views

Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbors algorithm from ...
-1
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
1answer
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, ...
5
votes
2answers
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 ...
-2
votes
0answers
26 views

Please help me with exercise 6.3.3 of László Lovász Computational Complexity lecture notes

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

Must a function in lambda-calculus which inputs a boolean function be defined in a certian way?

This question is my best attempt to get at a more general question about what one can get from terms in the lambda calculus. Using the church encoding, we define booleans by $\texttt{true} = \lambda ...
-1
votes
0answers
23 views

forward checking is useless?

From the book russel & norvig One of the simplest forms of inference is called forward checking. Whenever a variable X is assigned, the forward-checking process establishes arc consistency for ...
0
votes
1answer
38 views

Is there any model of Game of Life compatible with hypercomputation?

I found a question in Mathematics Stack Exchange which asks a very similar question (https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-...
0
votes
1answer
24 views

Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2

Given (n) , what is the Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2. Is there any way I can re-write this code just without using nested loop? ...
2
votes
2answers
62 views

Given all pairs shortest paths matrix, find graph with minimum total sum of edges

I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some ...
1
vote
1answer
19 views

Can a schedule be conflict serializable but not serializable?

A schedule is called conflict serializable if it can be transformed into a serial schedule by swapping non-conflicting operations. Then, My question is: Can a schedule be conflict serializable but ...
0
votes
2answers
55 views

Regular grammar with at most one c

I am attempting to make a regular grammar over alphabet {a, b, c} where there is at most one c. So far, I have the regular expression ((a|b)*|c)(a|b)* but am unsure ...

15 30 50 per page