2
votes
0answers
15 views

Algorithm for a special case of SAT/#SAT

Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time? ...
-1
votes
0answers
12 views

Haskell Defining an infinite tree

I want to define an infinite tree in Haskell using infinitree :: Tree, but want to set a pattern up for each node, defining what each node should be. The pattern is 1 more then then its parent. I am ...
0
votes
1answer
12 views

What is the name for this … (alerting when threshold is exceeded, but only if dropped enough below threshold first)

Imagine: you are monitoring a system, and want an alert when certain measured value goes over a threshold value X. But perhaps the measured value is constantly fluctuating close to X, and you get a ...
1
vote
0answers
6 views

weights in a simple neural network

I have seen that in the material made by Andrew Ng about neural networks, he uses the following weights: so when I replace the final values of h_theta(x) in the formula: I got values near 0 and ...
-2
votes
0answers
19 views

direct map cache

Let's say, I have a direct mapped cache with: 1- size of 2048 KB 2- with cache line of 64 bytes 3- with 48-bit address space of the processor what is minimum number of bits that needed to store the ...
-2
votes
0answers
7 views

Runtime of a particular step of karatsuba algorithm

I am new to algorithms and was trying to calculate the runtime cost of each step of the karatsuba algorithm. Assuming you know what the karatsuba algorithm is, So I was not sure of the calculation ...
0
votes
0answers
11 views

What languages are allowed for CS GCSE [on hold]

I am a student in year 10 covering Computer Science (CS). I am very strong in web languages, e.g. HTML, CSS, JS, JQuery, PHP, MySQL. But since starting CS at school i have learnt a lot of Python, and ...
2
votes
1answer
37 views

Shortest path in a mutable graph

I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find all shortest paths from a root $s$. This is performed in time proportional to $V + E$, where $V$ ...
-2
votes
0answers
18 views

Difference between Windows 7 and Windows 8 [on hold]

Rather than GUI what's the technical difference between Windows 7 and Windows 8 operating systems.
0
votes
0answers
32 views

What are the kinds of data in computers? [on hold]

I wonder what are the types of data that someone could find if he conducts a survey. I mean, I am working on a project about robotics and the professor insists that I have to find data about robot ...
4
votes
1answer
40 views

Why are comparisons so expensive on a GPU?

While trying to improve the performance of my collision detection class, I found that ~80% of the time spent at the gpu, it spent on if/else conditions just trying to figure out the bounds for the ...
-1
votes
0answers
23 views

Multivariate optimisation data-structure / algorithm?

Based on constraints given at runtime, is there an efficient way of finding the answer? Given $n$ rows with $k$ columns. To exemplify, with $n=3$ and $k=3$: ...
3
votes
3answers
479 views

How are hash table's values stored physically in memory?

Question: How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often? My current understanding (could be wrong): Let's say I have 3 ...
0
votes
0answers
35 views

Proof of Non-Deterministic Space Hierarchy Theorem

I am trying to prove the Non-Deterministic Space Hierarchy Theorem, which says: If $f$ and $g$ are two functions such that $f=o(g)$ where $g$ is fully space constructible and $g(n) \ge \text {log }n$, ...
1
vote
5answers
73 views

How do I show that a DFA accepts only one word?

I want to show that $\qquad\displaystyle O = \{M : M \text{ is a DFA}, |L(M)| = 1\}$. Here $|L(M)|=1$ means the DFA contains only one state. I really don't know where to get started in this ...
3
votes
3answers
49 views

Reviews of work in the field of partial evaluation (post 1993)

I'm looking for relatively new reviews of research work on partial evaluation. The most recent work I've found is "Tutorial notes on partial evaluation" by Charles Consel and Olivier Danvy (1993). The ...
2
votes
1answer
31 views

What is the meaning of undecidability in Rice Theorem?

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable? As an example the following language is ...
-2
votes
0answers
14 views

Deleted some core drivers now pc not starting [on hold]

I deleted some core drivers now my PC won't start. It is an Alienware with windows 7 professional 64bit
0
votes
2answers
28 views

Why does the Θ-class survive adding a constant only for positive, monotonic, and non-decreasing functions?

I know that for positive monotonically non-decreasing functions, f(n) and g(n), f(n) = O(g(n) + c) entails f (n) = O(g(n)) Why is this always true only for ...
-3
votes
0answers
31 views

is there an algorithm to calculate the sum of two egyptian fractions? [on hold]

I would like to create a programm of egyptian fractions and the sum and substraction of them
1
vote
1answer
29 views

Rubik Cube Algorithm for general n

I am not sure if this is the right place , but: Is there an algorithm for solving $n\times n \times n$ rubik's cube (non-trivial one)? If so how efficent is it? Now say I have a $n \times \ldots ...
-2
votes
0answers
9 views

Mux and Decoder Examples Challenges

i get confusing on Digital Design Course. I read on my books as an example that (1) is different from (2) to (4). anyone could describe it for me?
0
votes
0answers
23 views

Finding Contextual Nodes in a Knowledge Graph

I'm currently participating in developing a knowledge graph that uses ConceptNet and a few others as its data sources. It uses the same architecture as ConceptNet namely it is stored as a hypergraph ...
1
vote
0answers
15 views

Research work on computational models for a “specific” person's behaviors

Is there active research work on creating computational models of a "specific" person's behaviors (general behaviors, emotions, actions...)? What are some references for such research? I tried google ...
-1
votes
1answer
37 views

If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

Sets $A$ and $B$ are given but we don't know what kind of sets they are. If we know that $A \cap B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable? what ...
-5
votes
0answers
10 views

Write a program that simulates flipping a coin repeatedly and continues until three consecutive heads are tossed. c++ [migrated]

