Graph Theory - Programming
Python or Sage
Coding assignments must be done is Python (Python 2.7 or Python 3.*) or Sage. Python code can be as a .py file, or as a Jupyter notebook. Sage code should be as a Jupyter notebook. (Sage, written in python, is computer algebra system which uses python-like syntax. It adds vast mathematics-oriented libraries, and allows one to call functions from many other open-source algebra systems. It is much easier to install on linux, but there is a windows version.)Python Notebooks Online
If you are unfamiliar with all of these systems, I suggest you use a python notebook. If you can install it on your computer, this is probably the best. But if that is difficult, there are several places you can get free access to an online python notebook server. Again, this changes frequently, but here is a fairly recent list of free notebook servers: OUseful.Info For most you have to have a (free) account, but you probably already have a Google account with which you can use Colab, or a Microsoft account with which you can use Azure Notebooks. The site CoCalc offers both Python and Sage Notebooks.Using Libraries
You may use libraries such as numpy and networkx for their matrix and graph data structures. They also have many algorithms that we see in this class. If I ask you to program an algorithm, you, of course, cannot use the algorithms from these libraries. As a rule of thumb, if you (or I or several of the students in the class) don't know, mathematically' how you would do the algorithm, then you cannot use it.Your first programming homework
Your first computing assignment will be a program that, given a graph H, in the networkx.graph format, will return 'true' or 'false' depending on whether or not H is a tree.If you hand this in as a jupyter notebook file, (as a .ipynb file) the final cell should execute to return your answer 'true' or 'false', and should do this for a graph H that can be defined immediatly before the final cell. (I will put my own graph in there to test your program.)
If you hand it in as an uncompiled python program (as a .py file), please use this file as a Template. It will include a file of TestGraph.py of mine that defines a graph H, on which I will test the program.
Make sure that your name and student number are in the comments in the file/notebook, and that the filename has a common version of your name in it: IsTree-Irshad.py or IsTree-Irshad.ipynb.
main page