# All Questions

4 views

### Hoare Calculus Incorrect Assignment Axiom

I'm currently preparing for an exam and recently came across the following exercise and would like to know whether my solution would be correct. Exercise: Prove that the following axiom is not ...
7 views

### Implementation of pipelined caches

I've read that the intel i7 has a L1 cache latency of 4 clock cycles and is pipelined, same can be said for arm a9 which has 3 stages devoted for instruction fetch. How is the L1 cache implemented ...
8 views

### How to exclude Code snippets from Microsoft Words spell check [migrated]

I am writing on an computer scientific report and I'm really tired of Word 2010 always switching between languages (code in english, text in german) and marking all my code red just because there are ...
8 views

### TM for F(x)= x div 2 + 1

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
22 views

### What is the min # of moves to sort an array from 1 to n?

Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to any place you want (insert to any place, not swap). Prove ...
17 views

### How do I prove all constants to some exponential power belong to little-o of some function

I'm trying to prove that c2n = o((loglog n)n) (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as n ...
32 views

### A recursively enumerable language and a recursively enumerable set

I am confused between these two terminologies: recursively enumerable language, recursively enumerable set. Do they have the exactly same meaning?
14 views

### How do I find data rate flowing across cable to display? [on hold]

I have a question for my Computer Graphics course where we're tasked with finding out the data rate that goes across the cable to my monitor's display. Is there any way to find this out? If it helps, ...
5 views

### Hierarchical learning in a non-static environment

I've been reading about hierarchical reinforcement learning (HRL), in particular it's application to a simple delivery task as show here. While reading the paper, I noticed that the environment ...
8 views

### Has hierarchical learning been embodied in a robot before?

I've been reading about hierarchical reinforcement learning (HRL) and it's applications. A well-written literature review on the subject can be found here. However, I was wondering if research has ...
23 views

### Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ ...
14 views

### Prefix closure of the language [duplicate]

If Σ is a finite set of symbols and α is a word in Σ ∗ , then a word β in Σ ∗ is said to be a prefix of α if α = β γ for some γ ∈ Σ ∗ . For example, the prefixes of the word abbab are λ , a , ab , abb ...
29 views

### Determine if DFAs accept any word which contains bb