Write a program that simulates flipping a coin repeatedly and continues until three consecutive heads are tossed. c++ $#include <iostream>$ $#include <cmath>$ $#include <string>$ ...
0
votes
1answer
32 views

Example of worst case input for Build-Max-Heap

Is there a worst-case inputs for Build-Max-Heap? I know there is but I just couldn't paint a clear picture of it in my head.
0
votes
1answer
53 views

Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$

I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a ...
0
votes
1answer
35 views

LL(k) Prediction Techniques (and Insight on method applied)

I'm requesting references for LL(k) in situations where k > 1 for reasons described below. I'm looking for ...
-1
votes
0answers
8 views

Using polymorphism (Java) in order to create a submenu [on hold]

I'm writing a Java class that simulates a program menu. It uses two packages, one of which contains an interface. I want to be able to use this code to create a separate sub-menu without rewriting ...
-1
votes
0answers
32 views

Morphism properties [on hold]

I'm searching morphism properties in a formal language. But i only find math (algebraic) properties like identity and associativity. Are math and formal language same properties? Or where can i find ...
0
votes
1answer
42 views

Set Intersection with asymmetric set sizes

I'm looking for an algorithm to perform set intersection where set $N_1$ is very small and set $N_2$ is very large. Due to the constraints of the problem I am solving, I cannot rely on an algorithm ...
1
vote
1answer
25 views

Construction of a counter automaton for the complement of the palindromes

How would I go about constructing a nondeterministic 1-counter automaton for the language $L$ that is the complement of the palindromes $\overline{L}=\{ww^{rev}\}$ over a 2 symbol alphabet $\Sigma = ...
-1
votes
0answers
22 views

How to convert a context free grammar to a left linear grammer

Can anyone tell me whether the following grammar is LL(1) or not if not can you please suggest how to convert it into LL(1)? To the best of my knowledge it is not LL(1) because ...
1
vote
1answer
32 views

FNP ⊂ FPSPACE or FNP ⊆ FPSPACE?

It is clear, that NP ⊆ PSPACE holds and that it is unknown if the strict inclusion holds. How is it if one looks at the corresponding functional complexity classes? Does FNP ⊂ FPSPACE hold?
-3
votes
1answer
27 views

A finite automaton accept no string

How can a finite automaton over(0,1) doesn't accept any string? I only can think of s->a->q->F Where the final state F is empty set. Is that true ...
0
votes
0answers
16 views

Is it possible to find closeness centrality using Gephi? [on hold]

I'm a newbie to Gephi. I need to calculate the centrality measures. Is there an option/plugin available to calculate them ?
3
votes
1answer
171 views

What's the purpose of ANDing a bit mask with all bits set to a value?

I'm adapting an algorithm for calculating a CRC 16-bit CCITT (XModem) value from an ASCII input. I've found some code here. I'm using the function the poster has in his question, but I've noticed at ...
-1
votes
0answers
16 views

How to solve equations that have asymptotic notations in equations?

Hi i'm new to algorithms and need some help understanding asymptotic notations. So my main issue is how do you go about solving equation to find whether they are true or not, such as n^2 + O(f(n) = ...
-1
votes
0answers
16 views

Running time of algorithms [on hold]

Suppose for all integers $0 ≤ m$, $n < N$, Algorithms $A$, $B$, and $C$ compute the following: Algorithm $A$ computes $n + m$ in time $O(A(N))$ Algorithm $B$ computes $m · n$ in time ...
0
votes
1answer
38 views

Build-Max-Heap vs. HeapSort

I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that: HeapSort: A procedure which sorts an array in place. Build-Max-Heap: A procedure which runs in ...
0
votes
1answer
17 views

Pumping lemma of regular language [duplicate]

I was wondering in how to solve this question, I feel a bit confused: for $\Sigma = \{1,\#\}$, consider $$D=\{w \mid w=x_1 \# x_2 \# \cdots \# x_k \text{ for } k \geq 0, \text{ each } x_i \in 1^*, ...
0
votes
0answers
44 views

Why is this language is not context-free? [duplicate]

Anyone could apply some theorem to prove this is not context free? I read lot's of material. it's not homework, it's not exam, it's not anythings. I want to learn, if some people try to answer this ...
1
vote
0answers
30 views

Network clearance algorithms

In the network clearance problem, we are given a simple undirected graph with a capacity assigned to each edge (and/or to each vertex). Each edge can transport up to its capacity each time step (i.e., ...
1
vote
1answer
29 views

Interpretation of '1/3' in IEEE floating point representation

For a rational number 1/3 below is the floating point representation(64 bit) of decimal expansion 0.3333333.... As per the above bit structure, I would like to ...
-1
votes
0answers
151 views

Trying to implement a simple neural network, without success [on hold]

(Background: I am a Civil engineer, and decided to read through Mitchell's ML book) I am trying to replicate an example from Mitchell's book (first edition), Figure 4.7 (later editions seem to have ...
0
votes
1answer
22 views

Text features in decision tree

Right now I am doing some problems on application of decision tree/random forest. I am trying to fit a problem which has numbers as well as strings (such as country name) as features. Now the library, ...
0
votes
0answers
25 views

Topics in Computability [on hold]

I am taking the graduate course Computability and at the end of the semester I will have a presentation. The prof told us to chose the topic. Do you have any suggestions??
2
votes
1answer
42 views

What type is this sorting algorithm?

I needed to sort vertices into buckets as an optimization for collision detection later. I came up with this: go over all the verts and count the size that each bucket needs to be to contain them ...
6
votes
4answers
113 views

Finding the two largest of five small integers as quickly as possible

I use a variation of a 5-cross median filter on image data on a small embedded system, i.e. x x x x x The algorithm is really simple: read 5 unsigned ...

15 30 50 per page