# All Questions

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? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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.
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 ...
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 ...
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$: ...
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 ...
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$, ...
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 ...
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 ...
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 ...
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
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 ...
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
29 views

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 ...
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?
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 ...
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 ?
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 ...
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) = ...
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 ...
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 ...
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^*, ...
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 ...
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., ...
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 ...
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 ...
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, ...
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??