## Threading hair while on pthreads

Due to multicore and hyperthreaded processors, threading is now a common task programmers need to perform whenever possible. Quite often we see ready template code online or even C++ library based implementations that makes it easy or us to cut & paste, make few changes and unleash on to market after several testings...

This is fairly common these days that hardly any programmer can escape due to higher productivity requiremets !

We we do threaded programming, it is sure to have concurrent processing. So we need some kind of synchronizations to make sure we don't corrupt some shared data. **Now the question is how to comeup with proper sync mechanism: mutex, spin-lock etc...**

Here is an example of such application of threading -

Q:* Print a sequence like: 010203040506070809010011012013 .... using threaded routines. One can do it in one thread, but here we need to exercise threading.*

It's necessary to see how minimal locking we can do. To do that it is good to look at the state diagram. For example if a thread just print zero, then it has to let other threads to print non-zero.

Now one more requirement imposed is: *Use three threads : One prints zeros, another one prints even numbers, yet another prints odd numbers.*

*Codition to analyize:: When can zero thread print ? -- It can print after any non-zero got print. When can an even nunber be printed:: - When when zero thd. is not allowed to print, and last non-zero thread was odd number thread.*

*Now here is an implementation. It is instructive, if you use paper pencil first...*

//

// main.c

// OS

//

// Created by Admin on 5/26/18.

// Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

#include <stdio.h>

#include "OS.h"

int main(int argc, const char * argv[]) {

// insert code here...

testOddEvenPrint();

printf("\nHello, World!\n");

return 0;

}

//

// thd.c

// OS

//

// Created by Admin on 5/26/18.

// Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

#include <stdbool.h>

#include<stdio.h>

#include<string.h>

#include<pthread.h>

#include<stdlib.h>

#include<unistd.h>

/*

* Create a multi threaded ( 3 thd ) that prints 0102030405060708....

* Need mutual exclusion

*/

//pthread_mutex_t mutx;

_Bool IsZero = true;

_Bool IsOddNo = true;

void AC( pthread_mutex_t *L)

{

// -- waitable may block

pthread_mutex_lock(L);

return;

}

void RL( pthread_mutex_t *L)

{

pthread_mutex_unlock(L);

return;

}

void *printzero( void *Lock)

{

pthread_mutex_t* L = (pthread_mutex_t*)Lock;

for (int i = 0; i < 20; i++){

AC ( L );

if ( IsZero ){

printf("%d", 0);

IsZero = false;

}

RL(L);

}

return NULL;

}

void *printOdd( void *Lock )

{

static int OddNo = 1;

pthread_mutex_t* L = (pthread_mutex_t*)Lock;

for (int i = 0; i < 10; i++){

AC ( L );

if ( !IsZero && IsOddNo){

printf("%d", OddNo);

IsZero = true;

IsOddNo = false;

OddNo += 2;

}

RL(L);

}

return NULL;

}

void *printEven( void *Lock )

{

static int EvenNo = 2;

pthread_mutex_t* L = (pthread_mutex_t*)Lock;

for (int i = 0; i < 10; i++){

AC ( L );

if ( !IsZero && !IsOddNo){

printf("%d", EvenNo);

IsZero = true;

IsOddNo = true;

EvenNo += 2;

}

RL(L);

}

return NULL;

}

void

testOddEvenPrint()

{

int err;

pthread_t tid0thd, tidOddthd, tidEventhd;

pthread_mutex_t mutx;

if (pthread_mutex_init(&mutx, NULL) != 0)

{

printf("\n mutex init failed\n");

return ;

}

err = pthread_create(&tid0thd, NULL, &printzero, &mutx);

if (err != 0){

printf("\ncan't create thread printzero :[%s]", strerror(err));

return ;

}

err = pthread_create(&tidOddthd, NULL, &printOdd, &mutx);

if (err != 0){

printf("\ncan't create thread printzero :[%s]", strerror(err));

return ;

}

err = pthread_create(&tidEventhd, NULL, &printEven, &mutx);

if (err != 0){

printf("\ncan't create thread printzero :[%s]", strerror(err));

return ;

}

pthread_join(tid0thd, NULL);

pthread_join(tidOddthd, NULL);

pthread_join(tidEventhd, NULL);

pthread_mutex_destroy(&mutx);

return;

}

## DP 5 - PickPocketer

Assume two pick pocketers **A**, and **B**, are settling on their end of the day earnings. The rule is that they will put all their picks on to a table. Then they will pick one coin at a time from either end of the line ( the coins are put on a line). Further assume that the number of coins is even, so both of them can have same number of coins. Fair game, as opposed to lot of things in life :-)

**How should they go about picking in tern from either end of line to maxmize gain?**

