Algorithmic Problem Solving

This is a first year assignment so please do not use any advance algorithm and also please follow the instructions strictly. Lecture and Workshop material to be used! ONLY USE THE MATERIAL PROVIDED PLEASE, BEFORE ANY EXTRA MATERIAL INTRODUCED, CONSULT WITH ME FIRST PLEASE!!! Selection, loops, and repetition. Introduction to data structures and decomposition Invariance and greedy algorithms Brute-force search Exhaustive search and divide and conquer Recursion Recursive divide and conquer, stacks and queues, and backtracking Import math Import random Strings Lists Coin question Graphs, multigraphs For –while (If else) loops The MU game Magic square Prime number Prime number Lists of Lists, Tables Sequential numbers Merge databases Sorting(selection sort, insertion sort, quick sort N Queens problem Adjacency matrix Incidence matrix Adjacency list anagrams bitlist Reading from a file Writing to a file Defining functions Function decomposition Binary search Variant in binary search Greedy approach/algorithm Compute factorial Euclid’s algorithm Root finding algorithm Pascal triangle Recursive function LIFO data structure FIFO data structure ASSIGNMENT ONLY THE FOLLOWING FILES MUST BE PREPARED: . graphFileOps.py . intersection.py . union.py . diference.py . supergraph.py . connectivity.py . greedy.py . greedy.pdf (or greedy.rtf if you prefer) bruteforce.py . You are not allowed to import any Python library or module and should not be using any inbuilt python functions that simplify the tasks you are told to implement. . The written program will be checked against a number of test cases. Do not forget to include comments in your code explaining your algorithm. If your implementations have bugs, you may still get some marks based on how close your algorithm is to the correct algorithm. Also, make sure that your program handles the boundary cases properly. . This assignment requires an understanding of greedy algorithms and brute force solutions to problems in order to complete. . PLEASE DO NOT FORGET TO COMMENT when necessary (especially when you introduce a new function or algorithm that is not listed above) AS I HAVE TO EXPLAIN THIS ASSIGNMENT TO MY TUTOR LATER. Context of the Assignment Graphs apply to many problems and are common in issues of connectivity and networks. For this assignment we are imagining ourselves as professional programmers already and have taken on a client, a Ms. Fathima Arda Moor. Ms. Moor runs a large wheat farm in western Victoria (Australia) and has recently purchased some of her neighbouring farms; she wishes to combine together the water systems to allow for more e cient irrigation of each farm’s crops. Fortunately each of these farms had their piping systems mapped in blueprints (which are relatively easy to digitise); Unfortunately some of these farms include multiple separate piping systems for handling irrigation so she has turned to you for help.