CS计算机代考程序代写 prolog data structure Java algorithm ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II – subtitle

ITI 1121. Introduction to Computing II
Queue: applications

by

Marcel Turcotte

Version March 7, 2020

Preamble

Preamble

Overview

Overview

Queue: applications
We are interested in all aspects of queues in programming. We examine several examples
of their use, including resource sharing and simulation algorithms. We explore the concept
of breadth-first-search.

General objective:
This week, you will be able to implement a breadth-first-search algorithm.

1 31

Preamble

Learning objectives

Learning objectives

Justify the role of a queue in solving a computer problem.
Design a computer program requiring the use of a queue.
Implement a breadth-first-search.

Readings:
https://en.wikipedia.org/wiki/Breadth-first_search

2 31

https://en.wikipedia.org/wiki/Breadth-first_search

Preamble

Plan

Plan

1 Preamble

2 Introduction

3 Labyrinth

4 Implementation

5 Conclusions

6 Prologue

3 31

Asynchronous processing

Applications such as producer/consumer, client/server or sender/receiver require the
use of queues if the data processing is asynchronous.

Asynchronous processing means that the client and server are not synchronized, the
server is not ready or able to receive the data at the time and speed of sending.

This treatment requires a queue:
The client inserts data into the queue (enqueue);
The server removes data from the queue at the appropriate time (dequeue).

Such a queue is sometimes called a buffer.

4 31

Asynchronous processing

In particular, the inter-process communications in an operating system work like this.
1. Printer spooler.;
2. Buffered i/o;
3. access to disks;
4. the transmission of messages (packets) over a network.

5 31

Timeshare

CPU

rearfront
new process

dequeue() enqueue()

All modern operating systems are time-shared. One of the common techniques for
time-sharing is called round-robin. The first process in the queue (dequeue) is assigned a
time slot after which its execution is suspended and the process is put at the end of the
queue (enqueue), and we move on to the next process.

6 31

Communications between processes

enqueue()

client

server

dequeue()

whi le ( t rue ) {
whi le ( ! q . i s F u l l ( ) ) {

q . enqueue ( . . . ) ;
}

}

whi le ( t rue ) {
whi le ( ! q . empty ( ) ) {

p r o c e s s ( q . dequeue ( ) )
}

}

⇒ inter-process communication (IPC), buffered i/o, etc.

7 31

Applications

Simulations;
Customer

+getArrivalTime() : int
+getNumberOfItems() : int
+getNumberOfServedItems() : int
+serve() : void

-arrivalTime : int
-initialNumberOfItems : int
-numberOfItems : int
-MAX_NUM_ITEMS : int

Cashier

+addCustomer(c : Customer) : void
+getQueueSize() : int
+serveCustomers(currentTime : int) : void
+getTotalCustomerWaitTime() : int
+getTotalCustomersServed() : int
+getTotalItemsServed() : int

-queue : Queue
-currentCustomer : Customer
-totalCustomerWaitTime : int
-customersServed : int
-totalItemsServed : int

<>
Queue

+enqueue(obj : Object) : void
+dequeue() : Object
+isEmpty() : boolean
+size() : int

ArrayQueue

<>

Breadth-first-search.

8 31

Introduction

What displays the method Search.run()?

pub l i c c l a s s Search {
pub l i c s t a t i c vo id run ( ) {

Queue q ;
q = new LinkedQueue() ;
q . enqueue ( ” ” ) ;

whi le ( t rue ) {
S t r i n g s ;
s = q . dequeue ( ) ;

q . enqueue ( s + “0” ) ;
q . enqueue ( s + “1” ) ;

System . out . p r i n t l n ( q ) ;
}

}
}

9 31

What’s that for?

Queue q ;
q = new LinkedQueue() ;
q . enqueue ( ” ” ) ;

whi le ( t rue ) {
S t r i n g s ;
s = q . dequeue ( ) ;

q . enqueue ( s + “0” ) ;
q . enqueue ( s + “1” ) ;

System . out . p r i n t l n ( q ) ;
}

This algorithm generates all strings consisting of the symbols 0 and 1 in ascending
order of length: 0, 1, 00, 01, 10, 11, 000, 001, . . .

10 31

[“”]
[“0”]
[“0″,”1”]
[“1”]
[“1″,”00”]
[“1″,”00″,”01”]
[“00″,”01”]
[“00″,”01″,”10”]
[“00″,”01″,’10″,”11”]
[“01″,”10″,”11”]
[“01″,”10″,”11″,”000”]
[“01″,”10″,”11″,”000″,”001”]
[“10″,”11″,”000″,”001”]
[“10″,”11″,”000″,”001″,”010”]
[“10″,”11″,”000″,”001″,”010″,”011”]
[“11″,”000″,”001″,”010″,”011”]
[“11″,”000″,”001″,”010″,”011″,”100”]
[“11″,”000″,”001″,”010″,”011″,”100″,”101”]

What does it do?

Queue q ;
q = new LinkedQueue() ;
q . enqueue ( ” ” ) ;

