All Questions

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

Another feasible way to implement multi-level page table?

The advantage of a multi-level page table is that we can swap the inner-level page tables to some secondary storage. If however we want quick access to the whole address space, we have to keep all ...
0
votes
0answers
23 views

Dangling Else Ambiguous Grammar

How is the following grammar ambiguous stmt -> if expr then stmt | matched_stmt matched_stmt -> if expr then matched_stmt else stmt | terminal
0
votes
1answer
124 views

If I have an MST, and I add any edge to create a cycle, will removing the heaviest edge from that cycle result in an MST? [duplicate]

Let's say that I have an MST, $T$. I pick an edge not in $T$ and change its weight, and add it to $T$ to create a cycle. Will removing the heaviest edge from that cycle result in an MST? MST means ...
0
votes
0answers
16 views

Given a p.c. function $f(x,y)$ find a p.r. function $g(u,v)$ s.t. $\Phi_{g(u,v)}(x)=f(\Phi_u(x),\Phi_v(x))$

Since $f$ is p.c. we know there's a program $\mathscr{P}$ that computes it. Let $w=\#(\mathscr{P})$. We have: $$f(\Phi_u(x),\Phi_v(x))=\Phi(\Phi(x,u),\Phi(x,v),w)$$ But the left hand side is a ...
0
votes
0answers
10 views

Circuit : Switching function. Can I ignore RESET and CLOCK for the functions?

So if I have to state any function like state transition function or switching function can I ignore CLOCK and RESETS?
0
votes
0answers
101 views

Strings that do not contain 11 as a substring

Today I had a couple of formal language lectures. The Instructor wrote a regular expression for the alphabet $\{0,1\}$ which does not include any string which includes "11" as a substring. She wrote ...
0
votes
1answer
51 views

How do I replace a D Flip Flop with a JK Flip Flop

Hello I have this circuit with this I want to learn about Mealey and Moore. Is this a Mealy Automata? I would say yes because of the upper LED depends on the variables I got. Otherwise isn't the ...
0
votes
0answers
34 views

What unusual property does this finite automata yield?

I'm asked to construct a finite automata for a given task. The Automata should accept the values zero or one. In the starting ...
0
votes
0answers
19 views

Internal & external fragmentation

