# All Questions

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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 ...
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: • ...
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 ...
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.
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 ...
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 ...
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 ...
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) ...
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. ...
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 ...
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).
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
20 views

### Matrix array problem

Create an algorithm named Moon. This algorithm should take a p by q matrix ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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)
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?
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?
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? ...
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 ...
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))$?
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 ...