Determine smalles possible parameter set for FPT

I am reading a book about complexity analysis and cannot find a way to solve a problem in that book. The problem is, that I do not understand how to determine the smalles possible parameters, given the runtime of an algorithm. Do I just need to insert some numbers and see if the parameters exceed n at some point? Perhaps someone can explain that to me.

An example is: $ O(p^q * n^2)$ . Now I know that by the definition of FPT, this runtime is FPT (because we have a function of the parameters times n^constant). However, what are the smallest p and q in that case?

Thank’s in advance. Cheers!

EDIT:

The exercise is: The following O(.) expressions resprent worst-case runtimes of different algorithms, where n is a measure of the input size and p, q and r are parameters (where p, q, r <= n). Which of the following running times are fpt running times? Give the smalles possible parameter set for which the rinning times are fpt (if one exists) and explain.

a) $ O(p^q * n^2)$

There are some more, but I just want to understand how to solve it and then I’ll try the rest myself again.

Taken from: Rooij, I. V., Blokpoel, M., Kwisthout, J., & Wareham, T. (2019). Fixed-Parameter Tractable Time. In Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis (p. 125). Cambridge, England: Cambridge University Press.

How to determine if a public IP address is in a datacenter or home etc

How can someone determine if a given IP range is in a datacenter or for home usage etc.? Companies like MaxMind provide lists of IPs located in hosting centers. How do they get this information? Do they simply look for specific fields in whois? or is it more involved?

If someone purchase IPs from RIPE, ARIN etc. do they provide their own location data and if it is designated for datacenter, home usage etc.?

programmatically determine if a python package needs to compile C

I am building a system that will take a list of python packages (several hundred), generate wheels if none exist, and publish said wheels to our internal artifactory. This is being done for several reasons, two biggest is speed of install, and our system runs on some off beat platforms (namely BSD).

I have the process of pulling the sdist down, thats fairly easy. My problem is once I have the sdist down and using setup.py to generate the list of primary and transitive dependencies using pipdeptree, is there a way for me to determine if the package and its dependencies are pure python or if they require C compiling? I think I have counted about 5 different methods of wrapping a C library already, but all im really looking for is something that can answer this:

def requires_platform_build(module):   if test_module(module):     'send to platform build system'   else:     'send to docker container to compile ANY wheel' 

I know this is easier said than done with test requirements and such, but im not concerned with the test packages, only the runtime packages needed.

What should I use to determine the growth rate at which files are growing in Linux? [on hold]

I want to know the size of the files that are growing abnormally in my Linux environment.

For example, I have two files, file1 and file2.

Now if I know the space occupied by file1 is growing at 1MB per minute and for file2 it is at 10MB per minute.

Now if all of a sudden there is a shoot in growth rate occupied by file1 from 1MB/min to 1000MB/min, I need to catch this.

What is the best way this can be achieved?

I also don’t know the way to calculate the initial rate at which the files are growing, what should be used to do that.

Should I be looking at this as ML problem, which learns the rate at which file is growing and catches it if it deviates from normal behavior or this can be worked out using df/du command and running some kind of cron job?

Also, the number of files can be large.

How to determine which key combo is free to assign?

I’ve already spent much more time on finding a combination that works in every app (universal).

The shortcut triggers a service for + or – brightness of my external monitor.

I tried a ridiculous ctrlaltcommandF1 and F2, but it doesn’t work in apps like finder, preview etc. It only gives an error beep. (But is it already assigned? Or its portion is assigned and gets triggered?) I haven’t found anything else since.

How do I find a free keyboard shortcut? Otherwise there’s no point in creating them.

Flutter doctor cannot execute…. to determine the version

! Doctor found issues in 4 categories. Raymonds-MacBook-Air:~ raymondfontaine$ flutter doctor -v [✓] Flutter (Channel stable, v1.5.4-hotfix.2, on Mac OS X 10.14.5 18F132, locale en-US) • Flutter version 1.5.4-hotfix.2 at /Users/raymondfontaine/Developer/flutter • Framework revision 7a4c33425d (3 weeks ago), 2019-04-29 11:05:24 -0700 • Engine revision 52c7a1e849 • Dart version 2.3.0 (build 2.3.0-dev.0.5 a1668566e5)

[!] Android toolchain – develop for Android devices (Android SDK version 28.0.3) • Android SDK at /Users/raymondfontaine/Library/Android/sdk • Android NDK location not configured (optional; useful for native profiling support) • Platform android-28, build-tools 28.0.3 • Java binary at: /usr/lib/jvm/default-java/bin/java ✗ Cannot execute /usr/lib/jvm/default-java/bin/java to determine the version

