$ od -c -N 50000 [qv]<lispcourse>OUTLINE39.TED!2 0000000 F . G . H . 0000020 6 / 2 5 / 8 5 \r L i s p C o u r 0000040 s e # 3 9 : S o l u t i o 0000060 n s t o H o m e w o r k # 0000100 3 8 \r L i s p C o u r s e # 3 0000120 9 : S o l u t i o n s t o 0000140 H o m e w o r k # 3 8 \r S o 0000160 l u t i o n f u n c t i o n s 0000200 a r e a t t a c h e d . \r N 0000220 o t e s o n P r o b l e m 0000240 C \r P r o b l e m C r e q u 0000260 i r e s a b r e a d t h - f 0000300 i r s t s e a r c h o f t 0000320 h e f a m i l y t r e e . 0000340 I n p a r t i c u l a r , 0000360 s t a r t i n g a t t h e 0000400 n o d e f o r t h e g i v 0000420 e n p e r s o n , y o u w 0000440 a n t t o c h e c k a l l 0000460 o n e - a w a y r e l a t i 0000500 v e s ( e . g . , p a r e n 0000520 t s a n d c h i l d r e n ) 0000540 . I f n o n e o f t h 0000560 e s e m a t c h , y o u w 0000600 a n t t o c h e c k a l l 0000620 t w o - a w a y r e l a t i 0000640 v e s ( i . e . , a l l o 0000660 n e - a w a y r e l a t i v e 0000700 s o f t h e o n e - a w a 0000720 y r e l a t i v e s ) . A 0000740 n d s o o n u n t i l y 0000760 o u f i n d a n N - a w a 0001000 y r e l a t i v e t h a t 0001020 m a t c h e s o r y o u a 0001040 r e o u t o f r e l a t i 0001060 v e s . \r T h i s c o n t r a 0001100 s t s w i t h a d e p t h 0001120 - f i r s t s e a r c h , w 0001140 h e r e y o u w o u l d s 0001160 e a r c h a l l o f t h e 0001200 p e r s o n ' s m o t h e r 0001220 s r e l a t i v e s f i r s 0001240 t , t h e n h i s o r h 0001260 e r f a t h e r ' s r e l a 0001300 t i v e s , t h e n h i s 0001320 o r h e r c h i l d r e n s 0001340 r e l e a t i v e ( w h e r 0001360 e c h i l d r e n a r e c 0001400 o n s i d e r e d i n s o m 0001420 e a r b i t r a r y o r d e 0001440 r ) . F o r e a c h o f 0001460 t h e m o t h e r ' s r e 0001500 l a t i v e s , y o u w o u 0001520 l d f i r s t s e a r c h 0001540 t h a t p e r s o n s ' m o 0001560 t h e r ' s r e l a t i v e s 0001600 , t h e n t h e i r f a t 0001620 h e r ' s a n d s o o n . 0001640 B a s i c a l l y , y o u 0001660 s e a r c h o n e b r a n 0001700 c h o f t h e f a m i l y 0001720 t r e e u n t i l i t e 0001740 n d s , t h e n s e a r c h 0001760 t h e n e x t b r a n c h 0002000 a n d s o o n . \r I n a 0002020 b r e a d t h - f i r s t s 0002040 e a r c h , a t e a c h s 0002060 t e p y o u h a v e t h e 0002100 a s e t o f N - a w a y 0002120 r e l a t i v e s , n o n e 0002140 o f w h o m m a t c h t 0002160 h e t h i n g y o u a r e 0002200 s e a r c h i n g f o r . 0002220 F o r e a c h o f t h e 0002240 s e N - a w a y r e l a t i 0002260 v e s , y o u w a n t t o 0002300 c o m p u t e t h e i r 1 0002320 - a w a y r e l a t i v e s 0002340 ( i . e . , t h e N + 1 - a 0002360 w a y r e l a t i v e s ) . 0002400 W h i l e y o u a r e 0002420 c o m p u t i n g t h e N + 0002440 1 - a w a y r e l a t i v e s 0002460 f o r e a c h o f t h e 0002500 N - a w a y r e l a t i v e 0002520 s , y o u n e e d t o m 0002540 a i n t a i n l o t s o f 0002560 i n f o r m a t i o n 234 i n 0002600 p a r t i c u l a r , y o u 0002620 n e e d t o k e e p a 0002640 l i s t o f t h e N - a w 0002660 a y r e l a t i v e s t h a 0002700 t s t i l l h a v e t o 0002720 b e w o r k e d o n A N D 0002740 y o u n e e d t o m a i 0002760 n t a i n a l i s t o f 0003000 t h e N + 1 - a w a y r e l 0003020 a t i v e s a l r e a d y d 0003040 i s c o v e r e d ( w h o w 0003060 i l l b e " e x p a n d e d 0003100 " d u r i n g t h e n e x 0003120 t r o u n d i f n o m a 0003140 t c h i s f o u n d a m o 0003160 n g t h e N + 1 r e l a t 0003200 i v e s ) . \r T h e b e s t 0003220 w a y t o m a i n t a i n 0003240 t h i s i n f o r m a t i o n 0003260 i s i n a g l o b a l 0003300 q u e u e ( s e e H o m e w 0003320 o r k # 3 2 & L i s p C o 0003340 u r s e # 3 3 ) . \r J u s t 0003360 k e e p r e p e a t i n g t 0003400 h e f o l l o w i n g u n t 0003420 i l t h e q u e u e b e c 0003440 o m e s e m p t y : \r T a k e 0003460 a p e r s o n o f f o f 0003500 t h e h e a d o f t h e 0003520 q u e u e . \r I f h e m 0003540 a t c h e s w h a t y o u ' 0003560 r e l o o k i n g f o r , 0003600 y o u ' r e d o n e 234 e x 0003620 i t . \r I f t h e r e ' s n 0003640 o m a t c h , e x p a n d 0003660 t h e p e r s o n i n t o 0003700 a s e t o f h i s 1 - a 0003720 w a y r e l a t i v e s a n 0003740 d a d d a l l t h e s e 0003760 r e l a t i v e s t o t h e 0004000 e n d o f t h e q u e u 0004020 e . \r N o t e t h a t w i t 0004040 h t h i s s c h e m e , y 0004060 o u d o n ' t n e e d t o 0004100 k e e p e x p l i c i t t 0004120 r a c k o f w h a t l e v 0004140 e l ( i . e . , K - a w a y 0004160 o r L - a w a y , o r w 0004200 h a t n o t ) y o u a r e 0004220 w o r k i n g o n . B e c 0004240 a u s e y o u a l w a y s 0004260 a d d t h e N + 1 - a w a y 0004300 t o t h e e n d o f t 0004320 h e q u e u e b u t t a k 0004340 e t h e n e x t p e r s o 0004360 n t o " e x p a n d " f r 0004400 o m t h e f r o n t o f 0004420 t h e q u e u e , y o u a 0004440 r e c e r t a i n t o p r 0004460 o c e s s a l l t h e N - 0004500 a w a y r e l a t i v e s b 0004520 e f o r e y o u s t a r t 0004540 o n t h e N + 1 a w a y 0004560 r e l a t i v e s . T h e 0004600 m o m e n t y o u f i n d 0004620 a m a t c h , y o u j u s 0004640 t s t o p a n d y o u c 0004660 a n b e s u r e t h a t 0004700 y o u ' v e f o u n d t h e 0004720 c l o s e s t r e l a t i v 0004740 e t h a t m a t c h e s . \r 0004760 H o w e v e r , i f t h e r 0005000 e a r e m o r e t h a n 0005020 o n e m a t c h i n g r e l 0005040 a t i v e a t t h e N t h 0005060 l e v e l , y o u w i l l 0005100 f i n d o n l y o n e a 0005120 n d t h e n s t o p . T 0005140 o f i n d a l l c l o s e 0005160 s t r e l a t i v e s i n 0005200 c a s e o f a t i e r e 0005220 q u i r e s s o m e s m a l 0005240 l v a r i a t i o n s o n 0005260 t h i s s c h e m e . \r \0 \0 \0 0005300 \0 \0 003 ( L I S T ( ( P A G E 0005320 N I L N I L ( 0 0 1 7 0005340 2 2 ) ( ( H E A D I N G N I 0005360 L ( H E A D I N G T Y P E Y 0005400 Y Y ) ( 5 4 0 7 5 6 7 2 0005420 3 6 ) N I L ) ( T E X T N 0005440 I L N I L ( 7 2 7 2 4 6 0005460 8 6 4 8 ) N I L ) ) ) ( P 0005500 A G E N I L N I L ( 0 0 0005520 1 7 2 2 ) ( ( F O L I O 0005540 N I L ( P A R A L O O K S ( 0005560 Q U A D R I G H T ) C H A R 0005600 L O O K S ( S U P E R S C R I 0005620 P T 0 S I Z E 1 2 F A M 0005640 I L Y T I M E S R O M A N O 0005660 V E R L I N E O F F S T R I 0005700 K E O U T O F F U N D E R L 0005720 I N E O F F S L O P E R E 0005740 G U L A R W E I G H T M E D 0005760 I U M ) ) ( 4 6 8 7 5 6 7 0006000 2 3 6 ) N I L ) ( H E A D 0006020 I N G N I L ( H E A D I N G 0006040 T Y P E X X X ) ( 7 2 7 5 0006060 6 7 2 3 6 ) N I L ) ( T 0006100 E X T N I L N I L ( 7 2 0006120 7 2 4 6 8 6 4 8 ) N I L ) 0006140 ) ) ( P A G E N I L N I L 0006160 ( 0 0 1 7 2 2 ) ( ( F 0006200 O L I O N I L ( P A R A L O 0006220 O K S ( Q U A D R I G H T ) 0006240 C H A R L O O K S ( S U P E 0006260 R S C R I P T 0 S I Z E 1 0006300 2 F A M I L Y T I M E S R O 0006320 M A N O V E R L I N E O F F 0006340 S T R I K E O U T O F F U 0006360 N D E R L I N E O F F S L O 0006400 P E R E G U L A R W E I G H 0006420 T M E D I U M ) ) ( 4 6 8 0006440 7 5 6 7 2 3 6 ) N I L ) 0006460 ( H E A D I N G N I L ( H E 0006500 A D I N G T Y P E X X X ) ( 0006520 7 2 7 5 6 7 2 3 6 ) N I 0006540 L ) ( T E X T N I L N I L 0006560 ( 7 2 7 2 4 6 8 6 4 8 ) 0006600 N I L ) ) ) ) ) \0 \0 \0 \0 \0 005 \0 0006620 \n \0 l \0 l \0 \0 \0 006 \0 \0 \0 006 002 001 \0 0006640 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0006660 \0 \0 220 \0 220 \0 \0 \0 006 \0 \0 \0 006 002 001 \0 0006700 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0006720 \0 \0 220 \0 220 \0 \0 \0 \n \0 \0 \0 006 002 001 \0 0006740 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0006760 \0 \0 l \0 l \0 \0 \0 \b \0 \0 \0 006 002 001 \0 0007000 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0007020 \0 \0 H \0 H \0 \0 \0 \b \0 \0 \0 006 002 001 \0 0007040 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0007060 \0 \0 $ \0 $ \0 \0 \0 \f \0 \0 \0 006 002 001 \0 0007100 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0007120 \0 \0 \0 \0 \0 \0 \0 \0 022 \0 \0 \0 006 002 001 \0 0007140 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0007160 \0 \0 \0 \0 \0 \0 \0 \0 006 \0 \0 \0 006 002 001 \0 0007200 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0007220 \0 \0 \0 \0 \0 002 210 \0 006 \0 \0 \0 006 002 001 \0 0007240 \0 \0 \0 \0 \0 \0 \v P A G E H E A D I 0007260 N G \0 003 X X X \0 \0 \0 \0 \0 \0 \0 \0 \0 0007300 \0 \0 \0 \0 H \0 006 \0 \0 \0 006 002 001 \0 \0 \0 0007320 \0 \0 \0 \0 \v P A G E H E A D I N G 0007340 \0 003 Y Y Y \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 0007360 \0 \0 004 \0 005 \0 \n T I M E S R O M A 0007400 N \0 \f \0 \0 \0 \0 \0 \0 001 \0 \0 \n T I M 0007420 E S R O M A N \0 \f \0 \0 \0 \0 \0 \0 003 0007440 \0 \0 \n T I M E S R O M A N \0 \f \0 0007460 \0 \0 \0 \0 \0 002 \0 \0 \n T I M E S R O 0007500 M A N \0 016 \0 \0 \0 \0 \0 \0 002 \0 \0 \n T 0007520 I M E S R O M A N \0 \f \0 \0 \0 \0 \0 0007540 \0 \0 \0 \0 \0 \0 \0 \0 002 \0 \n \0 \0 \0 030 \0 0007560 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 \t \0 \0 \0 + 0007600 \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 \b \0 \0 \0 0007620 + \0 \0 \0 \0 004 \0 \0 \0 \0 \0 002 \0 \a \0 \0 0007640 \0 ! \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 \a \0 0007660 \0 \0 023 \0 \0 \0 \0 003 \0 \0 \0 \0 \0 002 \0 006 0007700 \0 \0 \0 025 \0 \0 \0 \0 005 \0 \0 \0 024 \0 \0 \0 0007720 \0 002 \0 \0 001 j \0 \0 \0 \0 005 \0 \0 \0 \0 \0 0007740 002 \0 005 \0 \0 \0 026 \0 \0 \0 \0 005 \0 \0 \0 022 0007760 \0 \0 \0 \0 002 \0 \0 001 257 \0 \0 \0 \0 005 \0 \0 0010000 \0 \0 \0 002 \0 006 \0 \0 \0 005 \0 \0 \0 \0 005 \0 0010020 \0 \0 \r \0 \0 \0 \0 001 \0 \0 002 i \0 \0 \0 \0 0010040 005 \0 \0 \0 \0 \0 002 \0 005 \0 \0 \0 d \0 \0 \0 0010060 \0 005 \0 \0 \0 \0 \0 002 \0 004 \0 \0 \0 A \0 \0 0010100 \0 \0 005 \0 \0 \0 \0 \0 002 \0 002 \0 \0 \0 - \0 0010120 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 002 \0 \0 \0 ; 0010140 \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 003 \0 \0 \0 0010160 177 \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 005 \0 \0 0010200 001 335 \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 001 \0 0010220 \0 \0 315 \0 \0 \0 \0 005 \0 \0 \0 \0 \0 002 \0 001 0010240 \0 \0 \n 275 \0 & z 271 0010250