0
votes
0answers
4 views

Insertion sort?

So I have to trace the result of an insertion sort with the input {M,U,E,J,R,Q,X,B} and determine how many comparisons would be done in each iteration of the loop. I think I understand it but just ...
0
votes
0answers
10 views

Algorithm analysis of nested loop

so I have this code: for (int i=1; i < n; i=i*5) for (j=i; j < n; j++) sum = i+j; And I'm wondering, what's the time complexity of this for ...
0
votes
0answers
4 views

How to find maximum size user-space main memory that can be supported?

I can't figure out how to find maximum size of user space main memory. I have this data: 64-bit computer system that uses pure paging with 16KB page size, if each page table entry is 4 bytes ...
2
votes
2answers
206 views

Efficient algorithm for this optimization problem? Dynamic programming?

I've created a diagram that depicts what I'm trying to accomplish. Full-size Image In the input sequence, the nodes are as close together as possible. But I want the white nodes to be as close to ...
4
votes
0answers
17 views

Is there a complexity viewpoint of Galois' theorem?

Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a ...
1
vote
1answer
11 views

A little confusion with the Knapsack problem (a worked example)

I'm going through a worked example on the Knapsack problem: My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a ...
1
vote
0answers
6 views

Algorithm to find piecewise circular curve around object made of non-overlapping circles

Introduction I have an object which consist of loosely packed, non-overlapping circles, of radius r. Part of such an object is seen below, the object consist of the bold blue circles, and it ...
-2
votes
0answers
11 views

dependency graph for an S -attributed SDD

Show that, for an S -attributed SDD, the dependency graph of any parse tree is a DAG.
0
votes
1answer
9 views

Question about big O notation for function

I'm just starting to learn Big O Notation and I was trying to understand how this function would scale: $\frac{n(n-3)}{4}$ If the function was $n^2$, it would be quadratic, so O(n^2). However, the ...
-1
votes
0answers
5 views

Linked List With Map

Can someone help me solve these operations. I am trying to study for my test and wanted to do these as practice but I am lost and need guidance. Implement the Map ADT using a singly linked list: • ...
-1
votes
0answers
4 views

Finding Data Maxima Using Excel / MatLab / Mathematica

I'm having trouble figuring out a way to analyze some simple data. When graphed, the data I have make a somewhat sinusoidal curve. What I want to do is to find the x-values of the maximum peaks of the ...
1
vote
1answer
10 views

Reduction from 3 SAT to Monotone Exact 1 in 3 SAT

Can someone please help with a clear reduction from a 3SAT to a Monotone Exact 1 in 3 SAT. I tried searching by didn't find much.
0
votes
0answers
16 views

Main memory to cache mapping?

Currently studying for a final, need some advice for one letter in the following question: [18 marks] Consider a computer with a byte-addressable memory. A 32-bit memory address is divided as ...
2
votes
0answers
11 views

Relativization results in class separation

We know that $P\neq NP$ problem cannot be demonstrated by relativization because there exists oracle relative to which they are equal. Is there natural complexity classes that has been shown to be ...
1
vote
0answers
14 views

Hardness of a maximum contiguous subarray sum for a sparse multi-dimensional array

Suppose we have a d-dimensional array A (d > 1) where each dimension has length n. The array is given in sparse notation as input, and the number of given non-zero elements is N. We want to find a ...
0
votes
0answers
9 views

A linear temporal property that represents this (basic) execution?

A question gives me a set of atomic propositions AP = {a, b, c}and asks me to give a linear temporal property that represents all executions over AP such that: (1) ...
0
votes
1answer
13 views

Digital Logic Settle Time

I have an exam tonight and I'm reviewing my midterm exam. I got this question completely wrong, with no solution given. ...
2
votes
1answer
27 views

Are there algorithms with non-convex and non-concave computational complexity?

If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational ...
2
votes
1answer
24 views

TSP polynomial Time

