## Finding the timestamps of processes implementing Lamport’s clocks

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.

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?

## Finding the winning strategy on the Grundy’s game

Draw the game tree for Grundy’s game: Two players have in front of them a single pile of objects say stack of 9 pennies . The first players divides the stack in to two unequal pile , second player does the same until all piles of two or one object left . The player who plays last is a winner. Work out the winning strategy on it.

## 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

## Write an algorithm for finding the minimum element

Given array A=[31, 40, 41, 16, 41, 58,20], min algorithm returns 16. Write an algorithm for finding the minimum element.

## Finding the point with smallest x-ordinate between two given y-ordinates

Given a set of points P=p1,p2,..pn in R2 in where pi=(xi,yi),finding the point with smallest x-ordinate having y-ordinates between y1 and y2, where y1 and y2 are given as inputs. I can compare the point with other points which gives me an O(n) time algorithm ? Can this be improved any further ?