COSC 1285/2123
COSC 1285/2123 Algorithms and Analysis
Workshop 4
Brute Force Algorithmic Paradigm
Tutorial Exercises
Objective
Students who complete this tutorial should:
� Understand and apply selection and bubble sort.
� Understand and apply exhaustive search.
� Understand and apply BFS and DFS graph traversals.
3.1.8 Sort the list “E, X, A, M, P, L, E” in alphabetical order by selection sort.
3.1.11 Sort the list “E, X, A, M, P, L, E” in alphabetical order by bubble sort.
3.5.4 Traverse the following graph by breadth-first search (BFS) and construct the corresponding
breadth-first search tree. Start the traversal at vertex a and resolve ties by the vertex alphabetical
order.
3.5.1b Repeat question 3.5.4, but now using depth-first search (DFS) traversal. Also start the
traversal at vertex a and resolve ties by the vertex alphabetical order.
©2021 RMIT University 1
COSC 1285/2123
3.5.1 One can model a maze by having a vertex for a starting point, a finishing point, dead ends,
and all the points in the maze where more than one path can be taken, and then connecting the
vertices according to the paths in the maze.
a Construct such a graph for the maze.
b Which traversal – DFS or BFS – would you use if you found yourself in a maze and why?
3.4.6 Consider the partition problem: given n positive integers, partition them into two disjoint
subsets with the same sum of their elements. (Of course, the problem does not always have a
solution.) Design an exhaustive-search algorithm for this problem. Try to minimize the number of
subsets the algorithm needs to generate.
©2021 RMIT University 2
COSC 1285/2123
Practical Exercises
Objective
Students who complete this lab should:
� Learn to implement a fundamental sorting algorithm.
Introduction
In this lab exercise you are to implement selection sort and compare its performance to bubble sort.
Provided Code
SortDemo1.java reads a sequence of white-space separated integers from file and sorts them into
ascending numerical order. SortDemo1.java allows you to sort the input using several different
sorting algorithms. The algorithms were covered in the lecture and in the text book.
The program is divided into the following modules:
file description
SortDemo1.java Code to read data from disk into the set. Also performs timings. No need to modify this
file.
BubbleSort.java Implementation of standard bubble sort. No need to modify this file.
SelectionSort.java Your implementation of selection sort.
Compile the program using the following command:
javac *.java
To run the the sort demo:
java SortDemo1 bubble random.txt
This will run bubble sort on the input file random.txt. To run selection sort, replace bubble
with select.
The SortDemo1.java program supports the following algorithms:
algorithm description
bubble Standard bubble sort algorithm.
select Standard selection sort algorithm.
Task
Your task in this lab exercise is to implement the following sorting algorithm:
Selection sort is to be implemented in SelectionSort.java.
After implementing selection sort, run each of the algorithms (bubble, selection) on the following
test files and compare the run times:
©2021 RMIT University 3
COSC 1285/2123
file description
debug.txt file with few items for testing purposes.
random.txt file with items in random initial order.
nearlysorted.txt file with items nearly ordered.
reversed.txt file with items in reversed sorted order.
fewunique.txt file with very few unique items
©2021 RMIT University 4