Given five memory partitions 200kB, 600kB, 250kB, 450kB and 500kB which are fixed and in order. processes of 212kB, 517kB, 115kB and 430kB in order. In First-Fit order 212 kB --> 600 kB partition (...
0
votes
2answers
51 views

Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work. ...
0
votes
0answers
14 views

Weights vs Training ML

The weights of Machine Learning models are learned during the training process. Why is said that the higher values of weights leads to the overfitting of the model? Why is it necessary to have low ...
0
votes
0answers
12 views

working set bits in working set approximation

I am looking at the example pdf from Cornell found here: https://www.cs.cornell.edu/courses/cs4410/2016su/slides/lecture13.pdf Also reading OS Concepts 10e Chapter 10 but it does not go into detail. ...
0
votes
0answers
16 views

Is it possible to implement iterative pre/in/post-order traversal with only one stack?

All iterative algorithms I've seen for pre-order, in-order, and post-order traversals of trees have used two stacks. Is it possible to do it with one? I've been thinking about it for ever, I haven't ...
0
votes
0answers
30 views

Is this correct transformation of a grammar to one without left recursion?

So the last few days I am writing a compiler for a subset of C language by given grammar for a class at university. I encountered this problem and then I realized I need to remove left-recursion in my ...
0
votes
1answer
30 views

Clustering algorithm with specific cluster grouping areas

I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its ...
0
votes
1answer
212 views

Sorting strings using Counting Sort in O(n), where n is the total number of characters in all the strings

Suppose, you are given an array of strings of different lengths, but the total number of characters over all the strings is n. Describe an algorithm using Counting Sort to sort the strings in ...
0
votes
1answer
40 views

pseudocode to split number value to array of numbers

How to write a pseudocode to split a number value to array of numbers? Let's say the number value is 12345. I need to convert it into [1,2,3,4,5].
0
votes
0answers
18 views

Is DHAMPATH downward self-reducible?

DHAMPATH is the set of all the directed graphs which have a hamiltonian path. It's a well known NP-complete problem. I know the proof of SAT's downward self-reducibility. Arora-Barak says Cook-Levin'...
0
votes
1answer
71 views

What does {a,b}* for DFA's mean?

For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has? For example a DFA that accepts $\{w \in \{a,...
0
votes
0answers
11 views

Detect a class of a grammar having its DSL AST

I have a grammar for some language written in some DSL for writing grammars, and this DSL implements EBNF. I have an AST for the description of a grammar in the DSL. How can I detect the minimal class ...
0
votes
0answers
19 views

Google's TPU peak performance

Google's TPUv1 comprise 256x256 MACs and runs at a frequency of 700MHz. Therefore, the peak performance is $$ (256\times256)\cdot 700 \text{MHz} = 46 \text{TOPS/s}. $$ Yet, everywhere they mention ...
0
votes
1answer
55 views

Can a 32-bit processor work with a 64-bit size word?

In a 32-bit byte addressable memory system, each "row" has 4 bytes and each byte has a 32-bit address. My question is: can I read and/or write word of length 64 bits from/to memory? In other terms, ...
0
votes
0answers
21 views

How do I know which node to do rotation on?

I'm wondering which node do I perform a rotation for on an AVL tree? I think in a single rotation it is always the grandparent of the node causing the imbalance (which could either be the root node ...
0
votes
0answers
31 views

Need help in understanding these relational algebra queries

I just finished reading about operators in relational algebra and tried to solve this problem. But I dont even understand what the first statement is doing. From what I know, $π$ (project) is a unary ...
0
votes
1answer
19 views

Pagination of results from different sources merged by a unified scoring function

Assume a Hotel reservation scenario, given $m$ ranked lists of attribute values such as distance, price, amenities (normalized between $0$ and $1$), and a unifying linear score function $F(\cdot)=\...
0
votes
1answer
49 views

Understanding how convolution of images work in cnn

I'd like to understand convolutional neural network. Consider this quote from Stanford CS notes on Convolutional Neural Networks for Visual Recognition (CNNs/ConvNets): Example Architecture: ...
0
votes
0answers
22 views

Why does my EM algorithm not converge?

Any ideas why my likelihood probability for this EM algorithm doesn't converge (have slope of 0) to "find" the three clusters? I've tried increasing the iterations, which makes the slope nearly ...
0
votes
0answers
36 views

Graham 1966 Minimum makespan scheduling

I am trying to understand how Graham's 1966 makespan algorithm results in 2-approximation. I have searched in google and I have found files, and videos on youtube about makespan scheduling, but again ...
0
votes
0answers
42 views

Binary Search Complexity

I was reading an article about Binary Search on one of the websites on the internet that someone had linked, can't find the link anymore, but this really is bothering me, and I think I am missing ...
0
votes
1answer
45 views

Runtime Calculation Sort-Algortihm

I'm really struggling with the following exercise and I would really appreciate your help: I have to calculate the expected runtime of a sort Algorithm with the following variants: ...
0
votes
0answers
21 views

64 byte cache block and memory overhead for cachline with 7 states (3 bits)

I came across some lecture notes of a professor about memory consistency and models. There is an example about memory overhead: The cache line has 7 states (3 bits): unowned, shared, exclusive, ...
0
votes
0answers
23 views

Normalizing the Central Difference Method

How could I normalize the 2nd order central difference method? The original function is F(A,B,C,D) and only one variable is varied at a time. ie $F'' = \frac{F(A+\Delta A,B,C,D) - 2\times F(A,B,C,D) +...
0
votes
1answer
138 views

Max no. of keys of B-Tree of height h

I am reading about B-Tree through CLRS. One of the exercise problem is to express maximum number of keys in a BTree of height $h$ and minimum degree $t$. Properties of BTree of $t$: $t\ge 2$ Min. no ...
0
votes
0answers
7 views

Learning rule of hopfield network with sigmoidal activation function

I am going to build a hopfield network with continuous-valued units. In this article it is said that hopfield network units can have sigmoidal activation function (soft-limiting). If units can have ...
0
votes
0answers
202 views

Making Candies - HackerRank question - proof of optimality of a greedy approach

I stumbled across this question in HackerRank: Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a ...
0
votes
0answers
30 views

Formalizing “dual-time” temporal logic

I am interested in modeling a discrete temporal logic based on music, where there are two metrics of time, beat and seconds, (call them B and S). The constraints on what constitutes a syntactically ...
0
votes
0answers
23 views

Cover marked squares with rectangles with optimal tradeoff

I'm trying to solve this problem where I have to cover all the squares in a N x N grid with rectangles with a tradeoff between cost and computation. These are the constraints: Fields are rectangular, ...
0
votes
0answers
25 views

How can I efficiently find out if X is in any of N ranges of L-R numbers?

This is part of a bigger problem, which is to find out if point XYZ exists in any of n ...
0
votes
0answers
24 views

Johnson shortest path work for undirected graphs?

Does Johnson's shortest path algorithm works for Undirected graphs? All examples I am seeing with Johnson algorithm use directed graphs, but nobody is clear about what kind of graph was it designed ...
0
votes
0answers
42 views

What can be said about complexity class of a problem if there exist a pseudo-polynomial verification algorithm?

Let X be a problem for which pseudo-polynomial algorithm time for verification of solution exists. What can be said about complexity of problem X? Can X belong to NP-hard class?
0
votes
1answer
42 views

Tournament Scheduling Problem

I am trying to design an algorithm to compute the solution to this problem. Given a list of n tournaments with a name, start_date, end_date, latitude and longitude, find the list of p tournaments in ...
0
votes
0answers
25 views

is the set of decidable language the same as the set of computable functions?

is the set of decidable languages the same as the set of computable functions? As well as the complement: is the set of undecidable languages the same as the set of uncomputable functions? I feel ...
0
votes
0answers
14 views

how does the set of uncomputable functions relate to the set of non-halting programs?

How does the set of uncomputable functions / undecidable languages relate to the set of non-halting programs? underlying: how do programs relate to functions?
0
votes
1answer
40 views

Does Dekkers solutions to critical section problem ensure progress?

I was reading concurrency control section from Operating Systems book by William Stallings. In this book, he gives three attempts by Dekker to give solution to critical section problem: Attempt 1 <...
0
votes
1answer
123 views

Determine minimum and maximum number of leaves on a complete tree

I want to determine the minimum and maximum number of leaves of a complete tree(not necessarily a binary tree) of height $h$. I already know how to find minimum($h+1$) and maximum($2^{h+1}-1$) number ...
0
votes
1answer
52 views

How big is the capacity of a standard memory cell that the pointer is linking to?

Often programming language lectures and references have an illustration of computer memory as an array composed of individual cells. Each cell has an address, which is effectively the pointer and can ...
0
votes
1answer
21 views

Confused on Variational AutoEncoder

I'm a bit confused on how Variational Autoencoders are trained. In particular I'm confused on how the latent variable is generated for each input. My questions are as follows: When running ...
0
votes
0answers
24 views

Spliting strings into groups of similar strings

I would like to group a list of strings into groups of strings differing by max 1 character: For instance, given: [John, Alibaba, Johny, Alidaba, Mary] I would ...
0
votes
0answers
44 views

What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?

It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?
0
votes
0answers
43 views

Segmenting a cat's side profile and plotting a line on the edges

My goal is to segment the side profile of a cats head and plot a line on the edges of the cat's face, The cats will have different backgrounds, colour and quality, and the feature (cat's face edges) ...

15 30 50 per page
1
635 636
637
638 639
735