Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Lab Objective
To write a fancy, high-level program, we inevitably end up building on fundamental
computational activities like querying data structures or ordering lists. Although
these subroutines are executed out of sight, it is still important that you develop an
appreciation for ecient, low-level algorithms.
This lab focuses on the design and implementation of combinatoric
algorithms.
First, you will have an opportunity to practice implementing searching and sorting
algorithms. Then, you will apply your understanding to implement Dijkstra’s short-
est path algorithm. Finally, you will use your code to investigate travel through a
network of connected Paci c Islands, simulating the migration of early Polynesian
explorers from Southeast Asia to Aotearoa.
In order to complete the lab, you have been provided with the following les:
an example network in test network.txt
partially completed functions in comblab functions.py
some practice exercises in comblab practice.py
an implementation le for your Dijkstra’s algorithm, comblab run dijkstras.py
an example template of the Dijkstra’s algorithm function in
comblab dijkstras template.py
a question-answer template le, comblab questions.txt
Your main tasks will be to complete the functions search, insertion_sort, and
dijkstra de ned in comblab functions.py.
Practice Exercises
These exercises are OPTIONAL but RECOMMENDED.
In your IDE, open comblab practice.py and read the commented instructions. Try
to complete these exercises before moving on to the assessed task.
Searching a Tree Network
In lecture, we discussed concepts and algorithms for searching within a tree network,
including how to build a queue or stack using a linked list object. The rst practice
task is to write a function to implement either a depth- rst or breadth- rst search
(your choice). Your search should make use of a linked list object.
Open comblab functions.py and complete the function search. Test your
code is working properly by passing the rst set of assert commands in
comblab practice.py.
It is recommended that you start by writing pseudocode and doing a few steps by
hand using the same Tree network given in the Jupyter notebook.
Sorting a list of integers
In lecture, we discussed dierent kinds of sorting tasks, including creating an index
table or rank table to sort a corresponding list. Review the Jupyter notebook visu-
alisation of the insertion sort algorithm. The second practice task asks you to write
a function to implement an insertion sort that sorts integers into ascending order
and also outputs an index table.
Open comblab functions.py and complete the function insertion_sort.
Test your code is working properly by passing the second set of assert
commands in comblab practice.py.
It is recommended that you start by writing pseudocode and doing a few steps by
hand using the same list given in the Jupyter notebook.