All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
5 views

What is the Time complexity of $\sum_{i=1}^n 1+\lfloor\log_2 n\rfloor$

What is the time complexity of $$\sum_{i=1}^n 1+\lfloor\log_2 n\rfloor$$ and how do you calculate it?
0
votes
0answers
6 views

What are some uses of the Thue-Morse sequence in computer science?

Note: I come from a mathematics background. The Thue-Morse sequence $t_n$ is a binary sequence that takes the value $0$ at the positive integer $n$ if the number of $1$s in its binary expansion is ...
0
votes
0answers
16 views

Prove that for any non empty Σ show that there exists language that are not recursively enumerable

Using diagonalisation method, prove that for any non empty Σ show that there exists language that are not recursively enumerable.
0
votes
0answers
7 views

Evolving graph rewritings between trees (representing JSON) and graphs (representing relational database schemas)

I have in input different, say 100, types of trees with labeled nodes (representing JSON files). I need to transform the information contained in the trees into graphs with labeled nodes (representing ...
0
votes
0answers
9 views

Minimum-cut with balanced and limited number of nodes in each partition: Does this have an efficient solution or even a name?

I'd like to remove the minimum number of edges from an undirected unweighted graph to partition the nodes into an arbitrary number of connected components $S_1$, $S_2$,$S_3$,... $S_k$ while maximizing ...
0
votes
0answers
11 views

PTAS for Multiple Knapsack with Uniform Capacities, fixed number of Knapsacks

Consider the following problem: We are given a collection of $n$ items $I = \{1,...n\}$, each item has a size $0 < s_i \le 1 $ and a profit $ p_i > 0 $. There are $m$ (a fixed number) of unit-...
0
votes
1answer
13 views

AI - Heuristic method

I am trying to code a n puzzle solver. I am currently trying to think of heuristics for A* search. The heuristics I have currently came up with are Manhattan distance, max swap and Hamming distance. ...
0
votes
0answers
10 views

number guessing (java) in google kick start [closed]

Below is the code which is running fine locally but when i submit the code it gives runtime error. import java.util.Scanner; ...
0
votes
0answers
11 views

Comparison of feature importance values in logistic regression and random forest in scikitlearn [closed]

I am trying to rank the features for binary classification, based on their importance using an ensemble method by combining the feature importances estimated by random forest and logistic regression. ...
0
votes
0answers
17 views

Prove that exists PARITYn fuction with size O(n^2)

Have to find Boolean circuit formula that solves PARITYn problem with complexity O(n^2)? (Function PARITYn(x1, . . . , xn) is equal to 1 if and only if the number of variables x1, . . . , xn equal ...
0
votes
0answers
17 views

From P=PP to FP=#P

Do we know $P=PP$ implies $FP=\#P$ or vice versa? If not what prevents such a result? Any references will be useful.
0
votes
1answer
18 views

practise resources for basic sorting

I have to prepare for a midterm and I am looking for a resource where I can practise the three basic sorting algorithms insertion sort, bubble sort and selection sort a little. Last year they had to ...
0
votes
0answers
18 views

Quick question about max heap

Suppose that we have a max heap and that it contains duplicate values .Is it always true that nodes with same value are adjacent(neighbors)?I think it is true because if there was any other node being ...
0
votes
0answers
15 views

Question about asymptotic analysis comparing two functions

I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^2 \\ g(n) = n^{2/3}$$ Show that $f(n) = O(g(n))$, or $f(n) = \Omega(g(n))$ and comment if $f(n) = \...
2
votes
1answer
52 views

“Searching and sorting” algorithm to find the natural logarithim of a number?

Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm ...
0
votes
1answer
16 views

Computing the minimum distance between each pain of points

I am trying to read an algorithm for computing minimum distance between each pair of points from the book: Algorithm Design Algorithm Design It considers the points in a line. If the points are in ...
0
votes
0answers
7 views

MIPS Assembly Program to find floor(log_2 x) recursively [closed]

I need help writing a MIPS assembly program that finds the floor(log2x) recursively, where x is input from the user. If the input is less than 1, have the program exit.
-1
votes
0answers
10 views

how to set up multiple computers full disk encryption? [migrated]

I want to set up my company's laptops in a way that all files created on these laptops can only read by these laptops. If it is copy to a usb then that file is only readable when plug that USB in a ...
-2
votes
0answers
11 views

probability of error for a Bayesian classifier with P(x | c 1 ) = P(x | c 2 ) and P(c 1 ) = P(c 2 )

What is the probability of error for a Bayesian classifier with P(x | c 1 ) = P(x | c 2 ) and P(c 1 ) = P(c 2 )? Why? Does this make sense? if so, can anyone explain this clearly?
-4
votes
0answers
26 views

How bitly.com to bit.ly works

I have a question about how bitly.com to bit.ly work. My questions is not about shorting url from a long url to short one. Like the service Bitly provide. Suppose I have website with the domain name ...
0
votes
1answer
21 views

Ascii characters in C language [closed]

Decimal Character ​ 48 0 49 1 50 2 51 3 52 4 53 5 54 6 55 7 56 8 57 9 these character are the present in ascii ...
4
votes
1answer
57 views

How come correctness proofs aren't tautological?

Consider the following function on binary trees, which is supposed to tell whether a given int is a member of a binary tree t: <...
0
votes
0answers
16 views

Runtime of tree sort algorithm confusion

Can anyone explain to me why the average runtime complexity of the program here - https://www.geeksforgeeks.org/tree-sort/ - is nlogn and not n^2logn? Similarly, why is the worst case time complexity ...
1
vote
2answers
24 views

Quadratic Probing Infinite Loop?

I understand the definition of Load Factor and how Quadratic Probing works. But what happens in the case where quadratic probing cannot find an empty slot for a new element? According to https://en....
0
votes
0answers
18 views

Is it possible to create an age estimation by face program using deeplearning with my laptop?

My computer specs: Processor type Intel(R) Core(TM) i7-8550U CPU @1.80GHz 1.99GHz Installed RAM 8.00 GB System Type 64 bit operating system i also have Intel UHD graphics 620. I am starting an ...
0
votes
1answer
18 views

Pseudocode for a searching tree

I want to describe my search tree in an algorithm and describe how each level of the tree is created. But I cannot find good examples to help me express how to write it in an elegant way. Please if ...
1
vote
0answers
21 views

Algorithm to minimize the damage received from the monsters [duplicate]

I have been puzzled by the following question on an exam for quite a while: given a set of monsters with their health and attack damage (per second), design an algorithm that minimizes your overall ...
0
votes
0answers
13 views

Wireless communication

Is wireless communication a part of computer science ? If anyone wanna pursue Phd in wireless communication, can you recommend some good universities in US ?
0
votes
1answer
20 views

Representing a sentence using propositional logic

I am confused regarding a propositional logic representation of a sentence. Please note that this sentence is not realistic: "A person who is male (M) is smart (S) if he is tall (T), but otherwise ...
1
vote
0answers
19 views

relationship between binary numbers and binomial heaps

I understand that a binomial heap can be represented as binary numbers according to the degree of each tree but what exactly is the relationship between inserting a new node into the binomial heap and ...
0
votes
0answers
20 views

Compiler design: How are the initialize conditions for data-flow problems set?

Consider a typical data-flow problem, for example, reaching definitions or available expressions. I am struggling to understand how $IN$ and $OUT$ of the basic blocks are initialized. For example, ...
0
votes
0answers
15 views

Android apps IPC during navigation of activity

During navigation of activities in an Android app by clicking back button, the current activity is paused, the previous one is restarted and resumed and the former is stopped. How does activity ...
0
votes
1answer
58 views

Travelling Salesman Problem Easy Algorithms

I'm looking for a easier algorithm to implement to solve the travelling salesman problem (in javascript). Unluckily all of the ones i found are really hard to understand/ to implement. The ones i ...
0
votes
0answers
24 views

Handling left recursion without left factoring with stateful parser combinators

Consider the language of simple types $$ T \mapsto B \ \mid\ T \rightarrow T \\ B \mapsto \text{Bool} \ \mid\ \text{Int} $$ where $\mapsto$ stands for productions to avoid ambiguity with the ...
0
votes
0answers
24 views

Scheduling jobs on a single machine - minimising the weighted sum of completion times

Consider the following problem: there are $n$ jobs $\{1,...,n\}$, each has a processing time, $p_i$, a weight $w_i$, and an arriving time $r_i$. The goal is to minimise the weighted sum of completion ...
0
votes
1answer
40 views

Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing

I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, ...
0
votes
0answers
15 views

Proof of Small-Step Semantics property

I'm trying to solve the exercise 2.20 from the book "Semantics with Applications" by Nielson & Nielson. The request is the following: Exercise 2.20 Suppose that (S1;S2,s) =>* (S2,s'). Show that ...
-2
votes
0answers
17 views

Hash Table Testing in C++ [closed]

I'm attempting to learn C++ right now, but I am struggling on this project from here: https://ucsb-cs32.github.io/f19/lab/lab04a/ I'm desperate for help right now, as I have no idea how to do it. If ...
-3
votes
1answer
55 views

Proving that a sum of n zeros are 0

Define a function $\text{zeros} \colon \textsf{nat} \to \textsf{natlist}$ that, given a natural $n$, produces a list of $n$ zeroes. You can use either Coq notation or, if you're comfortable with it, ...
4
votes
1answer
103 views

Interview Question with Arrays and Consecutive Subintervals

I recently came across this question and honestly am pretty unsure of how to solve it, or even begin to develop an algorithm to properly solve it.. The question is: "An array of $n$ integers is ...
0
votes
2answers
76 views

IS there a consensus on the definition of a computer program in CS literature and if so, what is it?

The following is what I came up with from my synthetic prior research but I might be wrong. I understand it is possible to reduce any computer "program", in a maximal reduction(?), to these features: ...
0
votes
0answers
14 views

STL Container Methods in GDB [closed]

Suppose I have a struct 'S' with a method called 'name()'. Another variable 'M' is a set of struct type elements. In GDB, I wish to get a handle on the elements of 'M' so I can call 'name()' method on ...
0
votes
0answers
10 views

Decision tree selection by error rate (What does this mean?)

I am asked to select a attribute based on it's error rate Could someone please explain me this? Let's say I have this data for example reasons For a attribut 3 Yes that classifies as + 1 Yes ...
0
votes
0answers
9 views

Finding if the x and y coordinate is within a view is enclosed by two intersecting rectangles, in java [closed]

Say I have this view with two subviews A and B, A and B has a color property mColor, I want a function in the parent view that has this signature: ...
0
votes
1answer
21 views

How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$

Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s. Also, I have a hint HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
-1
votes
1answer
43 views

Constructing an NFA for a language defined over $\Sigma = \{0, 1\}$

The language is defined as $$L = \{0^n10^m10^q \mid n,m,q \in \mathbb{N}, q \equiv nm \mod 5\}.$$ Can someone help me get started on this question? I don't know what part of the question I should do ...
-1
votes
1answer
25 views

Grammar for the following language: L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$$ N^{+}$ $\land$ m + k $\geq$ n}

I'm trying to create a grammar (having the highest type) for the language: L = {$a^{k}$$b^{n}$$a^{m}$ : m,n,k $\in$ $N^{+}$ $\land$ m +k $\geq$ n} I'm not finding any good approach for it. Hints ...
0
votes
0answers
8 views

The accounting Method analysis for table expansion by tripleling instead of doubling an array

If we double the array every time we get the amortized cost of 3n or 3$ if you prefer. I was wondering what would it be if we tripled the array size instead of doubling it. The rational between the ...
1
vote
1answer
23 views

How are “Problem Complexity” and “Solution Complexity” different?

I am in an algorithms course, and my professor keeps specifying "we are talking about Problem complexity here, not Solution complexity". I would like to gain an intuitive understanding of the ...
0
votes
0answers
20 views

Prove the equivalence between regular expressions (cb*c+cb*b)* and (cc)*+(cc)*(cb)(b+c)*

I need to prove the equivalence of the following regular expressions: (cb*c+cb*b)* (cc)*+(cc)*(cb)(b+c)* using the following equivalence rules: • (1) (E + F) + G = E + (F + G) • (2) E + F = F + E ...

15 30 50 per page
1 2 3 4 5 690