Karen Shay West's Home Page

Python Class Examples: Optimization Problems and Dynamic Programming: Multiple Examples in Links Below and Some Descriptions Follow

Links to Python Class Example: Optimization Problems and Dynamic Programming: Fitting Data to Linear Curve, Cubic Curve, and Quadratic Curve, Plots, Getting Trajectories, Height Distributions, Meausred Verses Predicted, and Means.

Links to Python Class Example: Samples, Coin Flip Experiment, Variance and Standard Deviation, Histograms

Links to Python Class Example: Die Rolls, Pascal, Standard Deviation, Trials, Pylab Plots, Normal Distributions, Simulations

Links to Python Class Example: Random Walk Simulations, Field Location, Drunk Classes Test, Mean and Max and Number of Steps to reach destination, Drunken Walk Plots

Links to Python Class Example: Random Choice Simulations, Standard Deviations and Throwing Needles Example, Estimation of Pi Example, Integration, Double Integration and Display

Links to Python Class Example: Knapsack Item Stealing Algorithm Problem, The Greedy Algorithm, Weight Metric, Power Sets, and Choose Best verses Random and Time

Links to Python Class Example: The memoize python function that works like a hardware cache for immutable arguments and examples of cost mistmatch or gaps in text format

• DFS and BFS and optimization were used for graph searches of related objects.


• Optimization problems


• Dynamic programming


• Fitting data to linear and quadratic curves


• Normal distributions


• Measuring goodness of fit of data to a curve


• Uniform distributions


• Estimating Pi


• Monty Hall Problems


• Number of samples needed for a coin flip experiment


• Variance and standard deviation


• Plotted histograms


• Causal and predictive nondeterminism


• Stochastic processes


• Monte Carlo Simulations


• Hash Tables


• Random walks and simulation models


• Examined different algorithms for searching and sorting and their Big O Notation performances.

Optimization Problems:

• This lecture example Python code demonstrated code optimization.


• You start with an objective function and a set of constraints the solution must satisfy.


• Examples were the n-queens problem, where you place n-queens on an NxN board so that no 2 queens attack each other (no 2 queens share the same row, column or diagonal).


• Other examples were bin packing, cutting stock and min cut networks and the traveling salesmen problem.


• The challenge shown was that these problems are "hard" to solve.


• Often finding optimal solutions requires examining all possible combinations of items.


• The time to examine all combinations grows exponentially with the number of items.


• "Real World" problems have a large number of items.


• The next set of examples were the burglar's dilemma, 0/1 knapsack problem, and greedy algorithms.


• Which metric works best? Max. value, min. weight or max-value / weight.


• Greedy Algorithm is a heuristic for a 0/1 knapsack problem.


• Given materials of different value/weight ratios, find the most valuable combination of materials which fit in a knapsack of fixed capacity W.


• Greedy algorithm with max value/weight metric finds optimal solution for continuous knapsack problem.


• Optimal solution for 0/1 knapsack problem: formal problem statement: Given vectors of weight wi, and values vi, where "0 <= i <= N-1" items; knapsack holds W.


• Find 0/1 vector ti. Technique exhaustive search enumerates all possible combinations of items and choose the best one that satisfies all constraints.


• Generate the power set combinations of all items.


• Greedy was "O(N log N)" and Optimal was "O(N 2**N)".

Dynamic Programming

• The dynamic programming using optimal substructure and overlapping subproblems.


• In the Fibonacci example the memoize function was used to demonstrate using function arguments as a sequence, which works for immutable and hashable arguments.


• The memoize function remembers previously computed answers, much like a cache does in hardware.


• It showed knapsack subproblems where you try different ways to optimize a long search, such as to not take the first item in the knapsack, then take the 1st item in the knapsack, combine the 2 solutions and see if there are overlaps.


• Code examples (above links) applied these optimizations to find where to place line breaks in a paragraph to minimize "badness".


• The line break subproblems first tried a solution with no line breaks after 1st word, then another with a line break after 1st word, and combined the solutions to find overlaps.


• Another code example demonstrated the minimum cost of alignment between 2 sequences.