讲解python数据结构算法、辅导ython数据结构

DataStructures andAlgorithms Spring

2018

Assignment 2(Due11:59PM,Friday, 4rdMay, 2018) (10 marks)

Objectives

1. Design and implement a discrete event simulation

2. Choose and implement appropriate data structures

3. Adapt standard algorithms to a specific problem

Task

Consider the scenario of a license service center. Suppose two services are provided: applying for a new license

(Service 1) and renewing an existing license (Service 2). There are three counters (1-3) for Service 1 and three

counters (4-6) for Service 2. The customers are categorized based on the type of service they are asking for and

each customer is given a ticket number. Each counter serves the customers asking for that particular service,

following the order of their ticket numbers. If at the moment there is no customer for that service, the corresponding

counter will help serve the customers asking for the other service. For example, Counters 1-3 serve the available

customers asking for Service 1; if there is no customer for Service 1, Counter 1-3 help serve the customers asking

for Service 2; and vice versa. Please write a single program which simulates the queuing and service of the customers in this license service

center. Program

Your program should choosetheproperqueuestrategyandrundiscrete event simulation. The simulation should

start at time 0 and run until all customers have been served. Your program should be readable and well

commented. Data Structures and Algorithms

Part of the purpose of this subject is to gain an in-depth understanding of data structures and algorithms. As

such, all programming tasks in this subject require you to choose appropriate data structures and

algorithms, and to implement them yourself. You may not take advantage of any built in data structures

more complex than an array, but instead should provide your own implementation. The use of STL, Java

Collection, or any collection framework in your language of choice, is disallowed. If you use any references

other than the lecture notes, ensure you cite them or you may receive 0 for plagiarism. A clear comment in

your code is sufficient.

2

Readme

Write a text file named readme. Include clear instructions on how to compile and run your algorithm. Ensure that your program compiles and runs correctly . If your program does not compile, it will receive 0

marks. If it doesn’trun according to the specification, youwill receive very few marks. You may also include

a makefile if you wish. Analysis

Write a file named analysis.pdf explaining the queue strategy and the data structures that you use in

your code. Input

Your program should read a file name from standard input, and run the simulation using the named file as

theinputfile. The input file has the following format: • The number of servers. • A set of lines each consisting of a customer arrival time followed by the corresponding service time,

followed by the service type (1 or 2). Times are in seconds, from the start of the simulation. Although a sample input file has been provided, your program should still run successfully on substantially larger inputs. Output

Output should be to standard output. The output should consist of the following data, clearly labelled: • Number of people served for each server. • Time that the last customer finished being served (total simulation time) for each server. • Average time a customer spends in queue. • Maximum time a customer spends in queue. • Maximum Length of queue. • Total idle time for each server.

3

Submission instructions

Your completed assignment should contain your source code, readme and analysis.pdf in a zipped folder

named ass2_yourname.zip. 1. Late submissions will be marked with a 25% deduction for each day. 2. Submissions more than three days late will not be marked, unless an extension has been granted. 3. If you need an extension apply through SOLS, if possible before the assignment deadline. 4. Plagiarism is treated seriously. If we suspect any work is copied, all students involved are likely to

receive zero for the entire assignment.