代做CSCI203、代写Python/c++编程语言

日期：2024-02-01 09:22

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 1 of 9

Assignment 2 (20% of total marks)

Due date: 15 February 2024, Thursday

Scope:

The tasks of this assignment cover the data structure and algorithm. The assignment

covers the topics discussed in topics 3 and 4.

The assignment is divided into two parts – Part One covers the theoretical aspect of the

materials discussed during classes, and Part Two covers the practicality of the concepts.

The total mark for Part One is 75, and Part Two is 25.

Assessment criteria:

Marks will be awarded for:

Correct,

Comprehensive, and

Appropriate

application of the materials covered in this subject.

Marks:

Total mark: 100

Weightage: 20% of total subject mark

School of Computing and Information Technology University of Wollongong

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 2 of 9

Assignment Specification:

Part A: (75 marks)

Question 1 (25 marks)

a. The INORDER traversal output of a binary tree is A,B,N,O,R,M,A,L,L,Y and the

PREORDER traversal output of the same tree is Y,N,A,B,M,O,R,L,A,L. Construct the

tree and determine the output of the POSTORDER traversal output. (6.0 marks)

b. Given the following undirected graph:

Represent the graph as:

(i) Adjacency matrix (3.0 marks)

(ii) Adjacency list (3.0 marks)

(iii) Incidence matrix (3.0 marks)

c. Starting with an empty 2-4 tree, construct a 2-4 tree with the following keys. Show

the major working steps.

14, 12, 11, 13, 16, 15

(10.0 marks)

School of Computing and Information Technology University of Wollongong

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 3 of 9

Question 2 (25 marks)

Do a dry run on the two algorithms (ALGORITHM 1 and ALGORITHM 2) shown

below.

ALGORITHM 1

End of function A2

Note: the function ENQUEUE only inserts a new element in the

queue if this element is different from NULL.

School of Computing and Information Technology University of Wollongong

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 4 of 9

a) Briefly explain what the purposes of the two algorithms are and state the

asymptotic run-time complexity of each of the algorithms.

b) For the following Binary Search Tree (BST):

What is returned by the function call A1(root)?

(5.0 marks)

c) For the Binary Search Tree (BST) in part (b), provide a detail analysis on

the run-time complexity of the ALGORITHM 2, as explained in lecture.(5.0

marks)

d) Re-write the function A2, in pseudocode, using recursive function calls. You

may not use any form of iteration. (10.0 marks)

e) For a general Binary Search Tree (BST) of N elements, which of the two

algorithms A1 and A2, should you use? Give your choice and explain your

reasoning. (5.0 marks)

School of Computing and Information Technology University of Wollongong

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 5 of 9

Question 3 (25 marks)

The data structure shown in Figure 1 depicts an implementation of a list of two

lists, that is, two linked list joined into one. In this example, the data structure is

implemented to group two separate lists of numbers, one consists of lists of even

numbers and the other consists of lists of odd numbers.

Two types of linked list are used in the above implementation. The node of the

main list (highlighted in grey) consists of a content field, a next node field, and a

next list field. The content node holds a value 0 for an odd list and a value 1 for

an even list. The node also contains two reference fields. The first is a ‘next node’

that links to the first node of a secondary list, and the second is a ‘next list’ that

links to the next link list.

The node of the secondary list (non-highlighted) consists of a content field and a

next node field. For an even list, the content holds an even number and for an

odd list, the content holds an odd number. The node has a ‘next node’ field that

link it to the next secondary list node.

Next Node

Next List

head

Next List

Next Node

Node from main list: Node from secondary list:

Next Node

Figure 1: A list of two lists

School of Computing and Information Technology University of Wollongong

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 6 of 9

In a single linked list implemented in Java, this is the definition of a node:

class Node {

int data;

Node nextNode;

// Constructor to create a new node

// nextNode is by default initialized as null

Node(int d) { data = d; }

}

a) Assuming that the above definition is kept for the nodes of the secondary

lists, device a new definition of node for the nodes of the main list. Call this

type of node MainNode and use the names of pointers NextNode and NextList

respectively in your implementation. (5.0 marks)

b) Write the pseudocode of the function INSERT(head,x) that inserts a new

number in this data structure. If the number is even it must go to the second

secondary list, the list that starts with node 1 in the main list. Otherwise, it

must go to the first secondary list. Assume the data structure already has

the main list created and numbers are inserted at the start of the secondary

list. (5.0 marks)

c) Write the pseudocode of the function SEARCH(head,x) that returns TRUE if

the number x is in the data structure (in any of the secondary lists) and

FALSE otherwise. (5.0 marks)

d) Write the pseudocode of the function DELETE(head, b) that receives as input

arguments the head of the last of two lists and a Boolean value. The function

DELETE(head,b) deletes one of the main nodes. If b equals 0, then the node

storing number 0 is deleted. Otherwise, the main node storing number 1 is

deleted. Consider the following cases: the main list is empty and it has only

one node (node 0 or 1). (10.0 marks)

School of Computing and Information Technology University of Wollongong

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 7 of 9

Part B: (25.0 marks)

Your task for this assignment is to investigate some of the properties of queues.

You should write a Java, C++, or Phyton program which simulates the queuing

system in an email server.

Queues are commonly used in network systems. For example, e-mail is placed in

queues while it is waiting to be sent and after it arrives at the recipient’s mailbox.