**Example worth 1000 brainstorm !**

**S = { 6, 9, 1, 2, 16, 8 }. **

**Greedy approach: Both A, and B will pick the larger of the coins at two ends.**

A -> 8, B-> ... complete the process and see if A wins or B. You will see even though A has the first shot at it, A will loose. *So greedy approach does not work. So what should be the strategy ? -- Think ...*

**The approach should be to minimize opponents next gain, rather than maximize your own gain. What an envy ! First approach is called Greedy, and the second approach is Strategy.**

So at each turn, one would look at the difference between 2 left end coins and 2 right end coins and maximize the difference. In other words, you pick the greater difference.

Look at **Max { ( a[i] - a[i+1] ), ( a[N] - A[N-1] ) }, then pick either A[i] or A[N]**

Time to find a functional equation !

## DP 5 - TicketMaster

Suppose there is a train system that goes from station 1 to destination station N. Name the stations as you wish instead of 1, 2, ... N. You are suppose to get a ticket that minimize cost to go from 1 to N. The costs of the fairs going from i to j station is given as Cij, i < j.

Based on the cost matrix C, we can see that we could draw a graph. Please try simple train system like: 3 stations, and see.

First thing we need to comeup with a functional equation. In order to arrive at N station, we have to get to some intermediate station, and from their we need one more step to get to N.

Lets F(i,j) = Minimal cost from station i to j, i < j; Then

F(i,j) = min { F(i, j-1) + C<j-1, j> ; C<i,j> }, where C<i,j> is the fair to go from Ci to Cj

Now is the time for a try ...

//

// TicketMaster.c

// DP

//

// Created by Admin on 5/10/18.

// Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

/*

* TicketMaster is usually a person who gives you ticket to your destination station from the station you are now.

*

* U R given a simple railroad with stations 1, 2, 3, ... N. U R going from station 1 to N, and between each pair of

* stations (i,j), s.t. i < j there is a cost per ticket c(i,j). How do you minimize the cost of your travel from 1 to N

* In general minimize the cost from i to j.

*

* This can be represented as Directed Acylic Graph (DAG). Try drawing a simple graph on 3 station to have the feel.

* In Algos, and in general in Math, it is essential to find the nature of the problem, categorize if possible, classify

* to a know group of problmes, finally find a pattern or two and possibly reduce it to know problem.

*

* It surely looks like shortest path problem, since length and costs are interchangeable. Also it looks like a staged

* DP problem. Once we understand this much, it is time to comeup with Functional equation for the DP or just a

* recursive formulation of the problem. NOTE: While DP problems are back-tracking in nature, recursive are bottom up

* also depends on how you look at.

* FUCTIONAL EQUATION ::

*

* Let F(i,j) = Minimal cost to travel from i to j, s.t i<j. Then

*

* F(i,j) = Min { F(i, j-1) + C(j-1, j); C(i,j) }

* i<j

*

* As you can see this is the recursive formulation !! Why? Because it is not using any intermediate calculations !!

* Can we memoize the intermediate computations ? I'm not sure though, just will have to play around with some

* concret example

*/

#include <stdio.h>

unsigned int Min ( unsigned int a, unsigned int b)

{

return ( a < b ? a : b);

}

unsigned int C[4][4] = {

{9999, 4, 6, 14},

{9999, 9999, 5, 7},

{9999, 9999, 9999, 3},

{9999, 9999, 9999, 9999}

};

unsigned int TicketMaster(unsigned i, unsigned j)

{

int highNo = 999999;

if ( i >=j){

return highNo;

}

int result = Min ( TicketMaster(i, j-1) + C[j-1][j], C[i][j]) ;

printf( "result=%d, i=%d, j=%d, C[j-1][j] = %d C[i][j]=%d\n", result, i, j, C[j-1][j], C[i][j]);

return result;

}

int main(int argc, const char * argv[])

{

unsigned int Minticketcost = TicketMaster(0, 3);

printf("Minticketcost = %d\n", Minticketcost);

return 0;

}

// --- Traces ---

**result=4, i=0, j=1, C[j-1][j] = 4 C[i][j]=4**

**result=6, i=0, j=2, C[j-1][j] = 5 C[i][j]=6**

**result=9, i=0, j=3, C[j-1][j] = 3 C[i][j]=14**

**Minticketcost = 9**

**Note that in this case it is 3 stage process. DP formulation might not be needed !!!**

## DP 4 - Breakpoint

In DP3 we talked about recursive implementation for minimal coins needed for a given change amout.

Recursive algorithm is best seen as top-down tree. Drawing that tree for small sample shows there are redundant computations of sub-problems. So we need to store intermediate solution to sub-problems.