Let Σ= { a , b , c } . Describe an algorithm that takes as input a deterministic finite automaton M = ( Q , Σ , τ , s , A ) and determines whether or not M accepts a word containing bb (i.e. a word of ...
32 views

### Converting decision problems to grammars?

I'm struggling to understand some concepts related to the relationship between language and computability theories. Can we convert decision problems to the corresponding grammars describing the ...
31 views

### Count of all simple paths between two vertices in a Complement graph

A path is simple if it repeats no vertices. How many simple paths between two vertices in Complement graph? One way is listing the simple paths is to use depth-first search. but i think it should be ...
28 views

### What language for AI programming? [on hold]

What language should I use for AI programming? Python or C++?
15 views

### Bypass security restriction in firefox [on hold]

I want to bypass error code: sec_error_unknown_issuer in firefox 31. When I try to load a page, it always displays this error, and no means of adding the security exception at all. what shall I do?
24 views

### Gap between numbers in fixed-point vs. floating point arithmetic

If $r$ is a machine-representable number and $f(r)$ is the next larger machine representable number, are the following true or false? In fixed-point arithmetic, the distance between $r$ and $f(r)$ ...
19 views

### Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
27 views

### Looking for an algorithm that can create bitstreams [on hold]

I am trying to figure out an algorithmic way to generate bitstreams with N number of bits . So for example you input 2 and the output will be: 00 01 10 11 I am doing research on data compression ...
56 views

### RMQ with $\sqrt{n}$ space?

I'm asked to design an RMQ data structure (Range Minimum Query) for an array that has $<=\log(n)$ local minimums (a local minimum is an index $i$ such that $A[i-1]>A[i]<A[i+1]$). There are 2 ...
73 views

### match an array with a given set of arrays

We have a set of 24 distinct arrays, each array has 36 elements and each element can have one of 13 possible values. Then we're given an array X (this array is certainly part of our set) and we have ...
27 views

### Model Join calculus as hypergraphs

I'm not sure if this is the right site to ask, but I couldn't find a another one. Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For ...
37 views

### Distributing values of an array into smaller arrays with bounded sums

Take the following array of integers: [60, 45, 30, 45, 45, 5, 60, 45, 30, 30, 45, 60, 60, 45, 30, 30, 60, 30, 30] They need to be sorted into pairs of sub-arrays. The first sub-array in each pair ...
14 views

### Reading an image from same directory? [on hold]

Suppose I have been given an image called in.png in the same directory as my main.cpp. I have to read that image and put it into b i created in the main body. I have been given a class PNG, and the ...
22 views

### What is the global function we are trying to Optimise with Clustering Algorithms?

I am doing some reading (and implementation) of some Clustering Algorithms. First I started with the well known K-Mean algorithm and implemented it directly from a paper. Got a kind of decent ...
17 views

### complex python problem [on hold]

Write a program that reads n digit number. after reading the number, compute and display the sum of odd positioned digits,multiply all even positioned digits and add the two numbers. I have attempteed ...
165 views

### Direct NP-Complete proofs

I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are ...
13 views

### Simple proof of the polynomial smoothed runtime of k-means?

The k-means algorithm has exponential worst-case runtime but its smoothed runtime can be shown to be polynomial. Is there a simple proof of this?
13 views

### Is k-means parallelizable (other than the data parallelism of the distance function computation)

The k-means algorithm is known to be NP-hard. While the distance function computation in the algorithm loop is data parallel, the algorithm is iterative and may become exponential in the number of ...
27 views

### Counting inversion using D/C

This is a homework. It looks easy, but not really. A list of integers $a_n$, for every $i<j$, if $a_i>2a_j$, then it is an inversion. Count the inversions in the list, and return the count and ...
24 views

### Convolution of Haar filter

In "Conceptual Wavelets" (2009) by D. Lee Fugal, on pg 47 he writes Conv ([-1, 1], [1, 1]) = [-1, 2,-1] When I do it I get ...
45 views

### Creating a binomial heap from an array in Θ(n) time

I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert ...
18 views

### A bound for the minimum vertex cover of scale-free graphs

For a complete graph, the size of minimum vertex cover is $n-1$. I was wondering whether there exist an upper bound (or an expected value or upper bound) for the size of minimum vertex cover for ...
84 views

### Finding the max XOR of two numbers in an interval: can we do better than quadratic?

Suppose we're given two numbers $l$ and $r$ and that we want to find $\max{(i\oplus j)}$ for $l\le i,\,j\le r$. The naïve algorithm simply checks all possible pairs; for instance in ruby we'd have: ...
10 views

### simple explanation of simrank [on hold]

could you please explain in simple terms what do you mean by Simrank.I have to take a seminar on SimRank but I can't understand the mathematical equations that points to this topic.
15 views

### How do I measure the reliability of a confidence value in a predictive algorithm?

Supposing I have some algorithm that is able to provide me with a confidence value for some event occurring. Let's say on day 1 it tells me that there is a 80% chance it will rain, on day 2 it tells ...
58 views

### Which article in front of O(.), Ω(.), …?

Writing a survey, I am confronted to a very difficult and -- I dare say -- deep issue: I have many sentences mentioning or stating results of the form "a $\Omega(\sqrt{n})$ lower bound", or "a ...
34 views

### What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of ...
16 views

### Books for Hadoop [on hold]

I am a new graduate student. I want to study and work on Distributed systems. I want some good books for Hadoop which will help me with practical knowledge
58 views

### Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine. Is ...
37 views

### Finding a convex hull for a collection of points

I have an alternative algorithm for the problem of finding a convex hull for a collection of points. It is somewhat similar but not the exact of Graham scan. Find a point that is guaranteed to be ...
37 views

### Formal definion of the notations used in measuring time complexity? [duplicate]

Is there a formal definition of notations $\theta, O, \Omega, o, \omega$ given in asymptotic analysis of algorithms. I was interested as I read those notations from the book "Introduction to ...
1k views

### What does the processor do while waiting for a main memory fetch

Assuming l1 and l2 cache requests result in a miss, does the processor stall until main memory has been accessed? I heard about the idea of switching to another thread, if so what is used to wake up ...
25 views

### Is my running time function and its solution correct?

This is my problem: Given a function; ...
26 views

### Suggestions for Research Topics [on hold]

I need your assist to provide some suggestions for research topics on computer science. I have no idea what I will write about so far.
4k views

### How to fool the “try some test cases” heuristic: Algorithms that appear correct, but are actually incorrect

To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem ...
95 views

### Efficient algorithms for vertical visibility problem

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task: The problem: we are given a two-dimensional square box of side $n$ whose sides are ...