0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
-3
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
2answers
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?
-1
votes
0answers
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, ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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$ ...
-2
votes
0answers
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 ...
-2
votes
1answer
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 ...
2
votes
1answer
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 ...
-4
votes
1answer
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 ...
-2
votes
0answers
28 views

What language for AI programming? [on hold]

What language should I use for AI programming? Python or C++?
-3
votes
0answers
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?
0
votes
1answer
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)$ ...
4
votes
0answers
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$ ...
-1
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
2answers
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 ...
4
votes
0answers
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 ...
-1
votes
1answer
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
4
votes
2answers
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 ...
-1
votes
0answers
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?
0
votes
0answers
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 ...
1
vote
2answers
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 ...
-1
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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: ...
-1
votes
0answers
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.
2
votes
1answer
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 ...
2
votes
1answer
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 ...
3
votes
0answers
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 ...
-1
votes
0answers
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
5
votes
0answers
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 ...
2
votes
0answers
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 ...
-2
votes
0answers
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 ...
12
votes
3answers
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 ...
-2
votes
0answers
25 views
0
votes
0answers
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.
34
votes
16answers
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 ...
10
votes
1answer
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 ...
1
vote
1answer
41 views

Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where ...
1
vote
1answer
71 views

Is finding a solution of a satisfiability problem harder than deciding satisfiability?

Is the problem of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression? In other words, is there another ...

15 30 50 per page