Math

NP-complete Problems

Posted on Updated on

NP-complete problem, any of a class of computational problems for which no efficient solution algorithm has been found. Many significant computer-science problems belong to this class—e.g., thetraveling salesman problem, satisfiability problems, and graph-covering problems.

So-called easy, or tractable, problems can be solved by computer algorithms that run in polynomial time; i.e., for a problem of size n, the time or number of steps needed to find the solution is a polynomial function of n. Algorithms for solving hard, or intractable, problems, on the other hand, require times that are exponential functions of the problem size n. Polynomial-time algorithms are considered to be efficient, while exponential-time algorithms are considered inefficient, because the execution times of the latter grow much more rapidly as the problem size increases.

A problem is called NP (nondeterministic polynomial) if its solution can be guessed and verified in polynomial time; nondeterministic means that no particular rule is followed to make the guess. If a problem is NP and all other NP problems are polynomial-time reducible to it, the problem is NP-complete. Thus, finding an efficient algorithm for any NP-complete problem implies that an efficient algorithm can be found for all such problems, since any problem belonging to this class can be recast into any other member of the class. It is not known whether any polynomial-time algorithms will ever be found for NP-complete problems, and determining whether these problems are tractable or intractable remains one of the most important questions in theoretical computer science. When an NP-complete problem must be solved, one approach is to use a polynomial algorithm to approximate the solution; the answer thus obtained will not necessarily be optimal but will be reasonably close.

List of NP-complete problems (not an exhaustive list), that you may face in a Job Interview.

References:
Britanica

Using MATLAB To Solve Systems of Linear Equations

Posted on Updated on

For the times when you just don’t want to do the math you can use MATLAB’s solve function to evaluate systems of linear equations.

MATLAB command window input


solve('2*x+4*y+6*z = -12','2*x-3*y-4*z = 15','3*x+4*y+5*z = -8')

Result:

Predicting The Lottery With MATLAB® Neural Network

Posted on Updated on

DISCLAMER: This post does not in any way prove or disprove the validity of using neural networks to predict the lottery. It is purely for the purpose of demonstrating certain capabilities available in MATLAB ® . The results and conclusions are my opinion and may or may not constitute applicable techniques of predicting the popular Jamaican Lottery Cash Pot game.

Background:

Supreme Ventures Jamaica Limited has a lottery game called Cash Pot (CP) . The game is based on 36 balls being loaded into a chamber and one ball been selected at random from the grouping. The game is ran four (4) times each day seven (7) days per week.

Anecdotal Heuristics:

While doing a little tongue and cheek research at my favorite barbershop, I stumbled upon some heuristics that are employed by most patrons who play the (CP) game. One involved writing down the day, time, and winning number for each day’s lottery. After building up a sufficient dataset, they could then query a particular day and time; and with some simple arithmetic tally the most likely number to be played on that day and time. I was informed that this proved to be a very efficient way of telling which number was to be played next. Another popular heuristic involved pre-assigned symbols; these symbols were associated with each of the thirty six (36) numbers. Then based on dreams aka “rakes” numbers would be chosen that matched the symbols seen in the “rake”. These two methods were the favorite amongst the players of Cash Pot.

Procedure for predicting Cash Pot with MATLAB ANN:

  1. Get the dataset from Supreme Ventures Jamaica website. [contains all winning numbers with date and time]
  2. We will need to do some twiddling with the file in order to get it into a format that MATLAB can use. To do that we need to remove all headings/sub-headings and labels.
  3. Next remove the DRAW# and MARK columns since we will not be using those in our analysis.
  4. In column D use the =WEEKDAY() formula to get the day number from the corresponding date: repeat for all rows.
  5. Use find and replace to replace MORNING with 1, MIDDAY with 2, DRIVETIME with 3 and EVENING with 4. [Save the file]
  6. Using MATLAB folder explorer, navigate to the file then double click on it to run the import tool.
  7. Select columns B and D then hit the import button; this should import only columns B and D, rename the imported matrix to cpInputs .
  8. Select column C and hit the import button; this should import column C only, rename the imported matrix to  cpTargets.
  9. Because MATLAB sees Neural Network(NN) features as rows, transpose the two matrices using
  10. cpInputs = cpInputs’;
    cpTargets = cpTargets’;
    
  11. In the MATLAB command window type nntool.
  12. Import cpInputs and cpTargets into the NN data manager.
  13. Hit the new button on the Neural Network Data Manager and change the default name to cpNN.
  14. Set Input data to cpInputs, Target data to cpTargets.
  15. Hit the create button to create the NN.
  16.  

    Note:

    The newly created NN has two inputs, the first been the day of the week on which the [CP] is scheduled to be played and the second input the time of day that the [CP] is scheduled to played. It also has a hidden layer with 10 neurons with associated bias, and an output layer with 1 neuron and its associated bias. The output is a scalar double which represents the predicted winning number.

  17. Let’s go ahead and train this network. On the train tab of the Network: cpNN dialog, select cpInputs for Inputs and cpTargets for Targets; then press the Train Network button to start the network training.
  18. Results of training.
  19. After training the network to the desired tolerance’s go back to the Neural Network/Data Manager dialog box and hit the export button, select cpNN from the list then hit the export button.
  20. Go back to the MATLAB command window and type
  21. CpNN([2;3]) % [day;time]
    
  22. The resulting value will be the NN’s best guess of what will be the winning entry for Cash Pot on a Tuesday at DRIVETIME.

Conclusions:

My initial analysis of the results of the NN was not conclusive, maybe the parameters of the NN could be adjusted and the results compared to actual winning numbers. However, even after doing so one may find that the outputs are still random and contain no discernible patterns, which should be the case for a supposedly random game of chance.