0
votes
1answer
9 views

Extended knapsack: is it NP-complete?

I have a problem of this form coming from an application domain, similar to the classical knapsack problem but not quite the same: Maximize the value of ($\sum_{i=1}^n v_i \cdot x_i) + B \cdot ...
-2
votes
0answers
9 views

data structure and algortihm [on hold]

You are to write a simple essay editor with the following requirements: Requirements: 1. An essay contains a number of sentences or lines. 2. The entire essay shall be kept in a linked list; each ...
0
votes
3answers
109 views

Is every problem in NP solvable?

Is every $\sf NP$-problem solvable or are there problems that have no working algorithm to solve but have algorithms to verify?
0
votes
0answers
29 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
0
votes
0answers
14 views

Scheme Function For Flattening a Binary Search List [on hold]

Write a Scheme function, (contain-list order alist), that consumes a symbol, order (which is either 'A 'D, and produces the corresponding flattened list, either in ascending order if 'A is consumed, ...
1
vote
1answer
23 views

Conversion from assembly program to low-level machine language

While studying COMPILER-DESIGN through an online book from Google-Books,referenced as Compiler Design By A.A.Puntambekar, I got stuck across a line. Actually, I am ...
3
votes
0answers
8 views

Substituting “remaining variables” during partial evaluation?

In "Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler" Yoshihiko Futamura wrote: "[Some] portions of a computation process [...] are not evaluated at partial ...
3
votes
0answers
22 views

Polynomial time algorithms on strings

I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known. To be more precise, let $\Sigma$ be a finite alphabet. I am looking ...
1
vote
1answer
156 views

Subset sum algorithm in O(n³ log n)?

I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers. After my research, I'm lost between all the algorithms ...
3
votes
1answer
36 views

PARTITION with 0-sum assumption

The PARTITION problem: $\{\{x_1,...,x_n\}: \exists I\subseteq[n], \sum_{i\in I}x_i=\sum_{i\notin I}x_i\}$ is well known to be NP-complete. My question: does the partition problem remain ...
1
vote
0answers
22 views

Natural Language Parser that can handle syntactic and lexical errors

I have some background in natural language processing and I know that all parsers (top down or bottom up, or mix), at least when I studied just about a few years ago, cannot handle any error. A small ...
2
votes
1answer
34 views

What is oblivious RAM and how does it work?

Could anybody explain me what exactly oblivious RAM is? I found the following explanation which makes it kind of clear to me, but I would like to get a sense of the technical aspects: Encryption ...
0
votes
0answers
5 views

SCAN and CSCAN algorithms of disk scheduling

I am having hard time understanding the working of SCAN and CSCAN algorithm of disk scheduling.I understood FCFS,Closest Cylinder Next but heard that SCAN resembles elevator mechanism and got ...
-1
votes
0answers
15 views

Calculating time for refreshing the whole memory [on hold]

A main memory unit with a capacity of 4 megabytes is built using 1M x 1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is ...
0
votes
0answers
16 views

Substitution-based Operational Semantics of algebraic datatypes

Assume, I want to define the operational semantics for some subset of ML. ...
0
votes
1answer
24 views

What is alternative parenthesizations?

I'm a person using english as the second language and reading CLRS book at a slow pace due to my poor english. I have a problem with understanding the meaning of the word 'alternative'. In page 303 on ...
1
vote
1answer
28 views

If pref(L) is regular, does that imply L is regular?

I have this exercise for homework: Say we have a language L. we know that the language pref(L) (all the prefixes of ...
1
vote
0answers
17 views

Separate points inside set

I have a set of points corresponding to pictures on map. Because location precision is not very important, I want to separate the points inside the set to maximize the summed up distance between the ...
1
vote
1answer
60 views

Is There a Programming Language That Embraces Globals?

All programming languages have globally defined symbols. While best practices invariably abjure their use as mutable entities the philosophy of what is mutable and what is not mutable is highly ...
1
vote
1answer
47 views

How to prove that this is NP complete?

I'm trying to prove that if P = NP, then {⟨a, b, c⟩ : a + b = c} (as addition over N) is NP-complete. I think I managed to prove that it is in NP, but I'm not sure what would be a good NP complete ...
3
votes
1answer
67 views

Question regarding Cook-Levin theorem proof

I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing ...
-1
votes
0answers
20 views

DFA of a language question [on hold]

For an example exercise in class, we were told to try out this question at home: Working with a binary language where the 3rd character is always a 1, we were asked to find an invariant for this ...
2
votes
1answer
15 views

Balanced Weight Distribution in Bins/Buckets

Let $W = \{w_1,w_2,...w_n\}$ be a set of integer weights. Let $B = \{b_1,b_2,...b_m\}$ be a set of buckets, with $m \leq n$. Let $T(b_j)$ represent the total weight present in bucket $b_j$, which ...
0
votes
0answers
21 views

Generate a Random Diagonally Dominant Matrix

I would like to write a function to generate a diagonally dominant matrix of random values. What I'm ultimately leading to is writing a code to implement the Jacobi method on this matrix in CUDA for a ...
2
votes
1answer
527 views

What does the set {n | n is an integer and n = n + 1} represent?

I am reading Michael Sipser's book Introduction to the Theory of Computation, which mentions the set $$S = \{ n \mid \text{$n$ is an integer and $n = n + 1$}\}.$$ This doesn't make any sense to me. I ...
0
votes
1answer
26 views

Hadoop MapReduce Word Counting Example [on hold]

In an example of the application of MapReduce provided by University of Utah, it says that Map() function emits <"hello", 1> every time it sees hello where the reduce function counts the number ...
0
votes
0answers
15 views

Processing Image - substraction by once color [on hold]

I think here somebody know about processing image, question is for experts. I have this first task of processing image, so i am noob. Mode alpha is allowed. How to calculate programically (I pref ...
2
votes
1answer
26 views

Second order function formalization

I need to work on a optimizer for a language whose operator are second order functions. They are the well known ones filter, map, reduce, fold, foreach etc. etc. I need to formalize as much as ...
2
votes
1answer
34 views

An infinite language with no infinite RE or co-RE subsets?

Are there any languages that are infinite (that is, they contain infinitely many strings) but which do not have any infinite subsets that are RE or co-RE languages? This seems related to simple sets, ...
1
vote
1answer
21 views

Why would this Semidefinite Program be Dual Infeasible?

My semidefinite program amounts to two constraints, $L_1 = 0$ and $L_2 = 0$ where $L_i$ are linear functions of my variables $x_{ij}$ with the additional constraint that the $x_{ij}$ matrix is ...
1
vote
1answer
39 views

Dynamic Programming for finding shortest alternating paths between all pairs of vertices in a graph

I'm learning Dynamic Programming (By myself) and in the textbook there is this question: Given two undirected graphs $G_1=(V,E_1)$ and $G_2=(V,E_2)$ over the same set of Vertices $V$ and a weight ...
0
votes
0answers
16 views

A* search.How it works and its algorithms in artificial intelligence [on hold]

how does the A* search work with an illustration of a graph?
-1
votes
0answers
26 views

Parallel CREW algoritm for sorting n numbers between 0 and logn-1

We are given n integers in the range [0,..,log(n)-1]. How can we sort the numbers? The algorithm doesn't have to be work-efficient.
0
votes
1answer
37 views

Some questions about NP / coNP / CSP

I need help with the following mock exam questions. True or false? 1.) If a non-trivial $(\neq \emptyset, \Sigma^*)$ finite set is NP-complete, then $P = NP$. True. Every finite set is in $P$ and ...
3
votes
2answers
122 views

Free and bound variables

I am familiar with free and bound variables theory , but while learning I somewhere saw this lambda expression ((lambda var ((fn1 var) & (fn2 var))) argument) From what I have learned it ...
-1
votes
0answers
8 views

Calculating The Average of a Value Over a Month Java [on hold]

I am working on a project right now that is having me calculate monthly interest on a bank account. The way the interest is supposed to be calculated is as follows: Use the daily average to calculate ...
-1
votes
0answers
13 views

Graphical Linked List Java [on hold]

The question is as follows: Write a method draw to display a linked list graphically. Draw each element of the list as a box, and indicate the links with arrows. Please use this as a reference if ...
1
vote
2answers
26 views

Round robin tournament scheduling using divide and conquer

I want to scheduling $n$ teams using divide and conquer method for $n \in \mathbb{N}$.My approach is that if $n$ is even divide it to to group $\frac{n}{2}$ and $\frac{n}{2}$ but if $n$ is odd, add ...
-3
votes
0answers
7 views

How to Assign a letter grade to an array and If condition [migrated]

Write a program that reads 10 student scores, gets the best score, and then assign grades based on the following scheme: Grade is A if score is >= best – 10; Grade is B if score is >= best – 20; ...
1
vote
1answer
174 views

Show there exists a turing machine with the following properties

I'm struggling to understand a question I've been given. The question asks: Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning values to the ...
2
votes
2answers
449 views

Turing Machine Decidable: What right does the definition have to say what's not in language L?

I'm having trouble understanding the definition of Turing Decidable. The definition goes something like this: TM M decides language L iff the strings in L put M into the Accept state and the ...
3
votes
1answer
61 views

Is there any algorithm can solve the following equations efficiently?

$$ x_1 + x_2 + \cdots +x_n = c_1 $$ $$ \frac{x_1^2}{2} + \frac{x_2^2}{2} + \cdots +\frac{x_n^2}{2} = c_2 $$ $$ \cdots $$ $$ \frac{x_1^n}{n!} + \frac{x_2^n}{n!} + \cdots +\frac{x_n^n}{n!} = c_n $$ ...
2
votes
0answers
35 views
+50

Inverting ranges with a binary indexed tree

I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows: You are given a series of commands that operate on an array initially all zeroes. ...
1
vote
0answers
17 views

Information content of computational problems

The notion of low information content is used to describe sparse sets and tally sets in complexity theory. Such sets can not be $NP$-complete unless $P=NP$. I am not aware of a formal ...
0
votes
1answer
26 views

Single Source Shortest Path: What does the weights on the vertex and edges tell you?

In MIT's open courseware (http://courses.csail.mit.edu/6.006/spring11/lectures/lec15.pdf), I do not see how computing a set of numbers on the edge and the vertex will produce the shortest path. ...
2
votes
0answers
23 views

Understanding a paper on polynomial recursion in all finite types

So I wasn't sure weather or not this counted as "research level" or not but I figured it wasn't so I decided to post it here. There is a paper by S. Bellantoni et al. called "Higher Type Recursion, ...
0
votes
0answers
11 views

bloom filter in high load/concurrency environment?

"I was asked this question in an interview, How to design a bloom filter to reduce cache access in a high load and concurrency environment. I know how bloom filter works but try to understand how high ...
5
votes
1answer
32 views

What is the practical relevance of textbook mutual exclusion algorithms?

There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is ...
-2
votes
1answer
35 views

How to write CFG for languages [duplicate]

How do you write the CFG for the following language: {ax by c ax+y} Is there some formula or rules I need to follow? An explanation will be so appreciated. What I tried is: First I broke ax+y into ...
1
vote
1answer
52 views

Can a solvable problem be encoded in a recursively enumerable language?

Imagine I have a turing machine that can decide on a specific problem using a language. My question is that that problem (that can be decided by a TM M, with language L) can be encoded in a new ...

15 30 50 per page