Posts by Mavericks

According to
mktime takes struct_time in local time as per
"Use the following functions to convert between time representations:" section of the page
http://docs.python.org/2/library/time.html#time.struct_time

Line 29 I think needs to go between line 21 and 22.
can you check if that helps?
I say that because y += 1 is already handled in second if loop.
so it doesn't make sense to increment it again at line 29

how to find the time complexity of any algorithm
and also describe with examples
please help

http://www.cs.ucf.edu/~dmarino/ucf/cop3502/lec_biswas/recursion12.pdf
This will help understand time complexity of recursive function. Explanation is quite clear

Studying same problem, write my own implementation.

Sebastien Boutte

public static <T> int combinations(List<List<T>> list) {
		int count = 1;
		for(List<T> current : list) {
			count = count * current.size();
		}
		return count;
	}

        public static <T> List<List<T>> combinate(List<List<T>> uncombinedList) {
		List<List<T>> list = new ArrayList<List<T>>();
		int index[] = new int[uncombinedList.size()];
		int combinations = combinations(uncombinedList)-1;
		// Initialize index
		for(int i = 0; i< index.length; i++) {
			index[i] = 0;
		}
		// First combination is always valid
		List<T> combination = new ArrayList<T>();
		for(int m = 0; m< index.length; m++) {
			combination.add(uncombinedList.get(m).get(index[m]));
		}
		list.add(combination);
		for(int k = 0; k< combinations; k++) {
			combination = new ArrayList<T>();
			boolean found = false;
			// We Use reverse order
			for(int l = index.length-1 ; l >=0 && found == false; l--) {
				int currentListSize = uncombinedList.get(l).size();
				if (index[l] < currentListSize-1) {
					index[l] = index[l]+1;
					found = true;
				}
				else {
					// Overflow
					index[l] = 0;
				}
			}
			for(int m = 0; m< index.length; m++) {
				combination.add(uncombinedList.get(m).get(index[m]));
			}
			list.add(combination);
		}
		return list;
	}

What is the demo code to run this program? Are there any special conditions where this program works and won't work?

sorry replace DTPPhase with String :-)

I get the DTP.Model doesn't exist even after the replacemnt with String

I can't find where it says that in that text you linked, so it's hard to explain their reasoning without knowing what it is :)

Maybe I'm just being blind, can you tell me where it says that?

In
http://ptgmedia.pearsoncmg.com/images/0201361213/samplechapter/sedgewickch21.pdf

Program 21.1, has the following sentence:

The constructor is also a generalized graph search that implements
other PFS algorithms with other assignments to the priority P (see text).
* The statement to reassign the weight of tree vertices to 0 is needed for a
general PFS implementation *
but not for Dijkstra’s algorithm, since the
priorities of the vertices added to the SPT are nondecreasing

Thanks Momerath. I agree, and understand now.

I still don't understand why reassigning weights of tree vertices to zero is needed for general PFS(Priority First search) implementation.

I can't imagine a situation where reassigning will be needed.

I have a question regarding Dijkstra's algorithm (priority-first search)

To be precise:
In http://flylib.com/books/en/3.56.1.58/1/

The statement to reassign the weight of tree vertices to 0 is needed for a general PFS implementation but not for Dijkstra's algorithm, since the priorities of the vertices added to the SPT are nondecreasing

Note the Dijkstra's algorithm doesn't discuss about dealing with negative weights yet at that point.

What does priorities of the vertices(distances) added to the SPT are nondecreasing mean?

Does it mean distance s-v-t is greater than s-v
as only the edge weight or distance is positive ?
So, it cannot decrease and can only increase.

If so, why is reassigning the weight of tree vertices to 0 needed for a general PFS implementation ?