Description
COMP9024 Assignment One
In this assignment, you extend the doubly linked list class DList given in the textbook. The subclass is named MyDlist.
You need to implement the following constructors and methods of MyDlist:
1. public MyDlist(). This constructor creates an empty doubly linked list.
2. public MyDlist(String f). This constructor creates a doubly linked list by reading all strings from a text file
named f. Assume that adjacent strings in the file f are separated by one or more white space characters. If f is
“stdin”, MyDlist(“stdin”) creates a doubly linked list by reading all strings from the standard input. Assume
that each input line is a string and an empty line denotes end of input.
3. public static void printList(MyDlist u). This class method prints all elements of a list on the standard output,
one element per line.
4. public static MyDlist cloneList(MyDlist u). This class method creates an identical copy of a doubly linked list
u and returns the resulting doubly linked list.
5. public static MyDlist union(MyDlist u, MyDlist v). This class method computes the union of the two sets that
are stored in the doubly linked lists u and v, respectively, and returns a doubly linked list that stores the union.
Each element of a set is stored in a node of the corresponding doubly linked list. Given two sets A and B, the
union of A and B is a set that contains all the distinct element of A and B. Include the detailed time complexity
analysis of this method in big O notation immediately above the source code of this method as comments.
6. public static MyDlist intersection(MyDlist u, MyDlist v). This class method computes the intersection of the
two sets that are stored in the doubly linked lists u and v, respectively, and returns a doubly linked list that
stores the intersection. Each element of a set is stored in a node of the corresponding doubly linked list.
Given
two sets A and B, the intersection of A and B is a set that contains all the elements of A that are also in B.
Include the detailed time complexity analysis of this method in big O notation immediately above the source
code of this method as comments.
You may assume that in the above methods all the elements of each input set are distinct.
You are not allowed to use any data structures of Java you have not learned so far. In other words, you can use only
the arrays, strings and primitive data types of Java.
Major steps
1. Download the latest JAVA IDE Eclipse.
2. Create a project.
3. Create DList class and copy the code of DList to the class file.
4. Create DNode class and copy the code of DNode to the class file.
5. Create MyDlist class, and copy the sample main method to the class file.
How to submit your code?
Follow this link: https://cgi.cse.unsw.edu.au/~give/Student/give.php? Do the following:
1. Use your z-pass to log in.
2. Select current session, COMP9024 and assn1.
3. Submit your MyDlist.java file that contains only the class MyDlist.
Marking
The full mark of this assignment is 6. Marking is based on the correctness and efficiency of your code. Your code must
be well commented.
Deadline
The deadline is 11:59:59 pm, 1 April.
Late submission
No late submission will be accepted.
COMP9024 Assignment Two
In this assignment, you will implement a class named ExtendedAVLTree.
ExtendedAVLTree extends the AVLTree class to include the following methods:
Public static <K, V> AVLTree<K, V> clone(AVLTree<K,V> tree)
This class method creates an identical copy of the AVL tree specified by the
parameter and returns a reference to the new AVL tree. (3 marks)
For simplicity, we assume that K is int and V is String.
The time complexity of this method must be O(n), where n is the size of the input avl
tree. Put your running time analysis as comments after the code.
public static <K, V> AVLTree<K, V> merge(AVLTree<K,V> tree1,
AVLTree<K,V> tree2 )
This class method merges two AVL trees, tree1 and tree2, into a new tree, and
destroys tree1 and tree2.
The time complexity of your merge method must be O(m+n), where m and n are the
numbers of nodes of the two input AVL trees. Hint: 1. Create a sorted array list
containing all the entries in both avl trees in O(m+n) time. 2. Construct an avl tree
based on the sorted array list in O(m+n) time. Put your running time analysis as
comments after the code. (4 marks)
public static <K, V> void print(AVLTree<K, V> tree)
This class method creates a new window and prints the AVL tree specified by the
parameter on the new window. Each internal node is displayed by a circle containing
its key and each external node is displayed by a rectangle. You need to choose a
proper size for all the circles and a proper size for all the rectangles and make sure
that this method never prints a tree with crossing edges. (3 marks)
All the related classes are in the package net-datastructures-4-0. Please download netdatastructures-4-0, install it on your own computer and create the new class
ExtendedAVLTree in the same package.
You need to read the code of all the related classes in order to understand how the AVLTree
class works.
How to submit?
Follow this link: https://cgi.cse.unsw.edu.au/~give/Student/give.php. Do the following:
1. Use your z-pass to log in.
2. Select current session, COMP9024 and assn2.
3. Submit ExtendedAVLTree.java containing all the code, excluding the code in
datastructures-4-0.
Marking
The full mark of this assignment is 10. Marking will be based on the correctness, time
efficiency and readability of your code.
Deadline
No late submissions will be accepted.
References
1. http://docs.oracle.com/javase/tutorial/2d/index.html.
2. http://www.deitel.com/articles/java_tutorials/20050923/IntroductionToJava2D_Page6
.html.
3. http://docs.oracle.com/javase/tutorial/uiswing/components/frame.html.
COMP9024 Assignment Three
In this assignment, you will implement a task scheduler in Java
using heap-based priority queues.
Background
An embedded system is a computer system performing dedicated functions within a larger mechanical
or electrical system. Embedded systems range from portable devices such as Google Glasses, to large
stationary installations like traffic lights, factory controllers, and complex systems like hybrid
vehicles, and avionic.
Typically, the software of an embedded system consists of a set of tasks
(threads) with timing constraints. Typical timing constraints are release times and deadlines. A release
time specifies the earliest time a task can start, and a deadline is the latest time by which a task needs
to finish. One major goal of embedded system design is to find a feasible schedule for the task set
such that all the timing constraints are satisfied.
Task scheduler
We assume that the hardware platform of the target embedded systems is a single processor with m
identical cores, Core1, Core2, …, Corem. The task set V={v1, v2, …, vn} consists of n independent,
non-pre-emptible tasks. A non-pre-emptible task cannot be pre-empted by another task during its
execution, i.e., it runs until it finishes. Each task vi (i=1, 2, …, n) has four attributes: a unique task
name vi
, an execution time ci
, a release time ri
, and a deadline di(di>ri).
All the execution times, the
release times and deadlines are non-negative integers. You need to design a task scheduler and
implement it in Java.
Your task scheduler uses EDF (Earliest Deadline First) strategy to find a feasible
schedule for a task set. A schedule of a task set specifies when each task starts and on which core it is
executed. A feasible schedule is a schedule satisfying all the release time and deadline constraints.
The problem of finding a feasible schedule for this task scheduling problem is NP-complete. It is
widely believed that an NP-complete problem has no polynomial-time algorithm. However, nobody
can prove it.
First, we introduce two definitions: scheduling point and ready task.
A scheduling point is a time point at which a task is scheduled on a core.
A task vi (i=1, 2, ,,, n) is ready at a time t if tri holds.
The EDF scheduling strategy works as follows:
At each scheduling point ti (titi+1, i=1, 2, …), among all the ready tasks, find a task with the
smallest deadline, and schedule it on an idle core such that its start time is minimized. Ties are
broken arbitrarily.
Since this task scheduling problem is NP-complete, the EDF strategy is used as a heuristic which is
not guaranteed to find a feasible schedule even if a feasible schedule exists.
Example One
Consider a set S1 of 6 independent tasks whose release times and deadlines are shown in Table 1. The
target processor has two identical cores. A feasible schedule of the task set by using EDF scheduling
strategy is shown in Figure 1.
Table 1: A set S1 of 6 tasks with individual release times and deadlines
Task Execution
time
Release time Deadline
v1 4 0 4
v2 4 1 5
v3 5 3 10
v4 6 4 11
v5 4 6 13
v6 5 6 18
Core1 v1 v3 v5
Core2 v2 v4 v6
Time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Figure 1: A feasible schedule for S1
Example Two
Consider a set S2 of 6 independent tasks whose release times and deadlines are shown in Table 2. The
target processor has two identical cores. A schedule of the task set by using EDF scheduling strategy
is shown in Figure 2. As we can see, in the schedule, v6 finishes at time 16 and thus misses its
deadline. Therefore, the schedule is not feasible. However, a feasible schedule, as shown in Figure 3,
does exist.
Table 2: A set of tasks with individual release times and deadlines
Task Execution
time
Release time Deadline
v1 4 0 4
v2 4 1 5
v3 5 3 10
v4 6 4 11
v5 4 9 16
v6 5 10 15
Core1 v1 v3 v5
Core2 v2 v4 v6
Time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Figure 2: An infeasible schedule constructed by the EDF scheduling strategy
Core1 v1 v3 v6
Core2 v2 v4 v5
Time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Figure 2: A feasible schedule for S2
The TaskScheduler class
You need to write a task scheduler class named TaskScheduler. A template of the TaskScheduler
class is shown as follows.
public class TaskScheduler
{
…
static void scheduler(String file1, String file2, int m) {};
…
}
class ClassX {} /** Put all the additional classes you need here */
…
You can define any fields, constructors and methods within the TaskScheduler class. You can also
define additional classes. You must put all the additional classes in the file Taskscheduler,java.
The main method scheduler(String file1, String file2, int m) gets a task set from file1, constructs a
feasible schedule for the task set on a processor with m identical cores by using the EDF strategy, and
write the feasible schedule to file2. If no feasible schedule exists, it displays “ No feasible schedule
exists” on the screen.
Both file1 and file2 are text files. files1 contains a set of independent tasks each of which has a name,
an execution time, a release time and a deadline in that order. A task name is a string of letters and
numbers starting with a letter. Each of the execution times, release times and the deadlines is a string
of digits between 0 and 9. All the release times are non-negative integers, and all the execution times
and the deadlines are natural numbers. The format of file1 is as follows:
v1 c1 r1 d1 v2 c2 r2 d2 … vn cn rn dn
Two adjacent attributes (task name, execution time, release time and deadline) are separated by one or
more white space characters or a newline character. A sample file1 is shown here.
For simplicity, you may assume that all the task names in file1 are distinct.
This method needs to handle all the possible cases properly when reading from file1 and writing to
file2.
All the possible cases are as follows:
1. file1 does not exist. In this case, print “file1 does not exist” and the program terminates.
2. file2 already exists. In this case, overwrite the old file2.
3. The task attributes (task name, release time and deadline) of file1 do not follow the formats
as shown before. In this case, print “input error when reading the attribute of the task X”
and the program terminates, where X is the name of the task with an incorrect attribute.
file2 has the following format:
v1 p1 t1 v2 p2
t2 … vn pn tn
where each vi(i=1, 2, …, n) is the task name, pi
is the name of the core where vi
is scheduled, and ti
is
the start time of the task vi
in the schedule. In file2, all the tasks must be sorted in non-decreasing
order of start times. A sample file2 is shown here.
Time complexity requirement
You need to include your time complexity analysis as comments in your program. The time
complexity of your scheduler is required to be no higher than O(n*log n), where n is the number of
tasks (Hints: use heap-based priority queues). You need to include the time complexity
analysis of your task scheduler in the TaskScheduler class file as comments. There is no specific
requirement on space complexity. However, try your best to make your program space efficient.
net.datastructures-4-0 package
You can use net.datastructures-4-0 where there is a heap-based priority queue class named
HeapPriorityQue.java. Read through its code and understand how it works.
Restrictions
All the other data structures and algorithms that are not in net.datastructures-4-0 must be
implemented in the TaskScheduler class. You are NOT allowed to use any sorting algorithms and
priority queues provided by Java.
How to submit your code?
Follow this link: https://cgi.cse.unsw.edu.au/~give/Student/give.php. Do the following:
1. Use your z-pass to log in.
2. Select current session, COMP9024 and assn3.
3. Submit TaskScheduler.java.
Marking
Marking is also based on the correctness and efficiency of your code. Your code must be well
commented.
The full mark of this assignment is 7 if the time complexity of your scheduler satisfies the abovementioned requirement. Otherwise, the full mark will be 0.
Deadline
The deadline is 11:59:59 pm, 14 May. No late submission will be accepted.
COMP9024 Assignment Four
In this individual assignment, you will implement the compact representation of the compressed suffix trie
ADT, design and implement an algorithm for finding k longest substrings of two DNA sequences.
A template of the compact compressed suffix trie class is shown as follows:
public class CompactCompressedSuffixTrie
{
/** You need to define your data structures for the compressed trie */
/** Constructor */
public CompactCompressedSuffixTrie( String f ) // Create a compact compressed suffix trie from file f
{ }
/** Method for finding the first occurrence of a pattern s in the DNA sequence */
public int findString( String s )
{ }
/** Method for finding k longest common substrings of two DNA sequences stored
in the text files f1 and f2 */
public static void kLongestSubstrings(String f1, String f2, String f3, int k)
{ }
}
The data structures for the compressed suffix trie are not given in the above template. You need to define them
yourself. You may introduce any helper classes and methods to facilitate the implementation of these two
methods.
The constructor creates a compact representation of the compressed suffix trie from an input text file f that
stores a DNA sequence. All the characters of the DNA sequence are A, C, G and T. There is no specific time
complexity requirement for the constructor. However, you need to make it as time-efficient as possible.
Bonus Marks: there are two bonus marks for a correct linear time constructor for the compact compressed
trie.
The findString(String s) method has only one parameter: a DNA pattern s. If s appears in the DNA sequence,
findString(s) will return the starting index of the first occurrence of s in the DNA sequence. Otherwise, it will
return –1. For example, if the DNA sequence is AAACAACTTCGTAAGTATA, then findString(“CAACT”)
will return 3 and findString(“GAAG”) will return –1. Note that the index of the first character of the DNA
sequence is 0.
Time complexity requirement for the method findString(String s): If your findString(String s) method is
slower than O(|s|) (|s| is the length of s), you will get 0 mark for it.
The method kLongestSubstrings(String f1, String f2, String f3, int k) computes the k longest common substrings.
A common substring of two DNA sequences is a substring that appears in both DNA sequences. For example,
GTTAA is a common substring of AAGTTAAAAGT and GTGTTAAAATTGA. The longest common
substring is a substring with the maximum length. For example, GTTAAAA is the longest common substring of
AAGTTAAAAGT and GTGTTAAAATTGA. Note that the longest common substring is not always unique.
Specifically, the method kLongestSubstrings(String f1, String f2, String f3, int k) performs the
following task:
Compute the k longest common substrings of the two DNA sequences stored in the text files named f1
and f2, respectively, and write them to the file f3. The k longest common substrings must be stored in
non-increasing order of their lengths and each common substring starts in a new line with a heading
“i:”, where i is the sequence number of the longest common substring.
For example, assume we have two DNA sequences stored in the files f1 and f2, respectively as follows:
f1=ACGTCCACGGTTTGGATTGAATTT
f2=ACGTAAACGGTTTTTATTGAATTT
After the call kLongestSubstrings( f1, f2, f3, 3), f3 will contain the 3 longest common substrings shown as
follows:
1: ATTGAATTT
2: ACGGTTT
3: ACGT
Time complexity requirement for the method kLongestSubstrings(String f1, String f2, String f3, int k): The
running time of your method kLongestSubstrings(String f1, String f2, String f3, int k) must be at most
O(kmn), where m and n are the sizes of f1 and f2, respectively. Any method with a higher time complexity
will be given 0 mark.
You need to give the running time analyses of all the methods in terms of the Big O notation. Include your
running time analyses in the source file of the CompactCompressedSuffixTrie class and comment out them.
Input exceptions: You can use any reasonable methods to handle incorrect input such as non-DNA symbols in
a DNA sequence.
How to submit?
Follow this link: https://cgi.cse.unsw.edu.au/~give/Student/give.php. Do the following:
1. Use your z-pass to log in.
2. Select current session, COMP9024 and assn4.
3. Submit CompactCompressedSuffixTrie.java
Marking
This assignment is worth 7 marks, excluding the bonus marks. The breakdown is as follows.
1. Constructor: 3 marks or 5 marks for a correct linear time constructor.
2. The method findString(String s): 1 mark.
3. The method kLongestSubstrings(String f1, String f2, String f3, int k): 3 marks.
Marking will be based on the correctness, time efficiency and readability of your code.
Deadline: 11:59:59pm, 4 June
No late submission will be accepted!
