The End of a Wonderful Semester - Lessons Learned

           "The dream is not what you see in sleep,
                 dream is which does not let you sleep"
                                                        - Dr. Abdul Kalam

Last Friday, we finished our first semester of the fourth year. Now what we are going to face is the semester end exam. When I start my fourth year after studying for three years in the university, I had been holding a huge collection of experiences and memories in my mind. With all those things, I looked ahead about the fourth year as a totally different time period and I expected something different.


    At the end of this semester when I think back about past few months starting from the October of last year, I wonder how much a fantastic time it was. Unlike all the other semesters, we had a common word in our mouth all the time which is research. In my point of view, the core of the 4th year is the main research project that we have to do throughout the year. Identifying an interesting research problem, reading deeply about the related research works done on that domain and taking initial steps to find a solution can be considered as the main tasks that have to be done during the first semester according to my understanding.


    Unlike the other years, we began to create a closer relationship with the academic staff specially with the supervisors of our research projects. I have two supervisors in my research. They are Dr.Jeevani Gunathileka and Dr.Kasun De Zoysa. Their guidance have helped me to correct the way I work on my project up to now.

    In addition to the research project, I had five more course modules to follow in this semester. Two of them namely "Research Methods" and "Research Seminar" are mandatory courses. If I talk about the "Research Methods" course conducted by Dr.Ruwan Weerasignha, I would say it is a course which helped me to look at the world in a totally different angle. Some of the lectures he did around the topic "Towards a philosophy of Computer Science" led me to read a lot on philosophical texts regarding that. I never thought that philosophy would be such an interesting thing to read without becoming boring. I'm so sure that I will continue to read more on philosophy in the rest of my life time because of the influence I received in this semester.

     The other mandatory course we had is the fantastic "Research Seminar" series. In each week we discuss about two research papers presented by two participants. These research papers are belong to various domains of Computer Science and therefore it increases the breadth of our knowledge while our individual research project increase the depth of our knowledge in a specific research area. Our lecturer Mr. Dulan Wathugala do a great job on throwing us on to the research ocean and help to learn how to survive there.

    Except for few occasions, I never let the paper presenters an easy life at the research seminars. We had lots of arguments and big discussions regarding the papers and their solutions presented for various problems. I can honestly say that I significantly improved my questioning ability by attending to the research seminars. This is the semester I talked a lot. My voice was there in every major discussion and argument. The good news is Research Seminar series will be continued in the next semester also.

    It is not just the academic stuff that made this semester fascinating. We organized our last function in the undergraduate life with a great effort and at the same time with a great fun. It is the Going Down 2012 party we organized for our seniors. Since a big portion of our 2007/2008 batch is in the software industry because of they passed out from the university after completing the three year degree, most of the decoration works and responsibilities had to be handled by the 4th year students who are the remaining part of the batch 2007/2008 inside university. I personally enjoyed all the works we carried out in the preparation for the party. Even in the party day, I enjoyed a lot and danced as much as I wanted in the DJ. It was a fantastic time.

    It is not true if I say it was happiness and joy always around me in this semester. I had so many challenges, difficulties and struggles parallel to the happiness and joy. I could get through all those life experiences with the great helps of all the awesome people around me who never let me go down.
   
    At the last "Research Methods" lecture on last Friday, Dr.Ruwan invited Dr.Shiromi Arunathileka to conduct that last lecture. At the end of her lecture she expressed about her life experiences and difficulties she faced in her life. I felt that we are having a very special and passionate set of people as our lecturers not only in academic works but in life in general. In her lecture Dr.Shiromi highlighted a famous quote of great scientist Albert Einstein to convince us that sometimes we have to follow our intuition that comes from a deepest place in our heart since the rationality does not guide us in the right direction in life always. I return from this note leaving that great words here.

    “The intuitive mind is a sacred gift and the rational mind is a faithful servant. We have created a society that honors the servant and has forgotten the gift.”
                           ― Albert Einstein

Longest Path Algorithm Implemented in Python

Here I write down the longest path algorithm implementation I did in Python language. Since finding the longest path algorithm is considered as an intractable problem, you will notice that when the number of vertexes in the graph increases the time to find the longest path increases in an exponential way.

The input graph to the program is given as a separate configuration file which also I have shown separately.

longest_path.py file

