联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2022-03-29 10:09

CSC263 Problem Set 3

Question 1: Consulting on Board Game Design

You have been hired as a consultant by the board game company to help them analyze

potential designs for a new game. The game will have a map of cities and villages and two

ports. Playing the game will involve travelling from the starting port to an ending port

through some cities and villages. Some cities and villages are connected while others are

not. This diagram shows one possible board layout. The red circle indicates that B is a city.

A, C, and D are villages. Travel is permitted in both directions on all roads. You can not

travel through a port – only start or end at one.

The board game company wants to consider three different scenarios:

Scenario 1: Routes can travel through any city or village at most once.

Scenario 2: Routes can travel through any village at most once, but they can pass

through a city multiple times.

Scenario 3: There is a special village passport card. A player may play it on one village

and then is permitted to travel a route that passes through that village one extra time.

Routes can still travel through cities multiple times and all the other villages at most

once. The village passport can not be played on a port. The village passport does not

have to be played, so all the routes from scenario 2 are still permitted under scenario 3.

The company has a number of board configurations under consideration and for each config-

uration, they wish to know how many legal routes will go from start to finish under each of

the three scenarios. For example, using the board configuration in the diagram above, there

are 3 possible routes for scenario 1, 8 routes for scenario 2 and 39 for scenario 3. It starts

to get hard to calculate the numbers of possible routes by hand as the board configurations

get more complicated. So that’s why they have hired you!

(a) Your first task is to design efficient algorithms and associated data structures to count

the number of possible routes under each of the three scenarios for an arbitrary board

configuration.

The designers have realized that if two cities are directly connected then there will be

an infinite number of routes in both scenario 2 and scenario 3. So they will not ever

propose a configuration with connected cities. Also, every configuration they propose

1

will have one start port and one end port. The configurations never have two roads

connecting the same two places directly.

Submit a written description of the three algorithms. Your algorithms should be based

directly on a graph algorithm we learned in class and you should be explaining how

that algorithm is adapted and applied to this problem. Specifically, describe

the data structures you are using to support your algorithm. The audience is someone

who already understands the algorithms we learned and the specific terminology we

used in lectures so you can refer to those terms.

(b) Design your own concise text (i.e. human readable) representation of a board config-

uration. Write clear specifications for this representation. Make sure that your design

can represent any board that meets the assumptions specified above. As an example in

your explanation, include the representation for the small board above and then also

submit the input file for this board to MarkUs using the filename example board.txt.

(c) Implement your algorithm in Python. You must have a single file Routes.py and it

must not import any Python modules other than sys (which you need for command-line

argument processing) and optionally typing. The output of your program should be

a message giving the number of possible routes under the three scenarios. The exact

format of this output is up to you. You are not asked to list all the possible routes.

Your program must run on teach.cs with the following command

python3 Routes.py inputfilepath. You can assume that the inputfilepath passed to

your program in the command-line argument corresponds to a valid board configuration

file according to your representation in part b. It is fine to fail spectacularly if this

assumption is violated. Don’t spend time on error checking the input, but do use

excellent coding style including variable names and comments that will help the marker

see immediately how your code connects to the algorithm you described in part a.

We will separately post some extra advice about writing your program including some

sample code for reading the command-line argument and opening and reading from a

file.

(d) Design a set of tests for your program and use them to demonstrate to the marker that

your program works correctly. You should focus on algorithmically important and

interesting tests not boundary cases that are uninteresting algorithmically. Each test

case is a board configuration, NOT a unittest, and should be in its own .txt file.

Suppose your first test was in the board configuration file called test1.in.txt. Then the

TA should be able to run your code by typing python3 Routes.py test1.in.txt at

the command line on teach.cs.

In Q1.pdf (where you provide the English solution to parts a, b and d of this question),

expand on each test case you designed, explaining what it is that you are testing, the

specific input, and the actual output when you ran the test. You should reference the

exact filenames of your test files which you will submit to MarkUs separately as part

of your submission but a reader should be able to understand your testing without

opening any other files. You may wish to provide a visual picture of the boards

2

(inside the discussion in Q1.pdf) if that makes it clearer for the reader.1. A word of

advice, keep the input files small. It is fine to hand-draw board examples or to not have

pictures at all.

In order to earn full marks for correctness for your algorithms and their implementation,

you need to convey to the marker (in the time that they have available to read and

understand your Q1.pdf ) that your code has been tested properly. Conveying technical

information clearly, concisely and in a way that can be understood quickly is the skill

we are practicing here. It isn’t easy. If you say too much, the reader won’t have time to

dig through all your tests. If you say too little, they won’t be convinced that the code

was tested thoroughly. Finding the correct balance and presenting the information in

a way that can be grasped quickly is the goal.

Expectations for Question 1

There are multiple learning goals for this question. One is for you to solidify your knowledge

of graph algorithms by doing some actual implementation and designing test cases. The

second is for you to practice concisely communicating to a technical audience. While it is

important that your program works correctly, the majority of the marks will not come from

part (c). Do not leave the testing or the written explanations as after thoughts or assign

either of these tasks to a single person. Both partners should be involved in the designing,

coding, testing and writing.

Question 2: Amortized Analysis

Let [O1, O2, O3, ..., On] be a list of n operations each of which is either TASK1 or TASK2. O1

is TASK1 and O2 is TASK2 but the others are specified in the cases below. The running time

of TASK2 operations is always constant. The running time of the first TASK1 operation

(O1) is also constant, but the running time of each TASK1 operation Oi after the first is twice

as long as the previous TASK1 operation. Calculate the amortized time of the operations in

the following three scenarios.

(a) There are a constant number of TASK2 operations between consecutive TASK1 oper-

ations.

(b) There are Θ(

(n)) TASK2 operations between consecutive TASK1 operations.

(c) The number of TASK2 operations between a TASK1 operation (Oi) and the previous

TASK1 operation (Oj) is always twice the number between (Oj) and its previous TASK1

operation.

1You might need to compress the images to keep Q1.pdf within the Markus submission size limits

3

Question 3

Consider a connected undirected graph G. Design an algorithm based on BFS to find a

vertex v whose removal (deleting the vertex and all its incident edges) does NOT disconnect

the graph.

(a) Describe your algorithm in clear and precise English.

(b) Justify that your algorithm works correctly.

(c) Analyse the worst-case running time of your algorithm if G is represented by an adja-

cency matrix. Express the result in asymptotic notation with a tight bound.

Question 4: Minimum Spanning Trees

T is a minimum spanning tree for an arbitrary connected undirected graph G. G is repre-

sented as a matrix of edge weights where a 0 indicates no edge and negative weights are not

allowed. T is stored as an unsorted list of edges.

Now we add to G a new vertex v. We add a set of edges {e1, e2, ...ek} that connect v to

some vertices in G. The resulting graph is G′.

Describe an efficient2 algorithm for computing a minimum spanning tree for G′.

Briefly justify the correctness of your algorithm.

State and briefly justify the efficiency of your algorithm.

2We have intentionally not provided the required complexity for your algorithm. Your solution should be as efficient as

possible. An algorithm that correctly computes the result but is more complicated than necessary (in terms of running time or

space), will not receive as many marks as a more efficient solution.


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp