Tag: finding

Finding the timestamps of processes implementing Lamport’s clocks

I have been asked this question, but don’t know how to go about answering it.

Three process, which are implementing Lamport’s clocks, are running and a lot of events are taking, place including some messages being sent between the processes. The arrows and circles represent in-processor events and messages being sent between process. Assume all clocks starts on 0 and the time goes from left to right. Provide the logical timestamps associated with each event.

image

To my understadning each circle will mean +1 increase in the proccess clock and the arrows means that it should add the time from where the process is from +1 to the process which receives the arrow. Is this a correct understanding of the task or am I missing something?

Finding two nontrivial functional dependencies that follow from F (but are not in F)

Given below is the set F of functional dependencies for the relational schema: 

R = {A,B,C,D,E,F,G}.  F = {AB → C,BC → D,G → F,AE → FG}

Show two nontrivial functional dependencies that follow from F:

Which is :

AB → CD

ABC → D

I don’t know how those two derived from? Could someone walk me through? thanks

Finding minimal degree for a B-Tree

We are given 44,000,000 elements. We want to store them in a B-Tree so that his height is 5 (no more than 5).
We are asked: “What is the minimal t we can choose?”

($ t$ is the minimal degree, in each vertex that is not the root we have at least $ t-1$ keys but no more than $ 2t-1$ )

We have a debate whether the minimal $ t$ for the minimal height is $ 10$ or $ 30$ :

Some calculated as so: $ 5 = \log_t(22,000,000)$
which gives us $ t \approx 29.4$ and so $ t = 30$

However then a some good questions were asked whether we know the inserting order or not, if we know then it may be $ t=10$ and if we do not it may be $ t=30$

The TA answered that while we show that we can insert all the elements under the constraints, it is valid, the height should not be more than $ 5$ . Given we know all the elements and now you create the tree, your task is to show how to build a B-Tree (the exact calculation for the minimal $ t$ )

We are stuck from here, we do not know which way is correct.
Thank you!

If a decision problem is in $P$, must finding the solution be possible in polynomial-time?

Function Problem that finds the solution

  • Given integer for $ N$ .

  • Find $ 2$ integers distinct from $ N$ . (But, less than $ N$ )

  • That have a product equal to $ N$ .

This means we must exclude integers $ 1$ and $ N$ .

An algorithm that is pseudo-polynomial

N = 10  numbers = []  for a in range(2, N):     numbers.append(a)   for j in range(length(numbers)):   if N/(numbers[j]) in numbers:    OUTPUT N/(numbers[j]) X numbers[j]    break

Output

Soltuion Verified: 5 x 2 = N and N=10

The algorithm that solves the Decision Problem

if AKS-primality(N) == False:   OUTPUT YES

Question

Since the decision problem is in $ P$ must finding a solution also be solvable in polynomial-time?

Finding all rows of 2 variables using Gaussian Elimination

Suppose I have a system of linear equations. Using Gaussian elimination, I can determine whether a solution exists, and even find a valid solution.

During the elimination, I can combine rows together, to produce new rows with different number of variables. Is there a method to find all possible rows that contain exactly 2 variables? For example, I may want to find all equalities between variables. This is equivalent to finding all rows that contain exactly 2 variables. Is it possible to do this without trying all (exponentially many) combinations of rows?

For example if I have:

Row 1: A xor B xor C = 1

Row 2: A xor B xor D = 1

I can combine row 1 and row 2 to say that C xor D = 0

If I have a large amount of rows, and they require large combinations of large rows to produce smaller rows, is it trivial or hard to find all rows of size 2? Can I do better than adding random pairs to the system and checking it still has a solution?

Issues finding other locations in the file manager of Kali 2020 Forensics mode

I am having trying to follow a homework problem for a digital forensics class. The goal is to be able to boot Kali Linux from a flashdrive in forensics mode and then mount your computer’s harddrive as read-only so that you can view and interact with it. I am struggling to confirm my harddrive’s location and the “other locations” tab in the file manager is not showing up.

For your reference here is a link to the problem I am working through (pages 4 & 5) https://drive.google.com/file/d/1keVSTAWaPASnAsirl8Mkxsbtd1WMFTek/view?usp=sharing

Any suggestions or work arounds?

Finding the maximum elements that can be made to 0 in a sequence using a operation

We have a sequence that follows a linear equation y = bx+c (b and c are known). The range of x is 1 to infinity. There is an operation named m-clear. In one m-clear operation, we can decrement 1, from at most m distinct numbers in the sequence. Now given a starting ‘x’ value, a ‘m’ value and another value named ‘k’ which represents the maximum m-clear operations that can be performed, find the maximum number of consequtive elements that can be made to zero starting from y(x) in the sequence.

Example: b = 1 c = 1 x = 7 m = 2 k = 10 Ans is 2