# All Questions

31,463 questions
Filter by
Sorted by
Tagged with
6 views

### Is there a corpus of “general” C programs?

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++ ...
11 views

### Time complexity of rotation array m times using temporary array

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 ...
11 views

### Algorithm for detecting overlaps

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

### Genetic algorithm pool selection with fitness multiples

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 ...
10 views

### map 64-bit values into 32-bit range

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 ...
19 views

### Converting DFA to RE [duplicate]

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 ...
19 views

### Karatsuba Multiplication Rule in dividing a Number in two parts

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 ...
18 views

### how to approach this type of time complexity questions? [duplicate]

given this function, ...
17 views

### Algorithm Analysis of Insertion Sort

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 ...
27 views

### Basic complexity theory (in Oracle Separation of BQP and PH)

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 ...
13 views

### Updating to macOS Mojave [on hold]

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 ...
32 views

### Is it Turing recognizable/decidable?

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 ...
31 views

### Probabilistic halting problem

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 ...
15 views

### Where can I download a dictionary of computer technology terms for natural language processing? [on hold]

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 ...
23 views

### When should I refine my code? [on hold]

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 ...
23 views

### How can we find number of triangles in a given undirected graph? [on hold]

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|
24 views

### Graph with weighted edges question [on hold]

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

### Are Linux kernel modules a sort of Linux system paged pool? [migrated]

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 ...
44 views

### How to find an algorithm's complexity from actual running times

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 ...
22 views

### Contradict or Proof the following statement

My following proof is correct about the big theta statement?
24 views

### Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal

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 ...
33 views

### Gosper's Glider Gun

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 ...
143 views

### Langton's Ant Periodic Behavior

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

### Testing if a state is in final state

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 ...
14 views

### 'simple' algorithm that can predict disk usage or 'time to be full'

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/...
17 views

### Problem of making entities agree on some wavelength

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 ...
1k views

### is FIND WORDS in P?

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,...
33 views

### If X (an NP-hard problem) is polynomial-time many-one reducible to problem Y, then Y is NP-hard. Why is it the case?

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 ...
739 views

### Computational complexity of calculating mean vs median?

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 ...
5 views

### Oracle separation between AWPP and QMA

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)?
41 views

### Traversing a Graph polynomial time

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 ...
26 views

### graph theory conventions, difference between a PATH and a GRAPH?

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 ...
17 views

34 views

### A push-down automaton with two stacks which is equivalent to a linear-bounded automaton

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 ...
44 views

### Is the following a AVL tree?

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

### How can I solve this deadlock related problem mathematically?

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: ...
20 views

### For proof automation in Coq, when is it appropriate to use canonical structures or Equations instead of Ltac?

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 ...
12 views

### Relationship between IP, IPS, IPP and NP

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://...
14 views

...
15 views

### What is the meaning of realistic SNR? [on hold]

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.
69 views

### What types are propositions?

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 ...
30 views

### Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons

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 ...
26 views

### Minimum Bounding Quadrilateral

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 ...
16 views

### Maximising Success of candy distribution: Maximising the absolute difference

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 ...
14 views

### Calculate minimum and maximum Ethernet (IEEE 802.3) frame size from frame format

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