How can it be proved that TSP cannot be solved in polynomial time ( Please bear that I don't have a hardcore computer science background).
0
votes
0answers
8 views

Sparse representation of a signal

I got a problem with my project. Ok for first information I would like to let you know that I'm originally not an computer science related student. In particular in this project I have to deal with ...
0
votes
0answers
8 views

Question about 'Software Transactional Memory' by Shavit and Touitou

I've been reading the paper Software Transactional Memory by Shavit and Touitou. I understand how STM works in general but I need to understand this paper as it is ...
0
votes
0answers
7 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
0
votes
0answers
8 views

Available open databases as input data for software testing

I'd like to test my searching algorithms but I have no samples. I want something meaningful (from the real word), which is easy to download and process (I want to build a graph). Most of my friends ...
-1
votes
0answers
14 views

Which is the best language to programme a webpage to play chess online? [on hold]

I just wanted to know, which is the best language to programme a webpage to play online a game very similar to chess (in which the pieces can move more freely instead of square to square). A user ...
1
vote
0answers
18 views

Oracle for an inverse function

A. Let $F$ be a monotonically increasing real function from $[0,1]$ onto $[0,1]$. Given an oracle to $F$ and a number $y$, is there a way to calculate the inverse function $F^{-1}(y)$ in a finite ...
4
votes
1answer
77 views

Find the minimum range

Given a list of numbers as L, how do you find the minimum value m such that L can be made ...
0
votes
0answers
32 views

graph algorithm to obtain all smallest largest paths

I would like to find all the best paths for the problem in this question The frog's longest Smallest Jump using a graph algorithm (note that for every set of stones there might be more than one ...
2
votes
1answer
40 views

What is the worst case running time for an algorithm that combines insertionsort and mergesort?

Suppose that we have an algorithm "combination" that uses insertionsort for $n < 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$? I was ...
0
votes
1answer
19 views

If the language $A$ is decidable and the language $B$ is recognizable, then the language $A \cap B$ is recognizable?

I am discussing with a friend the following question: If the language $A$ is decidable and the language $B$ is recognizable, Then the language $A \cap B$ is recognizable? I believe it is. My point ...
1
vote
1answer
35 views

What do we know about $NP \cap co-NP$?

What do we need about the intersection of $NP$ and $co-NP$ apart from the fact that $P$ is a subset of it? (beyond what these answers here say, What do we know about NP ∩ co-NP and its relation to ...
0
votes
1answer
9 views

std::hash and separate chaining

I'm attempting to implement my own generic hash table using separate chaining. I'm using the std::hash() method to create my hash function. I noticed in the description of std::hash() that: For two ...
2
votes
1answer
30 views

A median of an AVL. How to take advantage of the AVL?

Here is the source of my question. Given a self-balancing tree (AVL), code a method that returns the median. (Median: the numerical value separating the higher half of a data sample from ...
-1
votes
0answers
10 views

I have three text files which are 3 different classes consisting of students with 3 scores each [on hold]

Class1 = Elizabeth, 2, 7, 3 Anna, 9, 6, 4 Jenny, 8, 1, 5 Victoria, 1, 4, 6 Class2 = Rachel 7, 8, 9 Quinn 1, 2, 3 Britanny 5, 7, 5 Santana 4, 6, 2 Class3 = Toby, 2, 3, 6 Caleb, 10 ,9 ,8 Ezra, 2, 5, ...
-1
votes
0answers
26 views

Two fetch-execute cycle?

Consider an 8-bit system with 32 memory locations (numbered from 0 to 31) and 8 different instructions. Assume op code for "Load Accumulator" instruction is 710 and for "Add" instruction is 410. At ...
0
votes
0answers
20 views

Matrix array problem

Create an algorithm named Moon. This algorithm should take a p by q matrix ...
5
votes
1answer
19 views

PAC learning model definition

The probably approximately correct (PAC) learning model is defined as: A concept class $C$ is said to be PAC-learnable if there exists an algorithm $A$ and a polynomial function $poly(·,·,·,·)$ such ...
-2
votes
0answers
17 views

Decidable language properties, L1 - L2

Given two decidable languages, L1 and L2, I have to show whether or not L1 - L2 results in a decidable language. I am not sure how to proceed, I am aware of the closure properties of decidable ...
2
votes
0answers
20 views

Future register file in computer architecture

Results from the execution units are written into the future file when they complete (may be out-of-order). Upon operand fetching, you fetch from the future file and not the architectural register ...
1
vote
0answers
11 views

phrase searches and vector space model

Consider a system that indexes documents based on vector space model and a simple query, such as qwe asd. When searching we assign weights to both words ...
2
votes
1answer
39 views

If p(n) is a polynomial in n, then is 1/p(n) polynomially bounded?

This is part of a homework exercise. Given is an algorithm that errs with probability $\frac{1}{2}-\frac{1}{p(n)}$ for some polynomial in the input size $n$. I'm trying to prove that a polynomial ...
1
vote
1answer
43 views

Computer Science and Programming for a complete novice

everyone! I am going to learn mathematics in a university, but it will be rather ''pure'' math, so, I want to get some exposure to computer science on my own. The problem is, I've never tried any ...
-3
votes
0answers
17 views

mmap() system call [on hold]

I was wondering about If a thread stack is created on a memory segment that was created using the mmap() system call, according to mmap() system call. Which the following is true? - The thread stack ...
-1
votes
0answers
12 views

What is the best mechanism in cache coherence?

I read that there are three mechanisms for cache coherence Directory based Snooping Snarfing Which one is the best between with respect to CIA (confidentiality, integrity, and availability)
0
votes
1answer
35 views

Can I overcome cache coherence in coding?

I know that cache coherence is the consistency of shared resource data that ends up stored in multiple local caches. Can any programming languages handle this problem? If so, how?
0
votes
0answers
19 views

An example for a finite hypothesis class which is not PAC learnable?

I know that with a bounded loss function, every finite hypothesis class is PAC learnable. Are there examples for non PAC learnable hypothesis classes with an unbounded loss function?
-3
votes
0answers
39 views

Controversial Answers in Stack Overflow [on hold]

In stackoveflow, as far as I understand, Controversial is defined as: a)large number of upvotes and downvotes b)large number of comments c)Depends on how you define the question. Any more suggestions? ...
2
votes
1answer
37 views

A non-regular language satisfying the pumping lemma

I got a problem to solve, which is to demostrate that the language $L$, given by: $L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$ Satisfies the pumping lemma. Is not ...
3
votes
1answer
40 views

If O(f) = O(g), why also Θ(f) = Θ(g)?

How we can prove that if $O(f(x))=O(g(x))$ then $Θ(f(x))=Θ(g(x))$?
0
votes
0answers
12 views

What are the known NP-hardness or optimization results about spectrum of matrices? [on hold]

Like for symmetric $d-$regular matrices over 0/1 or 0/1/-1 what are some known optimization results about their possible spectral radius or spectral gap? [..I am calling a symmetric matrix to be ...
-1
votes
0answers
16 views

unrestricted grammar [on hold]

Im so confused to construct unrestricted grammar, do you guys have a simple explanation step by step to construct unrestricted grammar? or if you guys have any better resources to look at? please help ...

15 30 50 per page