COMP9024 Notices

Your Final Result

Posted by Hui Wu Wednesday 22 May 2019, 09:03:34 PM.

Dear All,

Some of you have already noticed that your exam marks and final results had been released. To view your results, go to https://cgi.cse.unsw.edu.au/~give/code/login.php?app=/~give/Student/give.php . The field "exam" and "final" show your exam marks and final result for COMP9024, respectively. If your final result is at least 50, you have passed this course.

Congratulations to the following students who got HD:

1. Cheng, Chun-Chu
2. Fernando, Mihindukulasuriya Dilanka Gayan
3. Thirurajah, Samuel Harishan
4. Wang, Zhounan
5. Yu, Yangbo
6. Zheng, Yuquan
7. Li, Xin
8. Ren, Jiawei
9. Jiang, Yiwen
10. Liu, Yu
11. Zhou, Ruijun
12. Shang, Mengdi
13. Li, Zitong
14. Thekkedath, Anagha Narayanan
15. Rong, Zeyang
16. Zhou, Zhuolin
17. Punchhi, Sahil
18. Sharma, Manavh
19. Yue, Jiacheng
20. Shetty, Rishabh
21. Limarga, Raynaldio
22. Huang, Siyang
23. Deng, Benjamin Wen Xi
24. Yang, Zhichao
25. Yu, Haifeng
26. Chui, Marvin

Both Chun-Chu and Dilanka got full marks, and next few top achievers are very close to the full marks. Well done guys!

If your final result is lower than but close to 50, or you have applied for Special Consideration, or you have other special reasons, you will be given a supplementary exam. The supp exam will be held during Monday 27 May – Friday 31 May . You will be informed of the supp exam details (time, date and venue) soon. The scope is similar to that of final exam.

Lastly, I wish you all the best in your future studies.

Hui

Check Your Assignment Marks

Posted by Hui Wu Friday 17 May 2019, 02:50:38 PM.

Dear All,

Please check all your assignment marks (assn1~assn4 fields). If you have any issues, contact me by this Sunday.

Cheers,

Hui

Assignment 4 Result

Posted by Sidra Malik Monday 13 May 2019, 07:40:16 PM, last modified Thursday 16 May 2019, 09:12:51 AM.

Dear All,

Assignment 4 has been marked. Please go through the comments first before sending an email to LIC or me.

Here is the Marking Guideline:

• CreateEmptyGraph() 0.2
• InsertEdge(Graph g, Edge *e) 0.5
• DeleteEdge(Graph g, Edge *e) 0.5
• ReachableVertices(Graph g, Vertex *v) 2
• ShortestPath(Graph g, Vertex *u, Vertex *v) 4
• FreeGraph(Graph g) 0.8
• ShowGraph(Graph g) 2

Incorrect Time Complexity , 20% of the full mark is deducted

Compilation error - maximum 40% marks will be given based on your implementation. I have NOT marked individual function if there is a compilation error. Since there is no separate placeholder to comment on this, you might find the comment in any of the functions. Once you send me the fix, I will remark your submission. Please note no remarking will be done for students who have compilation error + minimal assignment specs completed.

Segmentation Fault - Check your code on CSE MACHINE - using gcc compiler. Fix the segmentation fault and email me the error along with the corrected version. This is only for students whom I have mentioned in comments to do so.

Function Not Implemented - total loss of marks for that function

Incorrect Output - There is also a penalty if the function does not print a correct output: i.e. does not perform as supposed. 50% penalty

If you have any query/fixing error regarding Assignment 4 marks, please send it to me till tomorrow i.e. 14th May, 2019.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Edit: 16/05/2019 : To the students who sent me queries, all your queries have been addressed but unfortunately the system is down since yesterday and I cannot update your marks. I will update and send you notifications (in reply to your emails) once the system is up again. Thanks a lot.

Last Announcement about Exam

Posted by Hui Wu Monday 13 May 2019, 02:07:05 PM.

Dear All,

Just a reminder that the final exam starts at 8:45am tomorrow. Please remember your CSE lab and seat number.

After logging in using you zPass, you will see the exam paper and a window. On the window, after typing "ls", you will find a text file named comp9024.txt. Just use comp9024.txt to enter your solutions to all the questions in Part II. Text editors emacs, gedit, vi, vim are available. Use your best editor to enter your solutions. AT the end of exam, please remember to save the file comp9024.txt. Also remember to periodically save it.

For all the questions in Part I, write your answers in the booklet. Since the booklet has only 8 pages, use it sparely.

Good luck!

Hui

Incorrect Algorithm for the Longest Path Problem in Problem Set 9

Posted by Hui Wu Sunday 12 May 2019, 02:14:05 PM, last modified Sunday 12 May 2019, 03:06:28 PM.

Dear All,

The previous algorithm based breadth-first search is incorrect. I have replaced it by a topological sort based algorithm.

In order to find a longest path from u to v, the following requirement must be met:

- For each predecessor x of v, before the longest path from u to x is computed, the longest path from u to each immediate predecessor of x must be computed.

Only a topological order meets the above requirement.

Many thanks to Weihuan Cheng who got 1 bonus mark for pointing out the error.

Sorry for the mistake!

Hui

Writing Algorithms for Part II Questions

Posted by Hui Wu Saturday 11 May 2019, 10:53:47 AM.

Dear All,

For each question in Part II, you need to write an algorithm with a specific time complexity requirement and analyse its time complexity. Some questions ask you to give complete code, which means you cannot call any algorithm without giving its pseudo code. For other questions, they explicitly state that you can call any algorithms given in the lecture notes. In the latter case, you can write an algorithm like this:

Algorithm Example()

{

...

Perform in-order traversal on the tree to create a list of all the items sorted in non-decreasing order of keys;

...

}

Cheers,

Hui

Your Lab and Seat Number

Posted by Hui Wu Saturday 11 May 2019, 10:45:18 AM.

Sorry for the mistake in the previous notice. You can find your CSE lab and seat number here https://cgi.cse.unsw.edu.au/~cs9024/19T1/seating/final/register.cgi/allocations .

Cheers,

Hui

More about Final Exam

Posted by Hui Wu Friday 10 May 2019, 09:08:31 PM, last modified Sunday 12 May 2019, 02:17:18 PM.

Dear All,

The final exam will be held in CSE labs. Please find your lab and seat number on myunsw.

1. Please be seated in the lab at 8:45am next Tuesday. Use your zPass to log into the machine. You have 10 minutes reading time. You start writing at 9:00am and finish the exam at 12 noon.

2. The exam paper is a pdf file. You write all the answers for Part I and intermediate results in the booklet given to you, and type all the answers for Part II in a text file named comp9024.txt by using a text editor. The text file comp9024.txt does not exist. You need to create one.

3. Remember to periodically save comp9024.txt, and save it before the exam finishes. There is not explicit process for submitting comp9024.txt. I will collect comp9024.txt after the exam.

If you are not familiar with CSE lab environment, do the following:

1. Download tigervnc. The link for downloading it is given here https://taggi.cse.unsw.edu.au/FAQ/Really_quick_guide_to_VLAB/. Make sure you download the correct .exe file for your machine.

2. Install tigervnc on your machine.

3. Connect to CSE lab using your zPass as shown in the following picture:

The exam environment is exactly the same as this. You can choose any editor supported by CSE lab machines in the exam.

Cheers,

Hui

Errors in Solution to Problem 8 of Problem Set 4

Posted by Hui Wu Thursday 09 May 2019, 10:59:49 PM.

Dear All,

There were two errors in the previous solution that can be easily found. I just uploaded the correct solution. Thanks to Cheng Chen.

Cheers,

Hui

Consultations for Exam

Posted by Hui Wu Thursday 09 May 2019, 10:10:02 PM.

Dear All,

I have arranged two consultation sessions:

Session one: 2-5pm this Friday (tomorrow)

Session two: 9am -12 noon next Monday

The venue for both sessions is K17-508 Consultation Room (the small room beside the lift). If I'm not there, call me on ext 56572 using the phone on the wall.

Cheers,

Hui

Correction to the Solutions to Problem 1.a of Problem Set 4

Posted by Hui Wu Wednesday 08 May 2019, 02:45:31 PM.

Dear All, the answer was wrong. The correct answer is 22. The mistake is in the mapping n(h) to a Fibonacci number. The correct mapping is n(h)=F_{h+3}+1. The previous mapping was n(h)=F_{h+2}+1. Many thanks to Samuel Thirurajah who got 1 bonus mark for pointing out this mistake.

Best,

Hui

MyExperience Surveys

Posted by Hui Wu Tuesday 30 April 2019, 12:44:33 PM.

Dear All,

Your feedback is extremely important for me. Could you fill up the surveys asap? The deadline is this Sunday 2019-05-05 23:59. The link is here https://unsw.bluera.com/unsw/ . Your response is much appreciated.

Cheers,

Hui

Final Exam Details

Posted by Hui Wu Tuesday 30 April 2019, 08:50:50 AM.