1:  #!/usr/bin/python  
2:  import string  
3:  import time  
4:    
5:  # represents a vertex in the graph  
6:  class Vertex:  
7:       def __init__(self, name):  
8:            self.name = name           # name of the vertex  
9:            self.visited = 0          # access flag 1=visited, 0=not visited  
10:     
11:     
12:  # represents an edge in the graph  
13:  class Edge:  
14:       def __init__(self, v, u, length):  
15:            self.start = v  
16:            self.end = u  
17:            self.length = length  
18:    
19:    
20:  # read a text file and generate the graph according to declarations  
21:  def generateGraph(V, E):  
22:    
23:       file = open("graph_def_v11", "r")  
24:       line = file.readline()  
25:       line = line[:-1]  
26:       while line:  
27:            taglist = string.split(line)  
28:            if taglist[0] == 'vertex':  
29:                 V.append(Vertex(taglist[1]))  
30:            elif taglist[0] == 'edge':  
31:                 E.append(Edge(taglist[1], taglist[2], string.atoi(taglist[3])))  
32:                 E.append(Edge(taglist[2], taglist[1], string.atoi(taglist[3])))  
33:            line = file.readline()  
34:            line = line[:-1]            
35:       file.close()  
36:    
37:    
38:  # returns the edges list of vertex v  
39:  def pickEdgesList(v, E):  
40:       vu = []  
41:       for edge in E:  
42:            if edge.start == v.name:  
43:                 vu.append(edge)  
44:       return vu  
45:    
46:  def pickVertexByName(V, A):  
47:       for vertex in V:  
48:            if vertex.name == A:  
49:                 return vertex  
50:    
51:  def LP(V, E, A):  
52:       #print("in LP")  
53:       dist = 0  
54:       maxa = 0  
55:       v = pickVertexByName(V, A)  
56:       v.visited = 1  
57:       vu = pickEdgesList(v, E)  
58:       for edge in vu:  
59:            u = pickVertexByName(V, edge.end)  
60:            if u.visited == 0:  
61:                 dist = edge.length + LP(V, E, u.name)  
62:                 if dist > maxa:  
63:                      maxa = dist  
64:       v.visited = 0  
65:       return maxa  
66:    
67:    
68:  def main():  
69:       print('Starting Longest Path Algorithm...')       
70:       t1 = time.time()  
71:       # graph elements  
72:       V = []  
73:       E = []  
74:       generateGraph(V, E)       
75:       maxa = LP(V, E, 'a')  
76:       print 'max=', maxa  
77:       t2 = time.time()  
78:       print t2-t1  
79:    
80:    
81:  main()  

The content of the graph configuration file which is saved as graph_def is as follows.

1:  vertex a  
2:  vertex b  
3:  vertex c  
4:  vertex d  
5:  ------------  
6:  edge a b 1  
7:  edge a c 1  
8:  edge a d 1  
9:  edge b c 1  
10:  edge b d 1  
11:  edge c d 1  

You can run this program on a Linux machined by typing the following line on the terminal,

python longest_path.py

cheers!

Dijkstra's Shortest Path Algorithm implemented in Python

For an assignment work I had to implement the shortest path algorithm and the longest path algorithm recently. Since the implementation language was our choice I used Python to implement it since I was thinking to learn Python for a long time. I took this assignment as an opportunity to learn Python.

Here I write down the source codes of the dijkstra's shortest path algorithm I implemented in Python. This may not be the best way to code it. But this is what my poor Python skills returned. However now I have a considerable exposure in the language and therefore hope I will use it in better ways in the future.

The input graph to the program is given as a separate configuration file which also I have shown.

shortest_path.py file