A problem occurs, however, if the outgoing mail processor cannot send one or

more of the messages in the queue. For example, a message might not be sent

because the recipient’s system is not available.

Write an e-mail simulator that processes mail at an average of 20 messages per

minute. As messages are received, they are placed in a queue. For the simulation,

assume that the messages arrive at an average rate of 30 messages per minute.

Remember, the messages must arrive randomly, so you will need to use a random

number generator to determine when messages are received.

Each minute, you can dequeue up to 20 messages and send them. Assume that

up to 25% of the messages in the queue cannot be sent in any processing cycle.

Again, you will need to use a random number to determine whether a given

message can be sent. If it cannot be sent, put it back at the end of the queue or

enqueue it.

Run the simulator for 15 minutes, tracking the number of times each message

had to be requeued. At the end of the simulation, print the statistics that show:

1 The total messages processed.

2 The average arrival rate, that is, the average number of messages arriving

per minute.

3 The average number of messages sent per minute.

4 The average number of messages in the queue in a minute.

5 The number of messages sent on the first attempt, the number of messages

sent on the second attempt, and so forth.

6 The average number of times messages had to be requeued (do not include

the messages sent the first time in this average.)

NOTE: Since the question is to assess your understanding of the concept of

Queue, you are NOT allowed to use the library of the language that implement

queue. You need to write the codes (implementation) of Queue for this exercise.

(See point (iii).)

School of Computing and Information Technology University of Wollongong

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 8 of 9

Sample Output:

Please enter the total minutes to run: 30

Total number of messages processed : 565

Average arrival rate : 29.60

Average number of messages sent per minute : 28.7

Average number of messages in the queue per minute : 65.07

Number of messages sent on 1st attempt : 391

Number of messages sent on 2nd attempt : 87

Number of messages sent on 3rd attempt : 18

Number of messages sent on 4th attempt : 4

Number of messages sent on 5th attempt : 2

Average number of times messages had to be requeued : 1.30

Note: These are just sample answers to show the output format required from

your program. They are NOT necessarily the output that your program must

produce because the numbers shown were randomly generated.

Standard Requirements for Part B (Programming question):

(i) Java Version – JDK 6 update 17 or higher (Using Windows), or

(ii) C++ / C compiler – g++ 4.0 or higher (Using Windows or UBUNTU). In the event

that you use UBUNTU via VM, be careful with the memory function of the language

and make sure that the functions are used properly and do not cause any

segmentation error when the codes are compiled in Windows environment.

(iii) All coding must be your own work. Standard libraries of data structures and

algorithms such as STL may not be used.

(iv) Programs should be appropriately documented with comments.

(v) Execute your program and screen-capture the output. Include in your submission

all source code and libraries plus the screen-captures.

(vi) Students are to place all compilation and instructions on how to run the program

inside a readme.txt file. Your lecturer will refer to this file when marking. Without

a readme.txt or clear instructions for compilation, your lecturer will compile based

on his/her computer setting; any incompatibility, will deem as failure to compile

the program.

(vii) Submission filenames are to follow the naming convention given in the submission

instruction below. Do not use your own filename.

School of Computing and Information Technology University of Wollongong

CSCI203 – Data Structures and Algorithm, 2024 S1

SCIT, University of Wollongong, copyright 2024

Page 9 of 9

Submissions

This assignment is due by 9:00 pm Singapore time on Thursday, 15 February 2024.

For Part A, type or hand-written your answer for each question in a MS Word or

equivalent document format and save it in a pdf formatted file, name your file as

YourUOWStudentNumber-A2-SolPartA.pdf.

For Part B, the name of your program should be QueueSim.cpp, QueueSim.java, or

QueueSim.py depending on the programming language that you use to develop

your program. Execute your program and screen capture your output. Next, zip

your source code, libraries, readme.txt together with your screen capture and name

your file as YourUOWStudentNumber-A2-SolPartB.zip.

Zip together YourUOWStudentNumber-A2-SolPartA.pdf and

YourUOWStudentNumber-A2-SolPartB.zip and name your file as

YourUOWStudentNumber-A2.zip. Do not use your own filename.

All assignments that do not satisfy the submission requirements listed above will

not be evaluated and will be returned to the students with 0 marks.

Submit the files YourUOWStudentNumber-A2.zip through Moodle in the following

way:

1) Access Moodle at http://moodle.uowplatform.edu.au/

2) To login use a Login link located in the right upper corner the Web page or in

the middle of the bottom of the Web page

3) When successfully logged in, select a site CSCI203 (SP124) Algorithms and

Data Structures

4) Scroll down to a section Submissions of Assignments

5) Click at Submit your Assignment 2 here link.

6) Click at a button Add Submission

7) Move a file, for example, YourUOWStudentNumber-A2.zip into the

submission area. You can drag and drop files here to add them. You can also

use a link Add…

8) Click at a button Save changes,

9) Click at a button Submit assignment,

10) Click at the checkbox with a text attached: By checking this box, I confirm that

this submission is my own work, … in order to confirm authorship of your

submission,

11) Click at a button Continue.

A policy regarding late submissions is included in the subject outline.

Only one submission per student is accepted.

Assignment 2 is an individual assignment, and it is expected that all its tasks will be

solved individually without any cooperation with the other students. Plagiarism is treated

seriously. Students involved will likely receive zero. If you have any doubts, questions,

etc. please consult your lecturer or tutor during lab classes or over e-mail.