Dear All,

The final exam will be held in CSE labs 8:45 am-12 noon Tuesday 14 May. Please check your lab and seat number here: https://cgi.cse.unsw.edu.au/~cs9024/19T1/seating/final/register.cgi/allocations

Log in with your zID and zPass.

Cheers,

Hui

Queries regarding Assignment 3

Posted by Sidra Malik Monday 29 April 2019, 01:18:32 PM, last modified Tuesday 30 April 2019, 06:45:21 PM.

Dear Students,

There are few things I need you to check before you email me regarding the assessment.

The marking guide (as provided by LIC) is as follows:

1. If you have implemented Binary Heap, not Binomial, maximum marks are 7.
2. If your program does not compile/execute, you are marked according to the code. In this case max marks awarded cannot exceeded 40% of the total.
3. If you have implemented time complexity, not using a scheduling queue or the search leads to a time complexity of O( mn+nlog n), you would be awarded 0.

Please refer to comments section first. The reason why your marks have been deducted is clearly mentioned there.

I have marked (compiled and executed) your code on CSE machines. Please check your codes on cse machines first, I am happy to entertain any queries where a segmentation/ compilation/execution error could be fixed with any optional field your program needs. In this case you will have to email me the fix + screenshots attached in the email.

Any logical/syntax errors at this point will not be entertained.

Edit [30/04/2019]: I am receiving heaps of emails, all the queries/emails will be addressed by the end of this week. If you have not received a reply from me please be patient. When I fix your marks, i will email you. Please avoid sending emails again and again. You may email LIC only if you are not satisfied with your mark.

regards

Sidra

Re: Assignment 3 Result

Posted by Hui Wu Monday 29 April 2019, 12:19:41 PM.

Dear All,

If you have any questions about your assignment 3 result, please send your query to Sidra Malik (email: sidra.malik@unsw.edu.au) who marked Assignment 3. Thanks.

Hui

Assignment 2 Result

Posted by Hui Wu Saturday 27 April 2019, 10:49:41 AM.

Dear All,

I have processed all the queries about assignment 2 I have received. Please check your result again using this link: https://cgi.cse.unsw.edu.au/~give/code/login.php?app=/~give/Student/give.php

If you still have queries about assignment 2, please contact me asap.

Assignment 3 marking is delayed due to Umair's unexpected family issue. Sidra Malik has placed Umair. She is busy marking assignment 3 and expected to finish soon.

Cheers,

Hui

Last Lecture Tonight

Posted by Hui Wu Tuesday 23 April 2019, 10:31:47 AM.

Dear All,

We have one more lecture tonight, at the same time and venue as before. I will finish randomised algorithms and then discuss the final exam.

Cheers,

Hui

The Adjacency List Representation

Posted by Hui Wu Sunday 21 April 2019, 09:06:20 AM.

Dear All,

In the lecture notes, the first level of pointers point to a linked list of adjacent vertices of each vertex and all the pointers are stored in a one dimensional array. If you use this array structure, "holes" may be created. A "hole" is a set of contiguous array cells that do not store a valid vertex. You need to find a way for handling holes.

You are not restricted to use this array structure. As always, you can explore other possible structures for storing those pointers. For example, how about using a linked list to store those pointers? What are the pros and cons of using a linked list and an array?

As I said in the previous lecture, you need to have a clear global picture of all the data structures and verify their efficiency before start coding.

Cheers,

Hui

Bonus marks in Assignment 2

Posted by Hui Wu Friday 19 April 2019, 02:13:32 PM.

Dear All,

If you implemented a linear-time algorithm for intersection and union, please email Umair so that your bonus marks will be recorded. Thanks.

Have a good long weekend!

Hui

Assignment 2 Result

Posted by Hui Wu Wednesday 17 April 2019, 10:17:45 AM.

Dear All,

You can view your result now. To view your result,

1. either go to the assignment page, click on "Assignment Specification" of Assignment 2 and then "Collect Assignment", or

2. go to https://cgi.cse.unsw.edu.au/~give/code/login.php?app=/~give/Student/sturec.php using your zPass and select current session and enter COMP9024.

If you have any questions, contact Umair (email:u.tariq@unsw.edu.au).

Cheers,

Hui

Assignment Four

Posted by Hui Wu Sunday 14 April 2019, 10:51:15 AM.

Dear All,

I have released Assignment Four. If you have completed Assignment Three, you can start working on the last assignment now.

I will discuss it in a lecture next week.

Cheers,

Hui

Sample Output of main() in Assignment 3

