CSE204: Complexity ofAlgorithms
Coursework Assessment 2
Department of Computer Science & Software Engineering Xi’an Jiaotong-Liverpool University
Assessment Information
Assessment Number 2
Contribution to Overall Mark Submission deadline
Assessment Objectives
15%
15 May
This assessment aims to test the followings:
• Yourfluencyonutilizingabstractdatatypessuchaslists,graphsandtreesinconjunction with classical problems such as search, insertion, removal, and sorting, etc.
• Your ability to comprehend, implement an algorithm in a high-level language and perform its complexity analysis.
Instructions
• ThisisanINDIVIDUALcoursework.Itisrecommendedtowriteyourprogram
in JAVA.
• Write a short report (up to 5 pages) on performance analysis of your algorithms.
• The implementation code and your report should be submitted as a soft copy on ICE. Only the “.zip” file type is acceptable.
• LatesubmissionswillbepenalisedaccordingtotheXJTLUUniversityrules.
1
Project 1 (Group 1)
Write a simple graphical program to show an AVL tree. An example is shown in Fig. 1.
a) Your program should receive the input of the elements from the keyboard and then
generate an AVL tree. The input size is limited to 32 to ensure that the hight of the
tree is not too high.
b) Your program should also support the methods (search, insert, remove) of the
ordered dictionary ADT using the AVL tree. When you run any method, your
program should draw the changes of the tree step by step.
c) Perform a careful experimental analysis of the running times for your insertion and
removal procedures of the ordered dictionary ADT. Plot their running times as a function of the input size and discuss whether observed curves can be expected by the theoretical analysis. (In this step, the input can be a build-in data. The limitation of input size should be ignored, and the graph should not be drawn when you are testing the running times.)
Figure 1. An example of a simple graphical program of a tree (This tree is not an AVL tree).
Design and2implement one studied 𝑂𝑂(𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛) run2 ning time sorting algorithms and one studied O(n ) running time sorting algorithms.
Project 2 (Group 2)
a) You can choose any 𝑂𝑂(𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛) and any 𝑂𝑂(𝑛𝑛 ) sorting algorithms to implement.
b)
c)
Your program should generate the following types of inputs to evaluate these two
algorithms.
1). a set of random integers.
2). a set of almost sorted integers (only a few elements are not correctly sorted). 3). a set of reverse ordered integers.
Write a short report describing these programs and perform a careful experimental analysis of the running times for different inputs.
2
Project 3 (Group 3)
Implement a system for solving the Knapsack problem.
a) Your system should solve 0 − 1 knapsack problems by using dynamic programming.
The input of the program can be fixed in the code or manually input by keyboard.
b) Design and implement also a greedy algorithm that solves the 0 − 1 knapsack
problem approximately.
c) Perform an experimental analysis to test these two algorithms. Discuss the trade-
offs between finding exact and approximate solutions. Write a short report on your experimental analysis discussing whether observed performances in terms of running times and accuracy of solutions can be expected theoretically.
3