All Questions

I am studying the properties of control flow graphs (CFGs) in general. The tool that I use to statically extract CFGs and label them is based on LLVM. Now, I am looking for a large corpus of C/C++ ...

I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the ...

This is a real-world application, not a student assignment. Suppose a list of events of that have startTime and endTime, and ...

Say I have an array of fitnesses like so: let array = [3,2,2,2]; Although the players with a fitness of 2 had a worse score, they are more likely to pass their ...

I am working on a graph partitioning algorithm and i have the following problem i am trying to solve. There is a 32-bit value c computed for each state of the ...

I have been trying to solve this problem. Convert the DFA to a regular expression. I extracted these following equation. $q_1 = q_2a$ $q_2 = q_1a + (a+b)q_3$ $q_3 = q_1b + q_2a $ Also,the ...

In Karatsuba algorithm for multiplying two numbers, we divide each number into two. For example: x= 1234 y= 2456 Then a = 12, b = 34, c = 24 , d = 56 What if ...

given this function, ...

Why is the recurrence formula for insertion sort is T(n-1) + n? I understand the T(n-1) part but the why does the cost for ...

I have some basic questions about complexity theory that came up when I tried to understand the result by Raz and Tal that BQP$^O\nsubseteq$ PH$^O$. Aaronsons paper was helpful, but I still have some ...

Will updating to a new OS replace and system files that I may have accidental tampered with that has since cause the system to run unstable. For example,I’m currently running OS X Sierra I’m now ...

Imagine we have a program which does an infinite loop: while(true){loop} We run the program on a linux machine(assume the compilation is ok), then this linux ...

I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing ...

I am doing some natural language processing in R of a moderately sized corpus. I am cleaning up the corpus to remove nonsensical terms (e.g. escape/typesetting characters, URLs, HTML code). Part of ...

I'm fairly new to coding. I have done some for loops, conditionals, and def or functions. I have a project to construct some sort of algorithm let's call it A. Now within A, there are some primary ...

If we assume we have n triangles in a given graph. How can we find the n triangles in O(n) time? And we also have to add and remove edges in O(log k) when k=|v|

Is my solution considered right? It was in my test.

I always read that Linux kernel isn't pageable. If I'm not mistaken Windows, instead, divedes system virtual memory in a paged part (paged pool) and non-paged part (non-paged pool). The non-paged part ...

I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of ...

My following proof is correct about the big theta statement?

Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one. A greedy algorithm for this would keep removing digits ...

I was going through some text on Conway's Game of Life and it had a question that kinda got me confused. For a 5-cell configuration for Conway’s Game of Life that has been produced by Gosper’s ...

I was wondering if there's any initial configuration which generates a pure periodic behavior for Langton's Ant?

Please excuse my language, I am new to the topic. I am trying to classify/find a class of game that describes games such as chess, tic-tac-toe as a finite state machine. For those games, final ...

Let say I have time series of disk usage of last 30 days.. Given this information and with the assumption that the disk usage 'pattern' isn't changing dramatically over time, what would be a naive/...

I remember seeing this problem somewhere before, but don't remember what it's called and can't find it again. It was presented as two guys having $n$ phones each that don't ring when called. Each ...

FIND WORDS is the following decision problem: Given a list of words L and a Matrix M, are all words in L also in M? The words in M can be written up to down, down to up, left to right, right to left,...

According to this source, If A is reduced to B and A ∈ class X, then B cannot be easier than X. This reduction is used to show if a problem belongs to NPH – just reduce some known NPH problem to ...

Suppose we have a list $L$ consisting of $N$ numbers (may include repetitions). I am curious which is more computationally intensive to calculate, the mean or the median? Naively, I would suppose ...

Are there any known oracle separations between AWPP (defined in http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf) and QMA (the quantum analogue of MA)?

Given a directed graph $G = (V, E)$ and a starting vertex $v_1$. The graphs edges is this $\{(v_1, v_2), (v_2, v_3), (v_3, v_4)\}$ basically below $(v_1) \to (v_2) \to (v_3) \to (v_4)$ Can we ...

Consider this example, I did my pseudocode in python findCycle(G): for each edge e in E(G): if isThereCycle(G-e): G = G - e return G ...

Is there any simple definition to understand W1-hardness $\&$ W2- hardness in complexity theory? What I understood, that is the following: Let $\Pi$ be a decision problem with parameter $k$, then $...

The minmax algorithm is a popular strategy used to design chess engines. Usually, since the state-space of chess is huge, we choose a fixed depth and evaluate the game tree down to that level, and ...

If the size of transmitted data is 24kbit, what it is the optimum channel rate to deliver this data?

I am trying to show the existence of a polynomial size, bounded depth monotone circuit on the inputs $(x_1,\ldots, x_n)$ that gives $1$ if $\sum x_i \geq n/2 + n/\log n$ and $0$ if $\sum x_i \leq n/2 -...

It is known that a PDA with two stacks is equivalent to a TM. On the other hand a PDA with one stack is capable to recognise only context-free languages. Hence there is a kind of a gap between the ...

I have a tree as Is it an AVL tree? it seems to balanced for me.

I came across following problem: A system has n resources R0,…,Rn-1,and k processes P0,….Pk-1.The implementation of the resource request logic of each process Pi is as follows: ...

There are a few possible approaches to proof automation in modern Coq. Writing proof scripts with Ltac. This is the approach described in http://adam.chlipala.net/cpdt/, which the author uses to ...

I read these notes which mention IPS (Interactive proof system) https://people.csail.mit.edu/ronitt/COURSE/S12/handouts/lec6.pdf I then saw IPP being mentioned in complexity zoo: https://...

...

I know the meaning of SNR(signal noise ratio), but in an article, I saw a realistic SNR and I want to know its meaning.

In the propositions-as-types paradigm, we are still faced with the question : what types are propositions ? I currently know 3 different answers : Coq's sort Prop ...

I've been attempting to write a Bentley-Ottmann sweepline algorithm to transform a self-intersecting (complex) into a set of simple polygons. There are some instructions on this page (see the heading ...

In an image processing project (using opencv with python), I am trying to detect as precisely as possible the location of a rectangular object in a photograph. My final goal is to output the 4 corners ...

N people attend a gathering and will be given candies at the end. Each person gets at least one candy Maximum number of candies any ith person can be given, is given in an array A[ ] of length N ...

According the frame format of Ethernet Minimum Frame Size should be : 7Bytes + 1Bytes + 6Bytes + 6Bytes + 2Bytes + 46Bytes +4Bytes = 72Bytes Maximum Frame Size ...

I have a loop: for(int i = 1; i < N; i*=5) {...} where {...} is some statement. I'm trying to understand its run time. So, ...

Do the functions of the collatz conjecture and their inverses model a Trapdoor Function? That is, given f(n) = n/2 or 3n+1 and the inverse g(n)=2n and (n-1)/3 it is easy to go from n to 1 by ...