Volume 1 I Fundamental Algorithms
`
`THE ART OF
`COMPUTER PROGRAMMING
`SECOND EDITION
`
`·
`Readmg, Massachusetts ·
`
`M 1 p k C l'f rn1'a · London · Don Mills,
`en o
`ar ,
`a 1 o
`
`
`
`Page 1 of 6
`
`SONY EXHIBIT 1017
`
`

`

`E LIBRARY
`HAROLD B . L~ UNIVERSITY
`BRIGHA~R~V~ UTAH
`
`This book is in the
`
`~~:~~;~:~~~::::~~~ ',:FORMATION PROCESSING
`
`d MICHAE L A.
`RICHARD S. VARGA an
`
`HARRISON Editors
`'
`
`COPYRIGHT@ 1973, 1968 BY ADDI ON-WESLEY PUBLISHING COMPANY 1 INC. ALL RIGHTS
`RESERVED . NO PART OF THIS PUBLICATION MAY BE REPRODUCED, STORED IN ARE(cid:173)
`TRIEVAL SYSTEM, OR TRANSMITTED, IN ANY FORM OR BY ANY MEANS, ELECTRONIC
`I
`MECHANICAL, PHOTOCOPYING, RECORDING, OR OTHERWI E, WITHOUT THE PRIOR WRlT-
`TEN PERMISSION OF THE PUB LISHER. PRINTED IN THE UNITED STATES OF AMERICA.
`PUBLISHED
`IMULTANEOU LY IN CANADA . LIBRARY OF CONGRESS CATALOG CARD NO.
`73-1830.
`
`ISBN 0-201 -03809-9
`ABCDEFGHIJ-MA-79876543
`
`
`
`Page 2 of 6
`
`

`

`2.2.a
`
`at
`
`ION' STUUcTUHES
`2-0
`T Jo'OHMA T
`)
`d r ked data.
`(
`11~
`algorithm for this subroutine all
`th sequential an
`I t . s on bo
`. t design an
`d'
`t
`.
`ocar
`m~tnipu !t •on
`. th ·s exercise IS o
`the tape
`rrec ory rn any wa
`f
`l!>tt
`The problem ~~ I allocator may trans orm n be read in anew by the sub 'Y 8.!1 i t
`task. The subroutm~nce the tape directory c~irectory is not needed by oth routine
`. ment and the tape
`er Parts
`Prepares its answer, Sl
`'ts next assign
`'
`allocator on 1
`f
`'th
`l
`•
`h subroutine allocatiOn a gon m o exercise 26
`f the loading routine.
`f . l
`·am for t e
`"
`o
`shows how to "solve a ~Ir y ~eneral type
`.
`[25] Write a MIX progr
`.
`27.
`The following constructro~ and many simpler games. Consider a finite of
`ame including chess, mm, 'ble "position" in the game. For each Posit~et
`[401
`28.
`two-person gh of ~hich represents~ possl
`f m that position into some other Pos·t·ton
`of nodes, eac
`"
`" hlch trans or
`.
`1 Ion
`or more moves w
`'tion y (and y IS a successor of x) if th
`·
`f
`there are zero
`.
`decessor o post
`ere
`that Position x IS a pre
`which have no successors are classified
`·t·
`W
`e say
`t · pos1 wns
`as
`. .
`·
`h
`C
`. a move from x to y. ~a11n 1 er· to move in positron x IS t e opponent of th
`s T 1e p ay
`1s
`,
`e
`.t.
`"
`" or "lost posl wn ·
`·t· n x
`h
`1
`sors of pos1 IO
`won
`·
`,
`we can compute t e comp ete set of "w
`- 1
`to move in the succes
`.t.
`fi
`P ayer
`tion of posl rons,
`)
`.
`on,
`Given such a con gur~ .
`'bl for the player to force a VIctory and the co
`h. h It IS pOSSI e
`.
`.
`t l
`ttl-
`positions (those m w 1c.
`.
`hich the player mus ose agamst an exp ·
`'trons (those rn w
`'1 't . 1d
`ert
`"
`"
`p1ete set of
`lost posl
`the following operation unti I yie s _no change: tnark
`.
`opponent) by repeatedly dorng
`marked "won" ; mark a position "won" if
`·t·
`"lost" if all its successors are
`a pos1 ron
`.
`k d "lost."
`least one of its successors IS mar e
`ated as many times as possible, there may b
`h.
`ation has been repe
`.
`h
`e
`Afte: _t rs oper
`been marked at all; a player m sue a position cannot
`I
`some posrtwns that have not
`d
`h be compelle
`to ose.
`.
`force a victory, nor can ~t . .
`the complete set of "won" and "lost" positions ca
` larn~~~m for computers that closely resembles Algorithm;
`This procedurffie f?r
`f .
`be adapted to an e cren a gon
`h
`.
`·r n a count of the number o Its successors t at have not
`. h
`h
`We may keep wit eac posr 10
`.
`f th
`been marked "won," and a list of allrts predecessohrs.d
`' l
`l
`'th
`·
`th' exercise is to work out t e etar s o
`e a gon m that has
`bl
`The pro em m
`IS
`.
`.
`a uely described and to apply it to some mterestmg games that do not
`t b
`·
`" • S · A
`(
`J us
`een so v g
`' . .
`.
`"
`.
`.
`a-
`ct. m. October,
`1
`involve too many possible positiOns [hke the mi rtary o_ame
`.
`1963), 124, or E. Lucas, Recreations Mathematiques, 3 (Pans, 1893) 105-116].
`[21] (a) Give an algorit hm to "erase" an entire list like (1 ), ~.e., to put all of its
`,.. 29.
`nodes on the AVAIL stack, given only the value of FIRST. The algonthm should operate
`as fast as possible. (b) R epeat part (a) for a list like (12), given the values of F and R.
`
`0t
`
`2.2.4. Circular Lists
`
`A slight change in the manner of linking furnishes us with an important alter(cid:173)
`native to the methods of the preceding section.
`A circularly-linked list (briefly: a circular list) has the property that its last
`node links back to the first instead of to A. It is then possible to access all of
`the list starting at any given point; we also achieve an extra degree of symmetry,
`and if we choose we need not think of the list as having a "last" or "first" node.
`The following situation is typical:
`
`(1)
`
`
`
`Page 3 of 6
`
`

