1
vote
1answer
10 views

How to compute number of ways to place 1's in an $M \times M$ matrix so that every row and column has $k$ 1's?

On math.stackexhange, someone asked the problem of counting the number of ways to place $1$'s into a $10 \times 10$ matrix so that every row and column had $5$ $1$'s. I came up with a recursive ...
0
votes
0answers
6 views

error: Index exceeds matrix dimensions in matlab [on hold]

I run my code in order to sort a structure array into decreasing order. I don't understand why this error appear, what this means and how to solve it. Any help would be appreciated!
0
votes
0answers
7 views

Radix Tries, Tries and Ternary Search Tries

I originally posted this over on Stackoverflow but realised that it may be better suited to the Computer Science zone. I'm currently trying to get my head around the variations of Trie and was ...
0
votes
0answers
6 views

GINN( Global-Similarity-based Indirect Noisy Node) ALGORITHM [on hold]

Please suggest java coding of above algorithm GINN( Global-Similarity-based Indirect Noisy Node) for further references please refer following IEEE Research paper "Sensitive label Privacy Protection ...
1
vote
1answer
11 views

How to find out what are accept, loop and reject in this Turing Machine?

I am trying to find out accept, loop and reject in this Turing Machine because it doesnt have any...I am not sure if I completely understand it but this is the turing machine I am talking about... ...
0
votes
0answers
19 views

career in CS for a physicist [on hold]

I don't know if this is the most appropriate section to post this kind questions, if it's not, please tell me and I'll post it in the appropriate stackexchange section; thank You in advance! The ...
1
vote
0answers
11 views

Using image processing to infer if a seat is occupied [on hold]

I'm looking into different attendance taking options for a particularly large seminar class (600ish students) and I was thinking - what if a picture was taken of the seats, maybe with a visual cue on ...
4
votes
0answers
20 views

Matrix equality up to row/column permutations problem name

Sorry for the trivial question; has the following decision problem an "official" (possibly short) name? Given two $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same ...
3
votes
1answer
25 views

Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$

Let $L = \{ <M> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\}$. Is $L$ decidable? Recognizable? Given that membership in $L$ asserts something about $M$'s behavior on an ...
2
votes
1answer
61 views

Can every program be turned into a quine?

Given a program $P$ which takes a binary string as input, can one always (effectively) construct a program $P'$ such that $P'(0x)$ runs $P(x)$ and $P'(1x)$ outputs the source code of $P'$? I didn't ...
2
votes
0answers
12 views

totally ordered multicast with Lamport timestamp

I'm studying Distributed Systems and synchronization and I didn't catch this solution of totally ordered multicast with Lamport timestamps. I read that it doesn't need ack to deliver a message to the ...
0
votes
0answers
11 views

What is the difference between Inclusive and Non-Inclusive Cache?

Inclusive cache is one where cache at each level(L1, L2, L3 etc) contains same information at any point of time, whereas ...
0
votes
0answers
13 views

(tensor decomposition) Is there a reference/source paper for the TUCKER_ALS() in Tensor Toolbox for MATLAB? [on hold]

TUCKER_ALS computes the best rank-(R1,R2,..,Rn) approximation of tensor X, according to the specified dimensions. I am using MATLAB Tensor Toolbox Version 2.5. I am wondering if I write a paper, how ...
1
vote
1answer
12 views

