mpis

This is a repo where I store my excercises from MPIS (Metody Probabilistyczne i Statystyka) during my III semester of Algorithmic Computer Science on the University of Science and Technology in Wrocław 2024.

Zad1

Excersise No. 1: Monte Carlo Method for Approximation.
Objective: Approximate integrals of given functions using a probabilistic Monte Carlo method.
Tasks:

• Implement and test the algorithm for three integrals and estimate π.
• Perform experiments for varying numbers of points and repetitions (e.g., 5,000 points and 50 repetitions).
• Visualize results with scatter plots of calculated values, their means, and true values for comparison.
• Ensure the use of high-quality random number generators like Mersenne Twister.

diff_approx

In this folder you'll find working C++ code. Unfortunately you have to run it seperately for every funcion (all of them are implemented, and somewhat usefully commented). After running this code you should get .txt files that work within the python code in the next directory.

monte_graph

In this folder you'll find working Python code. Unfortunately you have to run it seperately for every file (yes I didn't do it in a clever way, but it should be fairly easy to fix). After running this code you should get desired graphs.

graphs

Folder contains graphs generated by me.

Zad2

Excercise No. 2: Balls and Bins Model
Objective: Study classical probabilistic problems using simulations of throwing balls into bins.
Tasks:

• Measure outcomes like first collision, empty bins, and steps to fill all bins or double-fill all bins.
• Conduct experiments with independent repetitions for various bin counts (e.g., up to 100,000 bins).
• Analyze and visualize data using ratio-based metrics and hypothesize asymptotic behaviors.
• Explore applications like hash functions and cryptographic hashing using the birthday paradox.

balls_and_bins

In this folder you'll find working C++ code.
It prints out data into four txt files, that you can feed into python program in ball_graph

ball_graph

In this folder you'll find working Python code. Unfortunately you have to run it seperately for every file (simmiliar to the last one, it'll be reoccuring theme here). After running this code you should get desired graphs.

graphs

Folder contains graphs generated by me.

Zad3

Excercise No. 3: Advanced Probabilistic Simulations and Analysis
Objective 1 (balanced allocation): Examine how allowing each ball to choose the least-loaded urn from d uniformly random candidates affects the maximum load.
Tasks:

• Simulate the process for n balls and n urns for two scenarios:
  • d = 1 — each ball chooses a single random urn.
  • d = 2 — each ball probes two random urns and is placed in the less-loaded one (ties broken arbitrarily).
• For both cases, record the maximum load​ over multiple independent repetitions and a range of n (e.g., 10 000 … 1 000 000).
• Plot the empirical mean​ and overlay the theoretical guide curves

Objective 2 (Insertion Sort): Measure the cost of the classical INSERTIONSORT algorithm on random data.
Tasks:

• For every n∈{100,200,…,10000} generate k=50 uniformly random permutations and sort them.
• Record for each run:
  • the number of key comparisons cmp,
  • the number of key moves swaps.
• Plot
  • cmp(n) and the ratios cmp(n)/n and cmp(n)/n2,
  • swaps(n) and the ratios swaps(n)/n and swaps(n)/n2.

Objective 3 (Noisy Broadcast in a Star Network): Investigate how quickly a single central station can disseminate a message to n leaf nodes when each transmission is received independently with probability p.
Tasks:

• Simulate rounds of broadcast on a star with n leaves for two reliability levels: p = 0.5 and p = 0.1.
• For each n and p, run multiple repetitions and record the completion time​ (first round in which every leaf has the message).
• Plot individual completion times and the empirical mean as a function of n.

Balls_2

In this folder you'll find working C++ code for the Objective 1

DistortedComm

In this folder you'll find working C++ code for the Objective 2

insertsorthw

In this folder you'll find working C++ code for the Objective 3

ball_graph_zad3

In this folder you'll find working Python code to generathe graphs for Objective 1

graph_sort

In this folder you'll find working Python code to generathe graphs for Objective 2

graphs

Folder contains graphs generated by me.

Zad 4

Excercise No. 4: Inequalities & Random-Walk Objective 1 (Binomial Tail Bounds): Compare the sharpness of Markov and Chebyshev inequalities for extreme events in the symmetric binomial distribution.

Objective 2 (Simple Random Walk): Investigate how the cumulative sum of fair ±1 steps converges to the normal law.
Tasks:

• For N∈{5,10,15,20,25,30}N∈{5,10,15,20,25,30}:
  • empirically approximate the CDF of a given sum​,
  • plot histograms / step-CDFs.
• Superimpose the CDF of the normal distribution that should approximate the sum​ (CLT).
• Comment on the quality of the normal approximation as N grows.

Objective 3: Empirically examine the distribution of the fraction of time a simple random walk stays non-negative.

Objective 4 (Test PRNGs): Test Pseudo Random Number Generators according to NIST
Task:

• Using Zslotan Molnaras site test outputs of:
  • "Weak" PRNG, linear congruential generator LCG
  • "Decent" PRNG, permuted congruential generator PCG
  • Pseudo random sequence provided by the site

Markow_Czybyszew

Folder contains working Python code for the first objective (Yes, there is a typo)

Random_Walk_on_Integers

In this folder you'll find Python code for 2 and 3 objectives, along with a couple of already made graphs

NIST

Here you can find simple LCG and PCG in Python