In general, **Understanding the substructures and their relations to Original problem is the key.**

**DP problems have many classifications like: Dimensions, Stages, Deterministic vs. Non-deterministics. So understanding the structure and relate to some category is really a key insight.**

**During this process of trying and explaining DP problems and theirs' possible solutions I will try to cover as much as I could. But my main goal is to get to Stochastics Dynamic Programming.**

*Example:*

*We know shortest path in terms of distance or time is one such deterministic DP problem. None other than Bellman ( inventor of DP ) showed the solution using DP method.*

*Now lets turn around and think like ---*

* ***There is a roadway network from San Francisco, CA to Tempa,Florida. Further assume that there is a probability associated with any segment of the trip could be under construction, hence not accessible. Now the Question is how could I take the most viable route to get to the destination.**

**Another one, Suppose you expect N offers on your house on sale, and there a probablity associated with the i_th offer being the best offer. P(i) = Probability that the i_th offer is the best offer so far to accept and terminate the consideration process and H(i) = Probablity that it would be best to reject the offer to realize better gain later.**

**Above problems are some of the examples of - Stochastic Dynamic Programming. **

## DP 3

In DP 2, we saw that simple one dimensional problem could be fairly easy to get the DP functional equation, without going thru the recurrence relations first. This is because functional equation does not have too much dependencies. An example is Fibonacci number.

Here we talk about CoinChange problem which is somewhat difficult to comeup with DP functional equation right away. So it is best to get a recurrence relation and solve it first. A correct solution at first is always a good idea ! Then analyze the execution and perhaps come up with DP functional equation.

I'M NO EXPERT in DP analysis, so one step at a time.

**Problem statement:**

**Given a set of coins with infinite supplies of each denominations, like: S = {1, 5, 10, 25 }. So the set consist of pennies, nickels, dimes, and quaters.**

**Question: What is the minimal number of coins that make up to an amount of changes, say N.**

**Ex: N = 11 => {1, 10} or { 1, 5, 5}. MinNoOfCoins = 2.**

*Caution: Try to follow the DP 2 methods to come up with DP functional equations straight out and see if this could be easy or complex.*

Note that DP problems solving in most cases is to look at substructure from backtracking point of view.** **

**So the recursive definition is -**

**MinNoOfCoins(N ) = min { 1+MinNoOfCoins(N-1); 1+MinNoOfCoins(N-5); 1+ MinNoOfCoins(N-10); 1+MinNoOfCoins(N-25)}, depending on what is the last denomination being picked.**

For this recursive definition, here is the implementation ---

//

// Created by Admin on 5/6/18.

// Copyright © 2018 AdminProkash Sinha. All rights reserved.

//

#include <stdio.h>

/*

* Given a set of coins S = { 1, 5, 10, 25 } pennies, nickels, dimes, quaters

* Given N the change Amout, say 73 or 62 or 49 ...

* Find the min number of coins whose sum is N

*

* -- A straight DP functional equation may not be simple thing to do, becasue

* -- D(N ) defined as Minmum no. of coins to get changes to N, then

* -- D(N) = D(N-1) + D(N-5) + D(N-10) + D(N-25)

* --- priming the table would be hard, laborious, and confusing.

* -- So lets try the normal steps -- Find a recurrence equation.

---

Let's MinCoins(N) = min of { 1+ Minconins(N-1); 1+ Mincoins(N-5); 1 + Mincoins(N-10); +1 + Mincoins(N-25) }

*/

int Mincoins( int arr[], int Nodenomination, int N)

{

int mincoins = N ; /* the worst we can do using pennies */

if ( N <= 0) return 0;

/* array of coins from the denomination set S = { 1, 5, 10, 25} for example */

for (int i = 0; i < Nodenomination; i ++) {

if (N == arr[i])

return 1; /* just one more coin needed */

}

for (int i = 0; i < Nodenomination; i ++) {

int numcoins;

if ( arr[i] < N) {

numcoins = 1 + Mincoins(arr, Nodenomination, N - arr[i]);

mincoins = ( mincoins < numcoins) ? mincoins : numcoins;

}

}

return mincoins;

}

int main(int argc, const char * argv[]) {

int coins_set[] = { 1, 5, 10, 25};

int MinNoOfCoins;

int Nodenomination = sizeof(coins_set)/ sizeof(coins_set[0]);

MinNoOfCoins = Mincoins(coins_set, Nodenomination, 62 /*49*/);

// insert code here...

printf("MinNoOfCoins = %d\n", MinNoOfCoins);

return 0;

}

RK: If we try to find the minimum numbers of coins for a change of 4093 cents, the above implementation could take some time.