[!] iOS toolchain – develop for iOS devices (Xcode 10.2.1) • Xcode at /Applications/Xcode.app/Contents/Developer • Xcode 10.2.1, Build version 10E1001 ✗ libimobiledevice and ideviceinstaller are not installed. To install with Brew, run: brew update brew install –HEAD usbmuxd brew link usbmuxd brew install –HEAD libimobiledevice brew install ideviceinstaller ✗ ios-deploy not installed. To install: brew install ios-deploy ✗ Brew can be used to install tools for iOS device development. Download brew at https://brew.sh/.

[!] Android Studio (not installed) • Android Studio not found; download from https://developer.android.com/studio/index.html (or visit https://flutter.dev/setup/#android-setup for detailed instructions).

[!] Connected device ! No devices available

Any help would be appreciated

Is it possible to determine $M$ which maximizes the norm $\lVert f\rVert_{2}$?

Let $ p:[0,1]\rightarrow\mathbb{R}_{\geq0}$ be some continuous function whose integral over the interval $ [0,1]$ equals one. Consider as well some unknown function $ M:[0,1]\times\mathbb{R}_{\geq0}\rightarrow\mathbb{R}_{\geq0}$ and the diffeomorphism $ g:[x_{1},x_{2}]\subseteq[0,1]\rightarrow[0,1]$ . My question is: is it possible to determine $ M$ which maximizes the norm $ \lVert f\rVert_{2}$ where \begin{align*} f(x) = \frac{M(g^{-1}(x),p(g^{-1}(x)))Dg^{-1}(x)}{\displaystyle\int_{0}^{1}M(g^{-1}(x),p(g^{-1}(x)))Dg^{-1}(x)\mathrm{d}x} \end{align*}

When I am talking about $ \lVert f\rVert_{2}$ , I refer to the following expression \begin{align*} \lVert f\rVert_{2} = \sqrt{\int_{0}^{1}f^{2}(x)\mathrm{d}x} \end{align*}

Even if it is not possible, could someone tell me to which theory this problem belongs to? Any help is appreciated. Thanks in advance!

Determine if action is possible depending on many objects and notify state changes

In the game I’m developing I need to determine if an action is possible. Whether the action is possible is dependent on a number of factors spread across many objects (ActionDeterminers) in the game. These objects may or may not exist, and whether each of the objects allows the action is dynamic.

I had the idea to implement an Observer-style pattern, where these ActionDeterminers can register themselves with a Subject. When the Subject is asked IsActionPossibleEverywhere, it can then call an interface function on each of the ActionDeterminers: IsActionPossible, and then AND all of their results. Is there a name for this pattern?

The issue I’m facing is that I would also like to notify another set of objects (Observers) of changes in the result of IsActionPossibleEverywhere, using the standard Observer pattern. As far as I can tell, I have two options for this:

  1. Polling. I could simply call IsActionPossibleEverywhere in the main loop, and then notify every Observer when the the result changes from the last call. Unfortunately, the IsActionPossibleEverywhere call could potentially be non-performant (depending on each of the ActionDeterminers).

  2. Give each of the ActionDeterminers the additional responsibility of informing the Subject of when their personal IsActionPossible call might change. The Subject will then call IsActionPossibleEverywhere and inform its Observers if the result changed from the last call. This is considerably more complex and has more potential points of failure.

Please let me know if you have any other ideas for how I could implement this system. Thanks!

How to determine the distribution of Ubuntu

I want to launch an EC2 instance on AWS. I want to install Ubunto Xenial distribution. How do I know which one of these is Xenial?

I see a lot of options like:

  • Ubuntu Server 18.04 LTS (HVM), SSD Volume Type – ami-0b76c3b150c6b1423
  • Ubuntu Server 14.04 LTS (HVM), SSD Volume Type – ami-001dae151248753a2
  • Deep Learning AMI (Ubuntu) Version 23.0 – ami-0726ab58f406b644f
  • Deep Learning Base AMI (Ubuntu) Version 18.0 – ami-00c2ec90e50ed2f33
  • Ubuntu Server 16.04 LTS (HVM) with SQL Server 2017 Standard – ami-f13ff693
  • Ubuntu Server 14.04 LTS (HVM), SSD Volume Type – ami-0d21bd76bdbb39f53

Update

The reason I want Xenial is that Galera cluster is already built for xenial:

http://releases.galeracluster.com/mysql-wsrep-5.6.39-25.22/ubuntu/dists/xenial/