Search Results

5 matches found for 'backtracking'

Paint adjacent boundaries with distinct colors

... to True (this arc is revised) revised = True return revised def backtrackingSearch(csp): # initialization, runs only once assignment = {} for country in csp: assignment[country] = set(['red','blue','white','yellow','green']) return recursiveBacktracking(assignment,csp) def recursiveBacktracking(assignment, csp): """ GOAL TEST : each country should be mapped to 1 color only, meaning they are assigned """ if all(len(assignment[country]) == 1 for country in csp): return assignment """ choose a country with MRV (Minimum-Remaining Values) """ var = selectUnassignedVariable(assignment, csp) """ choose a color from all available colors.

December 11, 2014

Greedy Algorithms

There are many definitions of greedy algorithms, but in general, they have two properties: You build the solution by finding the most optimal answer at each local step. As you go through each local step, you do not backtrack; the answer you've picked for all of the previous steps remain the same.

October 28, 2018

Buy and Sell Two Stocks

Problem Given an array of integers representing stock prices, with each index representing a different day, find the maximum profit by selling at most two stocks. The buy/sell dates must not overlap.

December 10, 2018

Cyclic Permutation

This is an array/list trick that saves about O(n) in space complexity by taking advantage of a given array with integers representing indices. For this example problem, suppose that we want to apply some permutation P to an array A.

September 11, 2017

Compute the max. water trapped by a pair of vertical lines

Problem An array of integers naturally defines a set of lines parallel to the Y-axis, starting from x = 0 as illustrated in the figure above. The goal of this problem is to find the pair of lines that together with the X-axis "trap" the most water.

February 5, 2019