Very essential Microchip PIC32MX795F512H development board with three user LEDs and two buttons that supports USB bootloader and ICSP programming.
Microchip PIC32MX795F512H development board
Reply
Category Archives: Theory
Playstation controller hack with Arduino MINI and nRF24L01
This time we see a Playstation controller hack to use it wirelessly in our projects. In this article we use an Arduino MINI board wired with the Playstation’s controller circuit, an nRF24L01+ module and a small LiPo cell with an USB charger circuit based on Microchip’s MCP73831 ic.
Dynamic Programming
“In mathematics, computer science, economics, and bioinformatics, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems[1] and optimal substructure. When applicable, the method takes far less time than naive methods that don’t take advantage of the subproblem overlap. The idea behind dynamic programming is quite simple. In general, to solve a given problem, we need to solve different parts of the problem (subproblems), then combine the solutions of the subproblems to reach an overall solution. Often when using a more naive method, many of the subproblems are generated and solved many times. The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number of computations: once the solution to a given subproblem has been computed, it is stored or “memo-ized”: the next time the same solution is needed, it is simply looked up. This approach is especially useful when the number of repeating subproblems grows exponentially as a function of the size of the input.” – From Wikipedia
Randomized rounding on Linear Programming
“Within computer science and operations research, many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). Many such problems do admit fast (polynomial time) approximation algorithms – that is, algorithms that are guaranteed to return an approximately optimal solution given any input.
Randomized rounding (Raghavan & Tompson 1987) is a widely used approach for designing and analyzing such approximation algorithms. The basic idea is to use the probabilistic method to convert an optimal solution of a relaxation of the problem into an approximately optimal solution to the original problem.” – from Wikipedia
In the following we prove the correctness of randomized rounding on LP, given the optimal value.
Approximation algorithm for multiway-cut
Given a graph 
and a set 
of 
terminal vertices, a multiway-cut is a set 
of edges such that in 
, no path exists between any two nodes of 
. The multiway-cut problem is defined as finding the multiway-cut where 
is minimal. Multi-way cut terminal problem is known to be NP-hard for 
.
Again, using approximation we can make a faster algorithm.