Hello my name is Keelan Duddy. This github page contains my end of the year assessment for Graph Theory. The purpose of this notebook is to demonstrate my understanding, and learning outcomes I have earned in the module Graph Theory in software development at ATU.
Graph theory is the study of graphs which is a mathematical structure use to model pair wise relationships between objects from a collection. Graph theory uses vertices (nodes/points) and edges (lines) to show these relationships. We will be using graph theory to help us demonstrate the contents of this notebook which involves Heap sort and Graph Isomorphism.
For this module we were asked to discuss the following two:
In computer science, heapsort is a comparison-based sorting algorithm.
Within this notebook we discuss:
- Discuss what is the Heap Sort algorithm.
- Implementing Python function for Heap Sort.
- Explain the computational complexity of Heap Sort.
- Explain how graph theory is used in Heap Sort.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
Within this notebook we discuss:
- Discussing what is the Graph Iomorphism Problem.
- Explain how graphs can be represented in data structures.
- Create a Python function implementing an algorithm to determine if two graphs are isomorphic or not.
- Discussion of the computational complexity of the Graph Isomorphism Problem.
Platform: Jupyter Notebook
Coding language Python
We will be doing this through the programming language called Python. Python is one the top programming languages right now. It's design philosophy emphasizes code readability with the use of significant indentation. A lot of data scientists learn python due to it's powerful capabilities in data science with its many great libraries that deal with data science application.
The second reason why is the easy to learn syntax compared to other languages, this is important because many data scientist might not have the a lot of knowledge when it comes to programming and don't want to get bogged down with the nitty gritty some programming languages can have.
So Python will be a great way to demonstrate heap-sort algorithm and Graph Isomorphism Problem. How will we be doing this is through notebooks from a Python package known as Jupyter. Jupyter notebooks is a really helpful tool to visualise data in a detailed and organised manner.
Download Anaconda which is a distribution of the Python programming languages for scientific computing, that aims to simplify package management and deployment. The distribution includes data-science packages suitable for Windows, Linux, and macOS.
Click here To install Anaconda to get Python and follow this installation document
If you wish to look at the contents of the notebook closer, you will need to install jupyter notebook.
Jupyter installation requires Python 3.3 or greater.
Click here to install Jupyter via Python Installation
Once you followed the guides instructions, clone this repository:
git clone https://github.com/Keelan1996/Graph-Theory-ProjectOpen up your terminal at the designated location:
cd Graph-Theory-ProjectType in and run this command:
Jupyter notebookAfter this the jupyter notebook will pop up in your browser of choice.
Jupyter Notebook is an open-source web appliction that allows you to create and share documents that contain code, visualisations, equations and detailed notes. Many data scientist use jupyter notebook for statistc modelling, machine learning, data visualisations and much more.
If you are having any trouble with Jupyter Notebook. Jupter Notebooks troubleshooting page may help
If you would like to contribute to this notebook, please send me your ideas, new research, improvements to my email: [email protected]. I will review them and get back to you.
If you are still having any issues or even want to ask questions please contact me at my email: [email protected] I'll get back to you as soon as I can.
After completing this project I feel I've learned a lot about these two topics. The fact I had to go out and research these complex topics on my own, take what I found and explain them in depth. While trying to display the information I found in a more approachable way for other people to see, was a challenge. I feel this has greatly increased my research skills, especially when comes to computer science topics.
Using Jupyter notebook and understanding how it works will be a great asset to me. I really enjoy that it's a mixture of a word document where you can explain points in writing but you are also able to write and run code. I definitely see myself using this again when i need to research any other computer science or mathematic topics.
Python was certainly a language that I was wanting to learn more about. It's become a very popular language these days, I feel learning and now knowing the language is only a benifit to me. Using Python while researching these topics greatly improved my skills in the language. Early on I did find the indentation aspect of language to be quite frustrating for me, especially with other languages I know (Java) use curly braces. I did eventually with practice get over this hurdle with the language.
Keelan Duddy
Dr Ian McLoughlin.
Toni Canada.
https://en.wikipedia.org/wiki/Algorithm [1] https://en.wikipedia.org/wiki/Data_structure [2] https://en.wikipedia.org/wiki/Heapsort [3]
Data Structures and Algorithms in Java by Michael T. Goodrich https://books.google.ie/books?id=UqmYAgAAQBAJ&printsec=frontcover&dq=data+structures+and+algorithms&hl=en&sa=X&ved=2ahUKEwjT0pD3yM72AhVGasAKHYUfAMUQ6AF6BAgGEAI#v=onepage&q=data%20structures%20and%20algorithms&f=false [4]
What is a binary heap https://medium.com/@mopurisreenath/what-is-binary-heap-25cd0f8bed24 [5]
complete binary tree https://www.techiedelight.com/check-given-binary-tree-complete-binary-tree-not/ [6]
https://www.baeldung.com/cs/heap-vs-binary-search-tree [7]
binary tree data structure and algorithms https://www.tutorialspoint.com/data_structures_algorithms/tree_data_structure.htm [8]
max and min heap https://www.geeksforgeeks.org/difference-between-min-heap-and-max-heap/ [9]
binary heap geeks https://www.geeksforgeeks.org/binary-heap/ [10]
big o notation https://www.freecodecamp.org/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/ [11]
big o complexity https://guides.codepath.com/compsci/Big-O-Complexity-Analysis#:~:text=Big%20O%20notation%20is%20used,the%20size%20of%20the%20dataset. [12]
heapsort o(n log n) https://www.quora.com/How-does-Heapsort-take-O-nlogn-time [13]
what is graph theory and why we should care https://towardsdatascience.com/what-is-graph-theory-and-why-should-you-care-28d6a715a5c2#:~:text=Graph%20Theory%20is%20ultimately%20the,moving%20parts%20of%20dynamic%20systems. [14]
Dr Ian McLoughlin. [15]
heapsort complexity https://www.happycoders.eu/algorithms/heapsort/ [16]
Sciencing https://sciencing.com/the-advantages-of-heap-sort-12749895.html [17]
opengenus Time & Space Complexity of Heap Sort https://iq.opengenus.org/time-complexity-of-heap-sort/ [18]
run time analysis of heapsort https://medium.com/@angeloacebedo/run-time-analysis-heap-sort-8b81d6403508 [19]
merge sort https://www.geeksforgeeks.org/merge-sort/ [20]
quicksort https://www.geeksforgeeks.org/python-program-for-quicksort/ [21]
Graph theory https://economictimes.indiatimes.com/definition/graph-theory [1]
vertices and edges https://www.tutorialspoint.com/edges-and-vertices-of-graph [2]
vertix graph theory https://en.wikipedia.org/wiki/Vertex_(graph_theory) [3]
tutorialspoint isomorphic https://www.tutorialspoint.com/graph_theory/graph_theory_isomorphism.htm [4]
Graph Isomorphism problem wiki https://en.wikipedia.org/wiki/Graph_isomorphism_problem [5]
complexity class https://en.wikipedia.org/wiki/Complexity_class [6]
P vs NP https://simple.wikipedia.org/wiki/P_versus_NP [7]
Millennium Problems https://simple.wikipedia.org/wiki/Millennium_Prize_Problems [8]
brute force iso code https://tonicanada.medium.com/brute-force-code-for-isomorphisms-1241ef180570 [9]
GeeksforGeeks graph and its representations https://www.geeksforgeeks.org/graph-and-its-representations/ [10]
numpy doc https://numpy.org/doc/ [11]
sets geeksforgeeks https://www.geeksforgeeks.org/graph-representations-using-set-hash/ [12]
programiz adjacency list https://www.programiz.com/dsa/graph-adjacency-list#:~:text=An%20adjacency%20list%20represents%20a,an%20edge%20with%20the%20vertex. [13]
Brute force graph Isomorphic code https://gist.github.com/tonicanada/5f689540d30e51a9837d660b801ef9cb [14]
stack overflow: What are NP-Intermediate problems? https://stackoverflow.com/questions/40773886/what-are-np-intermediate-problems/40773945#40773945 [15]
GateVidyalay: Graph Isomorphism Conditions https://www.gatevidyalay.com/graph-isomorphism/#:~:text=Graph%20Isomorphism%20Conditions%2D&text=Number%20of%20vertices%20in%20both,the%20graphs%20must%20be%20same. [16]