Posted by Hui Wu Friday 12 April 2019, 05:58:07 PM.

Dear All,

I added a pdf file showing sample output of main(). Notice that I changed the attributes of task 8 in samplefile4.txt from 8 6 5 19 to 8 5 5 18 as there exists an infeasible EDF schedule for the previous samplefile4.txt on two cores. Thank Yao Lu for pointing this out.

Cheers,

Hui

The Number of Cores in Assignment 3 Is Not A Constant

Posted by Hui Wu Saturday 06 April 2019, 11:02:57 AM.

Dear All,

Please note that the assignment does not assume that the number of cores m is a constant. Therefore, you cannot assume m is a constant in the time complexity analysis of your tasks scheduler.

I explained that you could use two priority queues. You can find out that using these two priority queues are not sufficient to make your scheduler running in O(n log n) time. If searching in m cores for the smallest start of a ready task with the smallest deadline takes O(m) time, the time complexity of the task scheduler will be O( n(m+log n)) which is not the same as O(n log n) in general. In order to remove m from O( n(m+log n)), your algorithm for searching in m cores for the smallest start of a ready task with the smallest deadline should take O(log m) time.

Cheers,

Hui

Final Exam

Posted by Hui Wu Friday 05 April 2019, 09:26:08 PM.

Dear All,

The final exam is a closed book, written exam with a three-hour duration. The exam paper has two parts:

Part I: Basic data structures and algorithms (40 marks)

Part II: Design and analysis of algorithms (60 marks)

There are 8 questions in Part I and 5 questions in Part II.

Questions in Part I are about basic data structures and algorithms and each question in Part II asks you to write an algorithm to solve a problem and analyse the time complexities of your algorithm.

Sample questions in Part I:

Q1 Draw the frequency array and Huffman tree for the following string:

"dogs do not spot hot pots or cats"

Q2 What does a splay tree look like if its entries are accessed in increasing order of their keys?

Sample questions in Part II:

Q3 An vertex-weighted DAG (directed acyclic graph)is the DAG where each vertex has a weight. The length of a path from a vertex u to a vertex v is the sum of all the vertex weights of the path. A shortest path from a vertex u to a vertex v is the path with the minimum length. Describe an algorithm with O(m+n)time complexity for finding a shorted path from a vertex u to a vertex v in a vertex weighted DAG G, and show why your algorithm takes O(m+n) time.

Q4 Show how to modify the KPM pattern matching algorithm so as to find every occurrence of a pattern string P that appears as a substring in T, while still running in O(n+m) time. (Be sure to catch even those matches that overlap.)

You write algorithms in pseudo code.

As I said several times, the problem sets are intended to help you understand course material and prepare for the final exam. So please make best efforts to solve problems in the problem sets.

Cheers,

Hui

Assignment 1 Result

Posted by Hui Wu Sunday 31 March 2019, 07:59:05 PM.

Dear All,

You can view your result now. To view your result,

1. either go to the assignment page, click on "Assignment Specification" of Assignment 1 and then "Collect Assignment", or

2. go to https://cgi.cse.unsw.edu.au/~give/code/login.php?app=/~give/Student/sturec.php using your zPass and select current session and enter COMP9024.

If you have any questions, contact Umair (email:u.tariq@unsw.edu.au).

Cheers,

Hui

Errors in MyTaskScheduler.c

Posted by Hui Wu Sunday 31 March 2019, 11:30:31 AM.

Dear All,

There are errors in the function newHeapNode(). In HeapNode *newHeapNode(int k, int n, int c, int r, int d, ...), in addition to the attributes of the task stored at a node, you need to define other parameters depending on your design. I have fixed the errors. Please download the new assignment specs. Thanks Rui Xu for pointing out the errors.

As you can see, there is no specific design constraints on the binomial heap. However, your whole algorithm for task scheduling must meet the O( n log n) time complexity requirement.

Cheers,

Hui

Assignment 3

Posted by Hui Wu Friday 29 March 2019, 04:31:09 PM.

Dear All,

Assignment 3 is available. The deadline is 23:59 Wed 17 April. Please start working on it asap.

Cheers,

Hui

More on Assignment 2

Posted by Hui Wu Saturday 23 March 2019, 05:54:30 PM.

Dear All,

I have added the following:

1. Sample code for testing AVLTreesUnion() and AVLTreesIntersection() to the main.

2. File1.txt.

3. Both AVLTreesUnion(T1, T2) and AVLTreesIntersection(T1, T2) do not make any change to T1 and T2.

Please download the specs and MyAVLTree.c.

Cheers,