whi le ( t rue ) {
S t r i n g s ;
s = q . dequeue ( ) ;

q . enqueue ( s + “L” ) ;
q . enqueue ( s + “R” ) ;
q . enqueue ( s + “U” ) ;
q . enqueue ( s + “D” ) ;

System . out . p r i n t l n ( q ) ;
}

This algorithm generates all strings formed by the symbols L, R, U and D in
increasing order of length: L, R, U, D, LL, LR, LU, LD, . . .

12 31

[]
[“”]
[]
[“L”]
[“L”,”R”]
[“L”,”R”,”U”]
[“L”,”R”,”U”,”D”]
[“R”,”U”,”D”]
[“R”,”U”,”D”,”LL”]
[“R”,”U”,”D”,”LL”,”LR”]
[“R”,”U”,”D”,”LL”,”LR”,”LU”]
[“R”,”U”,”D”,”LL”,”LR”,”LU”,”LD”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”,”RL”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”,”RU”]
[“U”,”D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”,”RU”,”RD”]
[“D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”,”RU”,”RD”]
[“D”,”LL”,”LR”,”LU”,”LD”,”RL”,”RR”,”RU”,”RD”,”UL”]

Labyrinth

Semantics

What are these Ls, Rs, Us and Ds?
Each symbol corresponds to a direction:

L = left;
R = right;
U = up;
D = down.

Each string corresponds to a path in two-dimensional space.

14 31

D DR

DRR DRRU

DRRUR DRRURR

Let’s add some obstacles.

Now let’s assume that some of the cells are unaccessible.

DRRURRDD DRRDRR

16 31

x

s

s + L

s + R

s + U

s + D

dequeue
enqueue

Finding the shortest path in a maze

19 31

Implementation

Helper methods

We’ll need a method that checks if a partial solution is valid, checkPath(String
path).
As well as a method that tells us if a valid solution achieves its goal,
reachesGoal(String path).

20 31

Data structures

A matrix of characters, i.e. a 2-dimensional array.
char [ ] [ ] maze ;

An inaccessible position (a wall) is denoted by ’#’, an empty cell by ’ ’, and a visited
position by ’+’.

#+#####
#+# # #
#++ # #
### #
##### #

21 31

checkpath(String path)

p r i v a t e boolean checkPath ( S t r i n g path ) {

boolean [ ] [ ] v i s i t e d ;
v i s i t e d = new boolean [MAX_ROW] [MAX_COL] ;

i n t row , c o l ;

row = 0 ;
c o l = 0 ;

i n t pos =0;

boolean v a l i d = t rue ;

22 31

checkpath(String path)
. . .
whi le ( v a l i d && pos < path . l e n g t h ( ) ) { char d i r e c t i o n = path . charAt ( pos++); switch ( d i r e c t i o n ) { case LEFT : co l −−; break ; case RIGHT : c o l ++; break ; case UP: row−−; break ; case DOWN: row++; break ; de f au l t : v a l i d = f a l s e ; } . . . 23 31 checkpath(String path) After each move, we check that the current position is valid, i.e. inside the labyrinth, is not a wall, and has not been visited. i f ( ( row >= 0) && ( row < MAX_ROW) && ( c o l >= 0) && ( c o l < MAX_COL) ) { i f ( v i s i t e d [ row ] [ c o l ] | | g r i d [ row ] [ c o l ]==WALL) { v a l i d = f a l s e ; } e l s e { v i s i t e d [ row ] [ c o l ] = t rue ; } } e l s e { v a l i d = f a l s e ; } } // end o f w h i l e l oop re tu rn v a l i d ; } 24 31 «Are we done yet!» p r i v a t e boolean r e a c h e s G o a l ( S t r i n g path ) { i n t row = 0 ; i n t c o l = 0 ; f o r ( i n t pos =0; pos < path . l e n g t h ( ) ; pos++) { char d i r e c t i o n = path . charAt ( pos ) ; switch ( d i r e c t i o n ) { case LEFT : co l −−; break ; case RIGHT : c o l ++; break ; case UP: row−−; break ; case DOWN: row++; break ; } } re tu rn g r i d [ row ] [ c o l ] == OUT; } 25 31 Conclusions Breadth-first-search The algorithm using a queue is called breadth-first search. The search tree is built level by level. All the sequences of the same level (thus all the sequences of the same length) are processed before proceeding with the next level. 26 31 Depth-first-search The algorithm using a stack is called the depth-first search. The search tree is built branch by branch. A sequence is selected and repeatedly extended until no extension is valid. The algorithm then backtracks, hence the nickname backtracking. 27 31 Prologue Summary A breadth-first-search uses a queue to find the shortest path in a search space. 28 31 Next module Queue : array-based implementation 29 31 References I E. B. Koffman and Wolfgang P. A. T. Data Structures: Abstraction and Design Using Java. John Wiley & Sons, 3e edition, 2016. 30 31 Marcel Turcotte Marcel. School of Electrical Engineering and Computer Science (EECS) University of Ottawa 31 / 31 Marcel. Preamble Overview Learning objectives Plan Introduction Labyrinth Implementation Conclusions Prologue