1:  #!/usr/bin/python  
2:  import string  
3:  import time  
4:    
5:  # represents a vertex in the graph  
6:  class Vertex:  
7:       def __init__(self, name):  
8:            self.name = name         # name of the vertex  
9:            self.dist = 1000         # distance to this vertex from start vertex  
10:            self.prev = None        # previous vertex to this vertex  
11:            self.flag = 0           # access flag  
12:     
13:     
14:  # represents an edge in the graph  
15:  class Edge:  
16:       def __init__(self, u, v, length):  
17:            self.start = u  
18:            self.end = v  
19:            self.length = length  
20:    
21:    
22:  # read a text file and generate the graph according to declarations  
23:  def generateGraph(V, E):  
24:       file = open("graph_def", "r")  
25:       line = file.readline()  
26:       line = line[:-1]  
27:       while line:  
28:            taglist = string.split(line)  
29:            if taglist[0] == 'vertex':  
30:                 V.append(Vertex(taglist[1]))  
31:            elif taglist[0] == 'edge':  
32:                 E.append(Edge(taglist[1], taglist[2], string.atoi(taglist[3])))  
33:                 E.append(Edge(taglist[2], taglist[1], string.atoi(taglist[3])))  
34:            line = file.readline()  
35:            line = line[:-1]            
36:       file.close()  
37:    
38:    
39:  # returns the smallest vertex in V but not in S  
40:  def pickSmallestVertex(V):  
41:       minVertex = None  
42:       for vertex in V:  
43:            if vertex.flag == 0:  
44:                 minVertex = vertex  
45:                 break  
46:       if minVertex == None:  
47:            return minVertex  
48:       for vertex in V:  
49:            if vertex.flag == 0 and vertex.dist < minVertex.dist:  
50:                 minVertex = vertex  
51:       return minVertex  
52:    
53:    
54:  # returns the edges list of vertex u  
55:  def pickEdgesList(u, E):  
56:       uv = []  
57:       for edge in E:  
58:            if edge.start == u.name:  
59:                 uv.append(edge)  
60:       return uv  
61:    
62:    
63:  def findShortestPath(V, E, S, A):  
64:       # set A vertex distance to zero  
65:       for vertex in V:  
66:            if vertex.name == A:  
67:                 vertex.dist = 0  
68:    
69:       u = pickSmallestVertex(V)  
70:       while u != None:  
71:            u.flag = 1  
72:            uv = pickEdgesList(u, E)  
73:            v = None  
74:            for edge in uv:  
75:                 # take the vertex v  
76:                 for vertex in V:  
77:                      if vertex.name == edge.end:  
78:                           v = vertex  
79:                           break  
80:                 if v.dist > u.dist + edge.length:  
81:                       v.dist = u.dist + edge.length  
82:                      v.prev = u  
83:            u = pickSmallestVertex(V)  
84:    
85:    
86:  def printGraph(V, E):  
87:       print('vertices:')  
88:       for vertex in V:  
89:            previous = vertex.prev       
90:            if previous == None:  
91:                 print(vertex.name, vertex.dist, previous)  
92:            else:  
93:                 print(vertex.name, vertex.dist, previous.name)  
94:       print('edges:')  
95:       for edge in E:       
96:            print(edge.start, edge.end, edge.length)  
97:    
98:    
99:  def main():  
100:       print('Starting Dijkstra\'s Algorithm...')       
101:       t1 = time.time()  
102:       # graph elements  
103:       V = []  
104:       E = []  
105:       S = []  
106:       generateGraph(V, E)       
107:       #printGraph(V, E)  
108:       findShortestPath(V, E, S, 'a')  
109:       #printGraph(V, E)  
110:       print 'dummy '  
111:       t2 = time.time()  
112:       print t2-t1  
113:    
114:    
115:  main()  
116:    

The content of the graph configuration file which is saved as graph_def is as follows.

1:  vertex a  
2:  vertex b  
3:  vertex c  
4:  vertex d  
5:  ------------  
6:  edge a b 1  
7:  edge a c 1  
8:  edge a d 1  
9:  edge b c 1  
10:  edge b d 1  
11:  edge c d 1  

You can run this program on a Linux machined by typing the following line on the terminal,

python shortest_path.py

The longest path program implementation will be given as a separate post.

cheers!

Adding a custom device driver to Contiki OS

While working on various project works on sensor networks, we had a requirement to attach our own devices with sensor motes for different purposes. To do it we have to write low level drivers which will access the pins of the MCU and perform various tasks. If our applications are running on Contiki operating system, then we have to add our drivers to Contiki. In this post, I write the methodology we followed to do it.        
    This may not be the proper way of adding device drivers for Contiki. However this is the way we did it. Lets say we have two driver files named as my_driver.c and my_driver.h which are some drivers for Tmote Sky platform. The C file contains some functions of the driver and the header file contains the prototypes of the functions in C file. The contents of these files may be like follows. (please note that this example function calls the LED driver functions without doing something its own. Depending on your application it may contain some low level codes)

my_driver.c content

1:  #include "dev/leds.h"  
2:  void driver_function(){  
3:       leds_on(LEDS_RED);  
4:  }  

my_driver.h content

1:  void driver_function();  

 First we should copy these two files to Contiki/core/dev/ directory. Then open the Makefile.sky file which resides in the Contiki/platform/sky directory. There's an entry in this file which specify some C file names separated by spaces. Append our drivers C file name to this entry.

    Now open the file contiki-sky-main.c which resides in the same directory (Contiki/platform/sky) and add the following header file inclusion to it.

1:  #include "dev/my_driver.h"  

Now our driver is correctly placed inside the Contiki source code and therefore we can use it in our applications. To test this functionality, call the driver_function() within the Hello-World example application in Contiki/examples/hello-world directory and run it on MSPSIM simulator by issuing the following command.

make TARGET=sky hello-world.mspsim

    If every things went fine, the simulators red LED should be switched on by our drivers driver_function().