The min cut capacity in a network based on a bipartite graph (Hall's Theorem)

Thanks to Yuval Filmus, I got to read these lecture notes by Trevisan. At the bottom half of Page 5, The capacity of cut $S$ is the number of edges that go from $S$ to $\overline{S}$, that is ...
0
votes
0answers
16 views

Is the vertex cover problem NP-Hard in general graphs and in P for bipartite graphs? [on hold]

Wikipedia says that finding the minimum vertex cover is NP-Hard. However, for bipartite graphs, I can solve the maximum matching problem with Hopcroft-Karp in polytime and then, through Koenigs ...
0
votes
1answer
224 views

Is there a model of computation, that tries to be realistic? [on hold]

For instance, the tape on a Turing machine is infinite, where as we usually only have a finite amount of available memory. Secondly Turing machines are not really convenient IMHO for proving things ...
2
votes
0answers
19 views

Measuring similarity of music, using lossy compression [migrated]

I have two sound clips $C_1,C_2$ which are pretty similar. I'd like to measure how perceptually similar they are, i.e., how similar a human would perceive the two to be. Is there a way to use a ...
-1
votes
0answers
22 views
1
vote
1answer
41 views

Big O running time for this algorithm?

Here's the code for the algorithm: Foo(n) lcm = 1 for i = 2 to n lcm = lcm*i/Euclid(lcm,i) return lcm The running time of ...
1
vote
1answer
29 views

Computer Architecture - Von Neumann

With regards to introductory (beginner) Von Neumann computer architecture, how does a program change the order in which instructions are executed? I know the control unit is responsible for ...
-1
votes
1answer
17 views

Difference in CPU Wattage Question [on hold]

If I have 2 CPU's of the same manufacturer... say AMD Both are Quad-Core, Both are rated at 3.6Ghz 1 is 100W, the other is 65W Will the one with the higher wattage out-perform the lower one and ...
2
votes
2answers
41 views

Intersection/Union of recursively enumerable languages that aren't decidable?

For $L_1, L_2 $ and $L_1 \in RE $ and $ L_1\notin R$ and $L_2 \in RE $ and $ L_2\notin R$ I was asked to prove/disprove if the following can occur: $L_1 \cap L_2 \in R$ $L_1 \cup L_2 \in R$ $L_1 ...
0
votes
0answers
15 views

Boyce-Codd Normal form and violation issue

I have the standard problem of BCNF in front of me, in the table hospital we have: ...
-2
votes
0answers
15 views

External HDD I/O Error, disappearance problems [on hold]

I have a problem with my HDD Toshiba Hitachi HDS5C3020BLE630 2.0 TB.. I recently bought it with a damaged IcyBox where it came from, and I attempted to boot it but it's not working.. I tried many ways ...
0
votes
0answers
7 views

Data Mining vs Evolutionary Computation as subject for engineering course? [on hold]

I am a student pursuing Bachelor of Technology in Computer Science and Engineering entering my final year. I have a choice to pursue on of these two courses. Which one should I opt for? I have been ...
2
votes
0answers
25 views

Sub-dividing a 2d array into regions

Suppose I have a array of real numbers with $n$ rows and $m$ columns. I want to consider possible ways of dividing that array into rectangular regions of three different possible types: a constant ...
0
votes
2answers
42 views

What is the Big O estimate of a nested for loop?

I am trying to figure out what the big o estimate of the following for loop is. ...
5
votes
2answers
69 views

Is there anything lower than the bit level of 1s and 0s?

When learning about the architecture of computers and how it works, we are thought that the lowest language that we can find that the machine understands is binary as 1&0. And anything that we ...
3
votes
5answers
50 views

Could program verification techniques prevent bugs of the genre of Heartbleed from occurring?

On the matter of the Heartbleed bug, Bruce Schneier wrote in his Crypto-Gram of 15th April: '"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.' I read several years ago that a ...
2
votes
0answers
14 views

What are ways that you might analyze relations extracted from text

In the coursera NLP course, Dan Jurofsky says you might want to extract relations from text to serve as input to other algorithms. What are examples of ways that researchers have used or might use ...
2
votes
1answer
25 views

Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS?

In section 9.2 of CLRS (Introduction to Algorithms; page 185 in the 2nd edition and page 215 in the 3rd edition), a randomized selection algorithm is presented. For its analysis, $T(n)$ is a random ...
-3
votes
0answers
26 views

Grammar for permutation [on hold]

What is the minimal automation that can parse a string abab into following AST? How should the grammar look like?
0
votes
0answers
17 views

Simulating a Turing Machine with finite memory with a regular TM [on hold]

A Turing Machine with memory is defined just like a regular TM, with the addition of finite memory size n and the transition function d(mem). At each step, the transition depends on the current state, ...
2
votes
2answers
68 views

Breaking up sum of power of 2s

I'm writing an algorithm to solve a research problem involving searching for numbers on very large arrays. I encountered a sub-problem that requires me to break up sums of numbers which are power of ...
2
votes
2answers
47 views

Showing that deciding whether a given TM accepts a word of length 5 is undecidable

I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this: Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$ accepts ...
0
votes
0answers
24 views

Cutting/merging subgraphs so that they are equally sized [on hold]

Hi so I'm pretty new to graph theory. I have a directed graph with many seperate connected components of various sizes. I've found that there are algorithms for cutting a graph into a number of ...
1
vote
1answer
14 views

If A is mapping-reducible to B and is not mapping-reducible to co-B, is A Turing-reducible to co-B?

If $A \leq_m B$ and $A$ is not mapping reducible to $co\text{-}B$, then $A \leq_T co\text{-}B$. Is this true? My intuition is false even if we can find some special case to make it true such as ...
0
votes
0answers
14 views

Choosing the best set of keywords [on hold]

I have a dataset of tweets collected using twitter streaming API on a particular topic (say 'football') using around 40 keywords. Now if I'm going to track the same topic (football) in future how do I ...
0
votes
0answers
15 views

Natural language processing reference [on hold]

I am looking for references to natural language rocessing from java's perspective. I have read 'Foundations of Statistical Natural Language Processing' by Chris Manning. There seems to be an ...
-2
votes
0answers
17 views

Randon 3SAT - when is a clause ture? [on hold]

Hi i have been give some random 3Sat data and ask to WalkSAT to solve for uni. Only thing is I don't really know where to start. I have some clauses say -61 -63 26 -40 92 57 -74 -84 54 How do I ...
0
votes
0answers
15 views

What is the Diffrence between the Unity shell interface and a Desktop enviornment? [migrated]

I am writing a report and I have stumbled across a topic I am not quite sure how to to discuss. Essentially I have been doing a little research on the Unity shell system and its usage in Ubuntu ...
2
votes
1answer
57 views

Interpolation Optimization Problem

I will try to give the motivation behind this problem and later the math formality. Given a grayscale image (1 Channel - M by N Matrix). Someone marks some pixels as anchors. Now, you need to ...
0
votes
1answer
63 views

What is the formal description of a Turing machine?

I was asked to give a formal description of a Turing machine I have no experience with this, and was wondering what "formal description" entails.
1
vote
1answer
22 views

Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. ...
9
votes
3answers
613 views

Why use languages in Complexity theory

I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model. I have a pretty basic question, but ...
5
votes
1answer
57 views

Question about threads and locks

I am currently reading Fuss, Futexes and Furwocks: Fast Userland Locking in Linux and came across this quote: In a fair locking scheme the lock is granted in the order it was requested. This can ...
1
vote
1answer
48 views

Shortest directed path connecting given subset of vertices

Given weighted directed graph $G = (V,E,w)$, where $w : E \to \mathbb R^+$ source vertex $v \in V$ vertex subset $U \subset V$ how to find a shortest directed path from $v$ containing all vertices ...
0
votes
0answers
10 views

Vapnik-Chervonenkis dimension. Exercise [on hold]

Let X={2,4,6,8} the instances space. S'={6,8}. Set of hypothesis ...
0
votes
0answers
19 views

How to begin with automata paper? [on hold]

I am new to Automata Theory paper and i am just beginning with the basics by following Kamala Krithivasan's Introduction to Formal Languages, Automata Theory and Computation. Can somebody explain as ...
5
votes
3answers
406 views

Is it compulsory that every infinite set be non regular?

I am confused regarding the statements provided by one of our faculty regarding "Is it compulsory that every infinite set is non regular though every finite set is a regular set". Providing ...

15 30 50 per page