Hui

Assignment 2 Extension

Posted by Hui Wu Friday 22 March 2019, 02:52:42 PM.

Dear All,

Due to a number of requests, I have extended the deadline of Assignment 2 by three days. The new deadline is 23:59:59 Wed 3 April.

There are two typos in the previous assignments specs. The time complexities of Search(), InsertNode() and DeleteNode() should be O(log n).

I have changed the requirements of PrintAVLTree(). Now you need to print the height of each item as well.

Cheers,

Hui

Corrections to the Solutions to Problem Set 4

Posted by Hui Wu Thursday 21 March 2019, 12:28:14 PM.

Dear All,

The previous solutions to Problem 1 are partially correct, and the previous solution to Problem 4 does not consider AVL trees. I have fixed all the issues and uploaded the new solutions. Sorry for the errors.

Hui

Examples of AVL Intersection and Union

Posted by Hui Wu Wednesday 20 March 2019, 05:51:15 PM.

Dear All,

I have added examples to the assignment specs illustrating the AVL tree intersection and union.

Cheers,

Hui

Absent between 2pm and 3:30pm this afternoon

Posted by Hui Wu Friday 15 March 2019, 01:34:31 PM.

Dear All,

I have to attend Engineering Faculty Thesis Working Party Meeting from 2pm to 3:30pm. I will be in my office for consultation between 3:40pm to 6:40pm.

Cheers,

Hui

No Duplicate Element in Each Input Set in Assignment 1

Posted by Hui Wu Monday 11 March 2019, 05:21:49 PM.

Dear All,

I have made it clear in the assignment specs shown as follows:

For simplicity, you may assume that all the elements of each input set are distinct for both set union and set intersection. Therefore, you do not need to check if a set contains duplicates.

Cheers,

Hui

Eclipse

Posted by Hui Wu Friday 08 March 2019, 06:30:07 PM.

Dear All,

If you have any issues in installing Eclipse for C/C++, you may read this page: https://www3.ntu.edu.sg/home/ehchua/programming/ho... .

You need to install a C compiler before you can use Eclipse.

Cheers,

Hui

Time complexity analysis in Assignment 1

Posted by Hui Wu Wednesday 06 March 2019, 08:50:35 AM.

Dear All,

For the time complexity analysis of each function, you do not need to give the worst-case number of primitive operations line by line. Instead, give a summary of the time complexity of each major component (typically loop) and the total time complexity of the function.

Cheers,

Hui

Problem Sets

Posted by Hui Wu Friday 22 February 2019, 10:53:46 AM.

Dear All,

There are two problem sets this week.

As I said in the lecture, the problem sets are intended to help you understand the course material better and prepare for the final exam. You need to make efforts to work out your own solutions to all the problems before reading the solutions released.

Cheers,

Hui

Errors in Example 2 (Slide 39 in Introduction to C)

Posted by Hui Wu Thursday 21 February 2019, 11:08:32 PM.

1. Stu should be S.

2. Add "include <stdlib.h> as exit() is included in this header file.

3. Change "ch=getche()" to "ch=getchar()" as getche() is not a standard function.

I have fixed all the errors and updated both pdf file and ppt file. Sorry for the errors.

Hui

Problem Set

Posted by Hui Wu Wednesday 20 February 2019, 11:52:48 AM.

Dear All,

The first problem set is available. The solutions are also provided. Work out your own solutions first before reading my solutions.

Cheers,

Hui

Lecture Recording

Posted by Hui Wu Tuesday 19 February 2019, 11:36:17 PM.

Dear All,

The first lecture recording is available now. On the left pane, click on Lecture Recordings and it will take you to the Moodle site for this course. After you sign in using your zPass, you will find the button Lecture Recordings. Notice that the Moodle site contains lecture recordings only. Everything else is on this site.

Cheers,

Hui

Lecture slides for Week 1

Posted by Hui Wu Monday 18 February 2019, 10:52:40 PM.

Dear All,

The lecture slides for this week are available. The URL of COMP9024 is https://webcms3.cse.unsw.edu.au/COMP9024/19T1/ or

http://www.cse.unsw.edu.au/~cs9024.

See you tomorrow at 6pm at CLB 7.

Cheers,

Hui Wu

Welcome

Posted by Hui Wu Friday 15 February 2019, 03:35:04 PM.

Dear COMP9024 Students,

Welcome to COMP9024!

The course website is https://webcms3.cse.unsw.edu.au/COMP9024/19T1/

Please read the course outline. The lecture material will be available soon.

Cheers,

Hui Wu