Archive | May, 2012

Free online education

12 May

Free tertiary education is available through the intermediary Coursera. There are courses which a provided by top universities such as Princeton and Stanford! A range of courses from multiple categories are offered such as computer science, mathematics and social sciences. Personally, I feel that it probably doesn’t act as a complete substitute to tertiary education in it’s current state as the courses do not follow the complete syllabus as taught on campus. However, I have completed a course ‘Design and Analysis of Algorithms I’ and found it extremely useful in the short duration of 5 weeks which it lasted. Video lectures were provided by a highly competent lecturer and there are regular assessments to test your knowledge just like a real university course. A certificate of completion is even awarded by the end of it if a certain grade has been achieved. Also, did I mention that all of this is free?

I expect online education like this will be more prevalent in the future which I believe can only be a good thing.

Advertisements

Google codejam Round 1C 2012 Problem A. Diamond Inheritance

12 May

Introduction

So I recently came across this problem while browsing the google codejam contest practice problems. The problem is outlined below with the solution I came up with at the end. I typically use python as my programming language of choice for algorithm type problems as it is easy to use and therefore more focus can be put into actually formulating your algorithm rather than having to worry about the syntax and semantics of the language. A downside is that due to it’s high-level nature it is less performant than other languages in general but this shouldn’t be a problem in most cases.

Problem

You are asked to help diagnose class diagrams to identify instances of diamond inheritance. The following example class diagram illustrates the property of diamond inheritance. There are four classes: A, B, C and D. An arrow pointing from X to Y indicates that class X inherits from class Y.

In this class diagram, D inherits from both B and C, B inherits from A, and C also inherits from A. An inheritance path from X to Y is defined as a sequence of classes X, C1, C2, C3, …, Cn, Y where X inherits from C1, Ci inherits from Ci + 1 for 1 ≤ i ≤ n – 1, and Cn inherits from Y. There are two inheritance paths from D to A in the example above. The first path is D, B, A and the second path is D, C, A.

A class diagram is said to contain a diamond inheritance if there exists a pair of classes X and Y such that there are at least two different inheritance paths from X to Y. The above class diagram is a classic example of diamond inheritance. Your task is to determine whether or not a given class diagram contains a diamond inheritance.

Input

The first line of the input gives the number of test cases, T. T test cases follow, each specifies a class diagram. The first line of each test case gives the number of classes in this diagram, N. The classes are numbered from 1 to N. N lines follow. The ith line starts with a non-negative integer Mi indicating the number of classes that class i inherits from. This is followed by Mi distinct positive integers each from 1 to N representing those classes. You may assume that:

  • If there is an inheritance path from X to Y then there is no inheritance path from Y to X.
  • A class will never inherit from itself.

Output

For each diagram, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is “Yes” if the class diagram contains a diamond inheritance, “No” otherwise.

Limits

1 ≤ T ≤ 50.
0 ≤ Mi ≤ 10.

Small dataset

1 ≤ N ≤ 50.

Large dataset

1 ≤ N ≤ 1,000.

Sample

Input Output
3
3
1 2
1 3
0
5
2 2 3
1 4
1 5
1 5
0
3
2 2 3
1 3
0
Case #1: No
Case #2: Yes
Case #3: Yes

Solution

So pretty much my solution is based off of the breadth first search graph algorithm. Pretty much all that is done is to first build the graph using the classic adjacency list representation. We then loop through all nodes in the graph and invoke the BFS algorithm on each node. The special trick comes in the conditional section where we show that if we are trying to add a node to the existing path and the node already exists in the path created then it means we have already visited that node and hence another path to this node has been found. We can therefore break the loop as we have found this second path. Ways in which this algorithm can be improved is to simply return true or false as we only need a boolean for output and to come up with an alternate faster way of searching the existing path for the given node rather than just going

 if not v in path:

Perhaps a hash table should suffice in achieving this. Example input can be retrieved here, to run the program simply go

 python [programName.py] < inputfile

from command-line.

The code:

from sys import stdin

# create directed graph
def build_graph(rawData):
	""" Graph is built into an adjacency list
	e.g. 2 3
	     1 
	means that the first node points to the 2nd and 3rd and
	the second node points to the first with the 3rd node
	having no outgoing edges
	"""
	graph={}

	count = 1
	for line in rawData:
		data = line.split()
		edges = []
		for edgesString in range(1, len(data)):
			edges.append(int(data[edgesString]))
		graph[count] = edges
		count+=1

	return graph

# count number of paths using BFS
""" The special trick: if the node currently exists in the path then
we can simply say that there is another path to this node and hence
break the loop as we have found there is more than 1 path to the target 
"""
def count_paths(graph, start, path=[]):
	numPaths=1
	q=[start]
	while q:
		v=q.pop(0)
		if not v in path:
			path=path+[v]
			q=q+graph[v]
		else:
			numPaths+=1
			break
	return numPaths

for i in range(int(stdin.readline())):
	rawData = []
	for node in range(int(stdin.readline())):
		rawData.append(stdin.readline())
	graph = build_graph(rawData)

	numPaths = 0
	# loop through all nodes in the graph
	for node in range(1,len(rawData)+1):
		numPaths = count_paths(graph, node)
		if numPaths >= 2: break
	isDiamond = 'Yes' if numPaths >= 2 else 'No'
	print 'Case #'+str(i+1)+': ' + isDiamond

Introduction – Hello World!

12 May

Hi Everyone! This blog is intended for sharing all things techy/geeky from coding to software setup hence the name techshare1337. Mostly for educational purposes and I also intend to post some gaming stuff. Any suggestions for material you wish to see are welcome. Thats all for now and I hope you enjoy this blog!