`

`f'IJH lJr.,\ n J,IS'J'S
`
`'J:ll
`
`(lJll •
`
`, I hi\ I t lw nod<·~ hnVI' I wo fil'1d~ tNFO
`1 I
`. I 1
`,
`\~~unll
`llllcl I INK
`.
`111 1 hr· r1rr•f·Nflr
`Th<'l'l' 11' n 11\ < Vl\1'111 1 1• PTR w hif'IJ llf . 1
`' n
`•
`• ·
`1
`l 1
`Ill! " I o t I
`. I
`H· rtg li!Tlr, t n(Jdr• ,,f thl'
`·rill'
`'II;
`11
`~.~
`, nd LINK(PTR) 1"1 I H' Ill I 1'1'~"1 of t lw 1dtn
`I
`'o" nmt" ·n r
`t ~~ ,I
`.
`H• o\lr,w1nJ< pnrrllllVf•
`•· .'r·Jf i<'ll" 11rc m oHt Jmporlltnt ;
`) I 11~1·rt y nt ldt : P {=: AVAIL, INFO ( p) -
`y LIN
`(..INK(PTR) ~ P.
`1
`K(P) -
`11
`b) ln:;crt y at nght : Insert Y at left, then PTR _ P
`) Set y to left node and delete: P -
`LINK ( PTR)
`.
`r LINJ< (P), AVAIL {=: P.
`' y - INFO(P ), LINK(PTR)-
`
`LINK(PTR),
`
`,
`
`.
`ration (b) is a little surprising at first glance. th
`:ectivclY moves the leftmost node to the right . e t~er~tiOn PTR -
`0
`LINK ( PTR )
`e ~te easy to understand if the list is regarded m
`~ cha~ram (1), and this is
`as a cucle mstead
`t
`· h
`f
`qUl
`. with connected ends.
`o a s ra1g t
`]
`me
`d
`·11
`.
`The alert rea er w1 observe that we have m d
`a c a senous mistake in the
`( ) (b)
`.
`( )
`.
`.
`bove operatwns a 1
`c . What 1s 1t? Answer W h
`aonsidcr the possibility of an empty list. If for exam pi~ o e t~ve (fo)r~otten. to
`pedra ~on he IS appl~ed
`cve times to the list (1)' we wi ll have PTR pointing to
`a no c m t e AVAIL hst
`·
`·
`.
`fi
`nd this can lead to senous dtf£cult1es; for example imagine
`. '
`1 .
`app ymg operatiOn
`If
`(l )
`h
`. .
`•
`a
`.
`1
`1
`(c) six tun~s to
`.
`we ta<:e t e pos1t10n that PTR will equal A in the case of
`an empty list, we could remedy the above operations by inserting th dd't·
`1
`·
`A th
`e a
`1 1ona
`~~'f
`instructiOnS
`en PTR -
`P . otherwise
`"
`ft
`J PTR =
`'
`LINK ( P ) -
`"I NFD ( P ) r-Y " in (a) and (b); preceding (c) by the test "if PTR. ··A ~her
`"'f
`•
`d f 11
`"
`·
`( ) b
`en
`; an
`0 owmg C Y
`I PTR = P , then P TR - A. "
`UNDERFLOW
`Note that th~ operations (a), (b)~ and (c) give us the actions of an output(cid:173)
`restricted deque, m th e sense of SectiOn 2.2.1. Therefore we find in part icular
`that a circular list can be used as either a st ack or a queue. Operations (a) and
`(c) combined give us a stack ; operations (b) and (c) give us a queue. These
`operations are only slightly less direct t han their counterparts in the previous
`section, where we saw that operations (a), (b)~ and (c) can be performed on
`linear lists using two pointers F and R.
`Other impor tant operations b ecome efficient with circular lists. For example,
`it is very convenient t o "erase" a list , i.e., to put an entire circular list ont o the
`AVAIL stack at once :
`
`AVAIL ~ LINK(PTR) .
`
`(2)
`
`then
`If
`PTR ~A,
`[Recall that the "~" operation denotes interchange, i.e., P +--AVAIL, AVAIL+(cid:173)
`LINK ( PTR ), LINK ( PTR) +-- P.] Operation (2) is clearly v alid if PTR point s anywhere
`in the circular list .
`Using a similar t echnique, if PTR 1 and PTR2 point to disjoint circular lists
`, resp ectively, we can insert th e entire list L2 at the right of L1 :
`and 1
`
`1
`
`1
`
`2
`
`If
`(if
`
`t hen
`
`PTR2 ~ A,
`PTR1 ~ A,
`then
`PTR 1 +- PTR2, PTR2 +-A).
`set
`
`
`
`Page 4 of 6
`
`

`

`1' \ Tlll•JH
`,
`wrntrr
`.
`<!.~
`·o us wnyH, I H a noLher ki m
`1
`p P IJ
`j tl Vltri
`'
`1
`I ~~ in I o t wn, .
`r·o JTf'HJlOild to t h c ron~atr•. l"lr:r ftt
`272
`.!)atir
`•1rcJJIIll'
`
`,.
`111t
`1 n~ onr 1
`., ~
`'I' JH's r'
`1
`1
`~phi 1
`1 r' u H('(l not. only t o rrprPkr•r,
`r ~ (1"111,._•.
`br' drull'
`,,'{
`'1"1
`t r•tlll
`, . t r•ll ll
`I
`)
`I " ll)f
`'
`t linr~nr HLrii('LitrPH; a l'i rr·tJ I
`t 111
`· dr' lltl(tnn o .
`. r·nr'ltlllr tH
`lr•tr•rt
`·r•prcscn
`.
`l
`· a r 1
`1 1~
`, , t hnl ·'
`kcrJnll
`t'nlly cqUIVaent lo a Htta i"ht l lflt ~
`I'IHt~ ll <'st<
`I Jl n lso to '
`<
`sscn ''"'
`'""
`· 1r
`·c~ H
`111
`(!ott .~tntrl 11 ' 1 · • '('11 1• 11odc tH Pd.'
`•
` The natural question to ""L " 'flt
`'
`rca ·
`.
`·
`I~
`t 1 ( H' I
`1
`('ll'c'l '
`(
`. II
`'""1\
`·
`1
`to 1 he fron a 0
`do we find the end of the li<>t
`. ' ''' 1
`, JHllntcJ
`., . 1n
`.,
`tcrs
`·
`"r..tO\V
`r'tH
`11
`'~lr·~
`A link to signal the end. Th'
`t h t " ·n potn . • bscrvnJion, I S, .
`1
`1
`r h . I S nO
`.
`C a
`r,f
`II
`· ( J tillS 0
`·atiOI18 while illOVlllg through the [' ~~£•r I~
`JllJ11Ctry? "
`f el e
`11
`ned lOll W I 1
`me opel
`b k
`hr sy
`.
`'~t f
`tr>~l\
`to our start·
`. performmg so d
`t p when we get ac
`the rll·ru .
`t ·r we ;:t~e
`houl s o
`t .
`'ng l
`the next, we 8
`'II
`1
`D a~~
`·t·
`place is st1 presen rn the list)
`thn
`h t ur stai wg
`d ·
`·
`ode to
`one n .
`f course, t a o
`oblem just pose
`IS to put a spec· I
`to the pr
`.
`1a r
`·
`mwg, o
`(ns u
`Jternative solut.wn
`. 1' t as a convenient stopprng place. Thj ' ecog_
`~ Sp e .
`An a
`1 c rculai JS '
`·fi d .t .
`ft
`. bl
`. ode into cac 1
`d .
`plications we o en n
`IS quite co
`I
`I
`Cia\
`mza e n
`. h ad an Jn ap
`d
`h' h . .
`nven·
`node is called the lzst. e l~r list have exactly one no e w IC Is Its list head tent
`·nsist that every cJrc~ . 1 • list will then never be empty. The diagr · One
`t
`am ( l)
`o J
`that the cu cu a I
`advantage IS
`•
`now becomes
`
`[ist hr~~~~34___,,~+1
`"-
`
`I +.___I --LI +:c9J (4)
`
`the right end of the list, references to lists like (
`t
`.
`)
`fi
`t d of a pomter o
`.
`·
`are
`I
`4
`.
`the list head, which 1s often m a xed memory locat·
`ns ea
`usually made v1a
`d b
`ton
`In this case, we sacrifice operation C?) state a ove.
`.
`.
`.
`(4) may be compared with 2.2.3-(1) at the begmnmg of the Previ
`.
`D1agram
`.
`. h "'
`,
`.
`ous
`5
`h'ch the link associated wit
`Item
`now pomts to Loc (FIRST )
`.
`.
`sectwn, 111 w J
`•
`•
`f to A and FIRST is now thought of as a lmk Within a nod
`t d
`.
`111s ea o
`,
`.
`.
`e,
`NODE(LOC(FIRST) ) . The principal d1fferenc~ betwe~n (4) and 2.2.3-(1) is that
`with (4) it is possible (though not necessanly efficient) to get to any point of
`the list from any other point.
`As an example of the use of circular lists, we will discuss arithmetic on
`polynomials in the variables x, y, and z, with integer coefficients. There are
`many problems in which a scientist wants to manipulate polynomials instead of
`just numbers; we are thinking of operations like the multiplication of
`
`by
`
`to get
`
`- 6xy5 + 5y 6).
`Linked all?cation is a natural tool for this purpose, since polynomials can grow
`to unpredictable sizes and we may want to represent many polynomials in
`memory at the same time.
`
`(x 6
`
`
`
`O JH'l"llf IO il H
`
`1'
`
`Hll'l, t•JO
`1 :>~1•'0
`
`1•
`
`Page 5 of 6
`
`

`

`1.
`
`' ~ . .t
`•
`
`r
`,, !11 ('()]1:<Hk l IH'n' tlw t wn OPI'lll' lilt
`1
`I
`·
`Hlo Hdrl't
`' ' 1'
`,.;tt JlJlnl't' 1 wt n pn ynnmHtl til t ~'Ill I'HI'Itl
`I
`1 lOll "'"' 1111111 '''''I' I
`j II~ '
`j'
`('(
`llll
`'
`( Ifill
`I
`11
` n · o tH' nonZI'Hl t erm , nnd ha .. 'i 1 h e 1 \V
`\ htr·h , .. 11 L
`l
`Jl'
`1
`1!-11 111
`•
`o-" onl form
`" nnr'
`.tntH;: (
`
`I IHI
`
`1 1.\lt r,r ·rf\
`
`27:\
`
`COEF
`
`(5)
`
`<
`
`the coefficient of the term ir1 x AyB c
`COEF i
`z . w
`'ll
`ncre
`.
`. .
`is and exponents wlll always lie in tlle
`e Wt as ume that th co-
`range allo d b
`·fliclen
`.
`, ·t is not necessary to check this conditio d
`. we Y this format and
`1
`d
`n urmg ou.
`l
`1
`.
`,
`t luH J
`.
`1 ca cu at10n . The
`to stand for the+ A 8 c fi 1
`·on ABC wJll be use
`·
`e ds of th
`. Th
`-
`t
`nota 1
`1 ( )
`e 1gn of ABC , i.e., the sign of th _
`single uJ11t.
`e noc e _5 , treated
`35 a ys be plus, except that there is a special nod
`de e~d of every polynomial
`nll'~ah ha ABC =
`- 1 and COEF = 0 . This spec~ al
`,,, uc
`.
`.
`Ia no e 1s a O'f
`t
`·
`o us to our d1 cuss10n of a list head above be
`.
`< "' _ea convemencc,
`ani!
`.
`'
`cause It provides
`.
`log
`I" and it av01ds the problem of
`.
`a convement
`·
`an empty hst (corre o d.
`t
`"sentll1e
`~ 11 mg
`0 the
`]ynomial "0 "). The node of the list always appea . d
`if we follow the direction of the r 1
`r 111
`ecreasmg order of the
`fi Jd
`po
`m <.s, except that the pecial node
`ABC e
`'
`.
`hich has ABC =
`- 1) lmks to the largest value of ABC F
`s + 5 6
`w
`.
`or example the
`(
`·
`6
`6
`polynomial x
`Y would be represented thus:
`'
`-
`xy
`
`t t: econd word m (5), will
`
`Algorithm A (Additio"! of polynomials). This algorithm adds polynomial(P) to
`polynomial (Q), assummg that P and Q are pointer variables pointing to poly(cid:173)
`nomials having t he form above. The list P will be unchanged, the list Q will
`retain the sum. Pointer variables P and Q return to their starting points at the
`conclusion of this algorithm; auxiliary pointer variables Ql and Q2 are also used.
`
`AI. [Initialize.] Set P f-- LINK(P) , Ql f-- Q, Q f-- LINK(Q) . (Now both P and Q point
`to the leading term of the polynomial. Throughout most of this algorithm
`the variable Ql will be 110ne step behind" Q, in the sense that Q = LINK(Ql) .)
`A2. [ABC(P ) : ABC( Q) .] If ABC(P) < ABC(Q) , set Ql f-- Q and Q f-- LINK(Q) and
`repeat this step. If ABC {P) = ABC {Q), go to step A3. If ABC (P) > ABC (Q),
`go to step A5.
`If
`(We have found terms with equal exponents.)
`A3. [Add coefficients.]
`ABC{P) < 0,
`Otherwise set COEF(Q) +(cid:173)
`the a lgorithm terminates.
`COEF ( Q) + COEF ( p). Now if COEF ( Q) = 0, go to A4; otherwise, set Ql +- Q,
`P (--- LINK (P), Q f-- LINK (Q), and go to A2. (Curiously the latter operations
`are identical to step Al .)
`
`
`
`Page 6 of 6
`
`