Loading...
[PDF] LECTURE NOTES On CS8391 – DATA STRUCTURES (Anna
CS8391 – DATASTRUCTURES 2 VISION Our Vision is to build a strong teaching research environment in the field of computer
[PDF] Sri Vidya College of Engineering & Technology Course Material
Sri Vidya College of Engineering Technology Course Material ( Lecture Notes) CS8391 – Data Structures - Unit I Page 2 5 Search for a data element
[PDF] Lecture Notes on Data and File Structure - VSSUT
BCS-202 DATA AND FILE STRUCTURE – ( 3-0-0 )Cr -3 Proposed Lecture Plan Lecture 1 : Motivation, Objective of studying the subject, overview of Syllabus
[PDF] NPR Nagar, Natham, Dindigul - nprcetorg
Structures In C GE8161- Problem Solving and Python Programming Laboratory CS8391- Data Structures CS8381- Data Structures Laboratory
[PDF] ANNA UNIVERSITY CHENNAI KATHIR COLLEGE OF
Subject code CS8391 Subject name Data Structures COURSE OUTCOMES CO1 Explain abstract data types for linked list and its applications
[PDF] COURSE OUTCOMES - RMD ENGINEERING COLLEGE
Implement designs using Programmable Logic Devices CS8391 – DATA STRUCTURES C203 1 Implement abstract data types for linked list data structureand apply
[PDF] COURSE OUTCOME STATEMENTS III SEM TO VII SEM
CS8391 Data Structures 4 C204 CS8392 Object Oriented Programming firm basis for further reading and study in the subject
[PDF] KLN COLLEGE OF ENGINEERING BE Computer Science and
C203 CS8391 Data Structures 20 C204 CS8392 Object Oriented Programming 21 C205 EC8395 Communication Engineering 22 C206
[PDF] SRM Easwari Engineering College
The students will acquire Graph theoretical ideas which are highly useful CS8391 2 Implement abstract data types for linear data structures CS8391 3
[PDF] COMPUTER SCIENCE AND ENGINEERING
C303-CS8391/DATA STRUCTURES C303 1 Implement the operations of List ADT for problem solving C303 2 Apply the different linear data structures (Stack and
![[PDF] Lecture Notes on Data and File Structure - VSSUT](https://pdfprof.com/EN_PDFV2/Docs/PDF_3/68084_3lecture1428550942.pdf.jpg "[PDF] Lecture Notes on Data and File Structure - VSSUT")
68084_3lecture1428550942.pdf [9/...w9 bh9{ hb 5!! !b5 CL[9 {w.../...w9
.͵ Ļĭŷ͵ ЌƩķ {ĻƒĻƭƷĻƩ
/ƚƒƦǒƷĻƩ {ĭźĻƓĭĻ ε 9ƓŭźƓĻĻƩźƓŭ
ğƓķ
LƓŅƚƩƒğƷźƚƓ ĻĭŷƓƚƌƚŭǤ tƩĻƦğƩĻķ ĬǤ5Ʃ͵ wğƉĻƭŷ aƚŷğƓƷǤ
5Ʃ͵ ağƓğƭ wğƓƆğƓ YğĬğƷ
aƩ͵ {ǒƆğǤğ YǒƒğƩ {ğƷŷǒğ 99w {...w9b5w! {!L ...bL9w{L hC 9/Ibh[hDͲ ....w[! {!a.![t...wͲ h5L{I!Ͳ Lb5L! Α АЏБЉЊБ3RD SEMESTER B.Tech.(CSE, IT)
BCS-202 DATA AND FILE STRUCTURE - ( 3-0-0 )Cr.-3Proposed Lecture Plan
Lecture 1 : Motivation, Objective of studying the subject, overview of Syllabus Lecture 2 : Module I : Introduction to Data & file structures. Lecture 3 : Linear data Structures - Linked list and applicationsLecture 4 : Stack and Queue
Lecture 5 : Module II : Introduction to Non- Linear data structures Lecture 6 : General Trees , Binary Trees, Conversion of general tree to binaryLecture 7 : Binary Search Tree
Lecture 8 : Red-Black trees
Lecture 9 : Multi linked structures
Lecture 10 : Heaps
Lecture 11: Spanning Trees, Application of treesLecture 12 : Module III Introduction to Sorting
Lecture 13, 14 : Growth of function , 'O" notation, Complexity of algorithms, Lecture 15 : Internal sorting, Insertion sorting, Selection SortLecture 16 : Bubble Sort, Quick sort, Heap sort
Lecture 17 : Radix sort, External sort, Multi way merge Lecture 18 : Module IV : Introduction to Searching, Sequential Search, Binary SearchLecture 19 : Search trees traversal
Lecture 20 : Threaded Binary search trees
Lecture 21 : AVL Tree - concept and construction Lecture 22 : Balancing AVL trees - RR, LL, LR and RL RotationsLecture 23 : Module V : Introduction to Hashing
Lecture 24 : Hashing techniques, Hash function
Lecture 25 : Address calculation techniques- common hashing functionsLecture 26 : Collision resolution
Lecture 27 : Linear probing, quadratic probing
Lecture 28 : Double hashing
Lecture 29 : Bucket addressing
Lecture 30 : Module VI- Introduction to file StructuresLecture 31 : External storage devices
Lecture 32 : Records - Concepts and organization
Lecture 33 : Sequential file - structures and processing Lecture 34 : Indexed sequential files - strictures and processingLecture 35 : Direct files
Lecture 36 : Multi Key access
INTRODUCTION
5!! {w.../...w9ʹ Ώ{ƷƩǒĭƷǒƩğƌ ƩĻƦƩĻƭĻƓƷğƷźƚƓ ƚŅ ķğƷğ źƷĻƒƭ źƓ ƦƩźƒğƩǤ ƒĻƒƚƩǤ Ʒƚ ķƚ ƭƷƚƩğŭĻ ε
ƩĻƷƩźĻǝğƌ ƚƦĻƩğƷźƚƓƭ ĻŅŅźĭźĻƓƷƌǤ͵
ΏΏCL[9 {w.../...w9ʹ wĻƦƩĻƭĻƓƷğƷźƚƓ ƚŅ źƷĻƒƭ źƓ ƭĻĭƚƓķğƩǤ ƒĻƒƚƩǤ͵
ŷźƌĻ ķĻƭźŭƓźƓŭ ķğƷğ ƭƷƩǒĭƷǒƩĻ ŅƚƌƌƚǞźƓŭ ƦĻƩƭƦĻĭƷźǝĻƭ Ʒƚ ĬĻ ƌƚƚƉĻķ ğŅƷĻƩ͵
ź͵ !ƦƦƌźĭğƷźƚƓΛǒƭĻƩΜ ƌĻǝĻƌʹ ğǤ ƚŅ ƒƚķĻƌźƓŭ ƩĻğƌΏƌźŅĻ ķğƷğ źƓ ƭƦĻĭźŅźĭ ĭƚƓƷĻǣƷ͵
źź͵ !ĬƭƷƩğĭƷΛƌƚŭźĭğƌΜ ƌĻǝĻƌʹ !ĬƭƷƩğĭƷ ĭƚƌƌĻĭƷźƚƓ ƚŅ ĻƌĻƒĻƓƷƭ ε ƚƦĻƩğƷźƚƓƭ͵
źźź͵ LƒƦƌĻƒĻƓƷğƷźƚƓ ƌĻǝĻƌʹ wĻƦƩĻƭĻƓƷğƷźƚƓ ƚŅ ƭƷƩǒĭƷǒƩĻ źƓ ƦƩƚŭƩğƒƒźƓŭ ƌğƓŭǒğŭĻ͵
5ğƷğ ƭƷƩǒĭƷǒƩĻƭ ğƩĻ ƓĻĻķĻķ Ʒƚ ƭƚƌǝĻ ƩĻğƌΏǞƚƩƌķ ƦƩƚĬƌĻƒƭ͵ .ǒƷ ǞŷźƌĻ ĭŷƚƚƭźƓŭ źƒƦƌĻƒĻƓƷğƷźƚƓƭ
ŅƚƩ źƷͲ źƷƭ ƓĻĭĻƭƭğƩǤ Ʒƚ ƩĻĭƚŭƓźǩĻ ƷŷĻ ĻŅŅźĭźĻƓĭǤ źƓ ƷĻƩƒƭ ƚŅ La9 ğƓķ {t!/9͵
t9{ʹ
ź͵ {źƒƦƌĻʹ ĬǒźƌƷ ŅƩƚƒ ƦƩźƒźƷźǝĻ ķğƷğ ƷǤƦĻƭ ƌźƉĻ źƓƷͲ ĭŷğƩ ε .ƚƚƌĻğƓ͵
Ļŭʹ !ƩƩğǤ ε {ƷƩǒĭƷǒƩĻźź͵ /ƚƒƦƚǒƓķʹ /ƚƒĬźƓĻķ źƓ ǝğƩźƚǒƭ ǞğǤƭ Ʒƚ ŅƚƩƒ ĭƚƒƦƌĻǣ ƭƷƩǒĭƷǒƩĻƭ͵
Њʹ[źƓĻğƩʹ 9ƌĻƒĻƓƷƭ ƭŷğƩĻ ğķƆğĭĻƓĭǤ ƩĻƌğƷźƚƓƭŷźƦε ŅƚƩƒ ğ ƭĻƨǒĻƓĭĻ͵
9ŭʹ {ƷğĭƉͲ vǒĻǒĻ Ͳ [źƓƉĻķ [źƭƷ
Ћʹ bƚƓΏ[źƓĻğƩʹ !ƩĻ ƒǒƌƷźΏƌĻǝĻƌ ķğƷğ ƭƷƩǒĭƷǒƩĻ͵ Ļŭʹ ƩĻĻͲ DƩğƦŷ͵
!.{w!/ 5!! t9 ʹ⮚ {ƦĻĭźŅźĻƭ ƷŷĻ ƌƚŭźĭğƌ ƦƩƚƦĻƩƷźĻƭ ƚŅ ķğƷğ ƷǤƦĻ ƚƩ ķğƷğ ƭƷƩǒĭƷǒƩĻ͵
⮚ wĻŅĻƩƭ Ʒƚ ƷŷĻ ƒğƷŷĻƒğƷźĭğƌ ĭƚƓĭĻƦƷ ƷŷğƷ ŭƚǝĻƩƓƭ ƷŷĻƒ͵
⮚ ŷĻǤ ğƩĻ ƓƚƷ ĭƚƓĭĻƩƓĻķ ǞźƷŷ ƷŷĻ źƒƦƌĻƒĻƓƷğƷźƚƓ ķĻƷğźƌƭ ƌźƉĻ ƭƦğĭĻ ğƓķ ƷźƒĻ
ĻŅŅźĭźĻƓĭǤ͵
⮚ ŷĻǤ ğƩĻ ķĻŅźƓĻķ ĬǤ Ќ ĭƚƒƦƚƓĻƓƷƭ ĭğƌƌĻķ ƩźƦƌĻ ўΛ5ͲCͲ!Μ
5ў{ĻƷ ƚŅ ķƚƒğźƓ
Cў{ĻƷ ƚŅ ŅǒƓĭƷźƚƓ !ў{ĻƷ ƚŅ ğǣźƚƒƭ Ή ƩǒƌĻƭ [LbY95 [L{ʹ ⮚ ! ķǤƓğƒźĭ ķğƷğ ƭƷƩǒĭƷǒƩĻ͵⮚ [źƓĻğƩ ĭƚƌƌĻĭƷźƚƓ ƚŅ ķğƷğ źƷĻƒƭ͵
⮚ 5źƩĻĭƷźƚƓ źƭ ğƭƭƚĭźğƷĻķ ǞźƷŷ źƷ͵
⮚ [ƚŭźĭğƌ ƌźƓƉ ĻǣźƷƭ ĬΉǞ źƷĻƒƭ͵ tƚźƓƷĻƩƭ ğĭƷƭ ğƭ ƷŷĻ ƌƚŭźĭğƌ ƌźƓƉ͵
⮚ /ƚƓƭźƭƷƭ ƚŅ ƓƚķĻƭ ƷŷğƷ ŷğƭ ƷǞƚ ŅźĻƌķƭ͵
Ώ 5ğƷğ ŅźĻƌķ ʹ źƓŅƚ ƚŅ ƷŷĻ ĻƌĻƒĻƓƷ͵
Ώ bĻǣƷ ŅźĻƌķʹ ƓĻǣƷ ƦƚźƓƷĻƩ ĭƚƓƷğźƓźƓŭ ƷŷĻ ğķķƩĻƭƭ ƚŅ ƓĻǣƷ ƓƚķĻ͵
t9{ hC [LbY95 [L{ʹ
ź͵ {źƓŭƌǤ ƚƩ ĭŷğźƓʹ {źƓŭƌĻ ƌźƓƉ ĬΉǞ źƷĻƒƭ͵
źź͵ 5ƚǒĬƌǤʹ ŷĻƩĻ ğƩĻ ƷǞƚ ƌźƓƉƭͲ ŅƚƩǞğƩķ ğƓķ ĬğĭƉǞğƩķ ƌźƓƉ͵
źźź͵ /źƩĭǒƌğƩʹ ŷĻ ƌğƭƷ ƓƚķĻ źƭ ğŭğźƓ ƌźƓƉĻķ Ʒƚ ƷŷĻ ŅźƩƭƷ ƓƚķĻ͵ ŷĻƭĻ ĭğƓ ĬĻ ƭźƓŭƌǤ ĭźƩĭǒƌğƩ
ε ķƚǒĬƌǤ ĭźƩĭǒƌğƩ ƌźƭƷ͵ !5!b!D9{ʹ⮚ [źƓƉĻķ ƌźƭƷ ǒƭĻ ķǤƓğƒźĭ ƒĻƒƚƩǤ ğƌƌƚĭğƷźƚƓ Ʒŷǒƭ ğƌƌƚĭğƷźƓŭ ƒĻƒƚƩǤ ǞŷĻƓ ƦƩƚŭƩğƒ
źƭ źƓźƷźğƌźƭĻķ͵ [źƭƷ ĭğƓ ŭƩƚǞ ğƓķ ƭŷƩźƓƉ ğƭ ƓĻĻķĻķ͵ !ƩƩğǤƭ ŅƚƌƌƚǞ ƭƷğƷźĭ ƒĻƒƚƩǤ
ğƌƌƚĭğƷźƚƓ ͵IĻƓĭĻ ƷŷĻƩĻ źƭ ǞğƭƷğŭĻ ƚŅ ƭƦğĭĻ ǞŷĻƓ ƌĻƭƭ ĻƌĻƒĻƓƷƭ ğƩĻ ķĻĭƌğƩĻķ͵ ŷĻƩĻ
źƭ ƦƚƭƭźĬźƌźƷǤ ƚŅ ƚǝĻƩŅƌƚǞ Ʒƚƚ Ĭĭƚǩ ƚŅ ŅźǣĻķ ğƒƚǒƓƷ ƚŅ ƭƷƚƩğŭĻ͵
⮚ bƚķĻƭ ğƩĻ ƭƷƚƩĻķ źƓĭƚƓƷźŭǒƚǒƭƌǤ Ʒŷǒƭ źƓƭĻƩƷźƚƓ ğƓķ ķĻƌĻƷźƚƓ ƚƦĻƩğƷźƚƓƭ ğƩĻ ĻğƭźƌǤ
źƒƦƌĻƒĻƓƷĻķ͵
⮚ [źƓĻğƩ ķğƷğ ƭƷƩǒĭƷǒƩĻƭ ƌźƉĻ ƭƷğĭƉ ğƓķ ƨǒĻǒĻƭ ğƩĻ ĻğƭźƌǤ źƒƦƌĻƒĻƓƷĻķ ǒƭźƓŭ ƌźƓƉĻķ
ƌźƭƷ͵
5L{!5!b!D9{ ʹ⮚ ğƭƷğŭĻ ƚŅ ƒĻƒƚƩǤ ğƭ ƦƚźƓƷĻƩƭ ƩĻƨǒźƩĻǣƷƩğ ƭƷƚƩğŭĻ͵
⮚ bƚķĻƭ ğƩĻ źƓĭƚƓƷźŭǒƚǒƭƌǤ ƭƷƚƩĻķ ƷŷĻƩĻĬǤ źƓĭƩĻğƭźƓŭ ƷźƒĻ ƩĻƨǒźƩĻķ Ʒƚ ğĭĭĻƭƭ
źƓķźǝźķǒğƌ ĻƌĻƒĻƓƷƭ͵ ƚ ğĭĭĻƭƭ ƓƷŷ źƷĻƒ ğƩƩğǤƭ ƓĻĻķ ğ ƭźƓŭƌĻ ƚƦĻƩğƷźƚƓ ǞŷźƌĻ
ƌźƓƉĻķ ƌźƭƷ ƓĻĻķ Ʒƚ Ʀğƭƭ ƷŷƩƚǒŭŷ ΛƓΏЊΜ źƷĻƒƭ͵
⮚ bƚķĻƭ ƒǒƭƷ ĬĻ ƩĻğķ źƓ ƚƩķĻƩ ŅƩƚƒ ĬĻŭźƓƓźƓŭ ğƭ ƷŷĻǤ ŷğǝĻ źƓŷĻƩĻƓƷ ƭĻƨǒĻƓƷźğƌ
ğĭĭĻƭƭ͵
⮚ wĻǝĻƩƭĻ ƷƩğǝĻƩƭźƓŭ źƭ ķźŅŅźĭǒƌƷ ĻƭƦĻĭźğƌƌǤ źƓ ƭźƓŭƌǤ ƌźƓƉĻķ ƌźƭƷ͵ aĻƒƚƩǤ źƭ ǞğƭƷĻķ ŅƚƩ
ğƌƌƚĭğƷźƓŭ ƭƦğĭĻ ŅƚƩ ĬğĭƉ ƦƚźƓƷĻƩƭ źƓ ķƚǒĬƌǤ ƌźƓƉĻķ ƌźƭƷ͵
59CLbLbD [LbY95 [L{ʹ
ƭƷƩǒĭƷ ƓƚķĻ Ο
źƓƷ źƓŅƚͳ
ƭƷƩǒĭƷ ƓƚķĻ ΫƓĻǣƷͳ ƓĻǣƷŅźĻƌķ͵ !Ɠ Ļŭ ƚŅ ƭĻƌŅ ƩĻŅĻƩĻƓĭĻƷźğƌ ƭƷƩǒĭƷǒƩĻ͵ΛϔΜ
Π ΫƦƷƩͳΛϔΜ{ĻƌŅ wĻŅĻƩĻƓĭĻƷźğƌ ƭƷƩǒĭƷǒƩĻʹ ! ƭƷƩǒĭƷǒƩĻ ƷŷğƷ źƭ ƩĻŅĻƩĻƓĭźƓŭ Ʒƚ ğƓƚƷŷĻƩ ƭƷƩǒĭƷǒƩĻ ƚŅ ƭğƒĻ
ƷǤƦĻ͵ IĻƩĻ ͻƓĻǣƷͼ źƭ ƦƚźƓƷźƓŭ Ʒƚ ƭƷƩǒĭƷǒƩĻ ƚŅ ƷǤƦĻ ͻƓƚķĻͼ͵
ΏƦƷƩ źƭ ğ ƦƚźƓƷĻƩ ƚŅ ƷǤƦĻ ƓƚķĻ͵ ƚ ğĭĭĻƭƭ źƓŅƚ Ɠ ƓĻǣƷ ƷŷĻ ƭǤƓƷğǣ źƭʹ ƦƷƩΏѢźƓŅƚͳ ƦƷƩΏѢƓĻǣƷͳ
ht9w!Lhb{ hb {LbD[ [LbY95 [L{ʹź͵ {ĻğƩĭŷźƓŭ
źź͵ LƓƭĻƩƷźƚƓ
źźź͵ 5ĻƌĻƷźƚƓ
źǝ͵ ƩğǝĻƩƭğƌǝ͵ wĻǝĻƩƭğƌ
ǝź͵ {ƦƌźƷƷźƓŭ
ǝźź͵ /ƚƓĭğƷĻƓğƷźƚƓ {ƚƒĻ ƚƦĻƩğƷźƚƓƭʹğʹ LƓƭĻƩƷźƚƓ
ʹǝƚźķ ƦǒƭŷΛƭƷƩǒĭƷ ƓƚķĻΫΫ ŷĻğķƩĻŅͲ źƓƷ ķğƷğΜ ΏΏΏΏΏΏΏΏΛЊΜ
ΟƭƷƩǒĭƷ ƓƚķĻΫ ƓĻǞƓƚķĻ ў ƒğƌƌƚĭΛƭźǩĻƚŅΛƭƷƩǒĭƷ ƓƚķĻΜΜͳ
ƓĻǞƓƚķĻΏѢķğƷğў ķğƷğͳ ƓĻǞƓƚķĻΏѢƓĻǣƷў ΫŷĻğķƩĻŅͳ ΫŷĻğķƩĻŅ ў ƓĻǞƓƚķĻͳ ΠΛЊΜ ʹ ŷĻğķƩĻŅ źƭ ğ ƦƚźƓƷĻƩ Ʒƚ ğ ƦƚźƓƷĻƩ ƚŅ ƷǤƦĻ ƭƷƩǒĭƷ ƓƚķĻ͵ {ǒĭŷ ƦğƭƭźƓŭ ƚŅ ƦƚźƓƷĻƩ Ʒƚ ƦƚźƓƷĻƩ
źƭ ĭğƌƌĻķ wĻŅĻƩĻƓĭĻ ƦƚźƓƷĻƩ͵ {ǒĭŷ ķĻĭƌğƩğƷźƚƓƭ ğƩĻ ƭźƒźƌğƩ Ʒƚ ķĻĭƌğƩğƷźƚƓƭ ƚŅ ĭğƌƌ ĬǤ
ƩĻŅĻƩĻƓĭĻ͵ ŷĻƓ ƦƚźƓƷĻƩƭ ğƩĻ ƦğƭƭĻķ Ʒƚ ŅǒƓĭƷźƚƓƭ ͲƷŷĻ ŅǒƓĭƷźƚƓ ǞƚƩƉƭ ǞźƷŷ ƷŷĻ ƚƩźŭźƓğƌ
ĭƚƦǤ ƚŅ ƷŷĻ ǝğƩźğĬƌĻ͵ ź͵ LƓƭĻƩƷźƚƓ ğƷ ŷĻğķʹ ƭƷƩǒĭƷ ƓƚķĻΫ ŷĻğķўb...[[ͳ ŅƚƩΛźƓƷ źўЊͳ źѡЏͳźњњΜΟ ƦǒƭŷΛεŷĻğķͲźΜͳ Ʀǒƭŷ źƭ ĭğƌƌĻķ ŷĻƩĻ͵ 5ğƷğ ƦǒƭŷĻķ źƭ Њ͵ε ǒƭĻķ ĭƚǩ ƩĻŅĻƩĻƓĭĻƭ ğƩĻ
ƦğƭƭĻķ źƓ ŅǒƓĭƷźƚƓ ğƩŭǒƒĻƓƷƭ͵
Π ƩĻƷǒƩƓΛŷĻğķΜͳ Π ϔ ʹƚƦʹ Ў Ѝ Ќ Ћ Њϔ ʹLƷĻƒƭ ğƦƦĻğƩ źƓ ƩĻǝĻƩƭĻ ƚƩķĻƩ͵ΛķĻƒĻƩźƷΜ
źź͵ LƓƭĻƩƷźƚƓ ğƷ Ʒğźƌʹ ƭƷƩǒĭƷ ƓƚķĻΫ ğķķЊΛΜ Ο ƭƷƩǒĭƷ ƓƚķĻΫ ŷĻğķўb...[[ͳ ƭƷƩǒĭƷ ƓƚķĻΫ Ʒğźƌͳ ƦǒƭŷΛεŷĻğķͲЊΜͳƷğźƌ ў ŷĻğķͳ
ŅƚƩΛźƓƷ źўЋ ͳźѡЏͳ źњњΜ Ο ƦǒƭŷΛεΛƷğźƌΏѢƓĻǣƷΜͲźΜͳ Ʒğźƌў ƷğźƌΏѢƓĻǣƷͳ Π ƩĻƷǒƩƓΛŷĻğķΜͳ Π ϔ ʹ ƚƦʹ Њ Ћ Ќ Ѝ ЎĬ͵ ƩğǝĻƩƭğƌʹ
źƓƷ ĭƚǒƓƷΛ ƭƷƩǒĭƷ ƓƚķĻΫ ƦΜ ΟźƓƷ ĭƚǒƓƷ ўЉͳ ƭƷƩǒĭƷ ƓƚķĻΫ ƨͳĭǒƩƩĻƓƷ ў ƨͳ
ǞŷźƌĻΛƨΏѢƓĻǣƷ ͧў b...[[Μ Ο ƨўƨΏѢƓĻǣƷͳ ĭƚǒƓƷњњͳ Π ƩĻƷǒƩƓΛĭƚǒƓƷΜͳ Π ĭ͵ {ĻğƩĭŷźƓŭʹ
ƭƷƩǒĭƷ ƓƚķĻΫ ƭĻğƩĭŷΛ ƭƷƩǒĭƷ ƓƚķĻΫ ƌźƭƷͲ źƓƷ ǣΜ
Ο ƭƷƩǒĭƷ ƓƚķĻΫ ƦͳŅƚƩΛƦў ƌźƭƷͳ Ʀ ΏѢƓĻǣƷ ͧў b...[[ͳ Ʀў ƦΏѢƓĻǣƷ Μ
Ο źŅΛƦΏѢķğƷğўўǣΜ ƩĻƷǒƩƓΛƦΜͳ ƩĻƷǒƩƓΛb...[[ΜͳΠΠ
Lat[9a9b!Lhb hC [L{{
ʹ ź ʹ !ƩƩğǤ źƒƦƌĻƒĻƓƷğƷźƚƓʹ ϔķĻŅźƓĻ b...abh59{ ЊЉЉ ƭƷƩǒĭƷƓƚķĻƷǤƦĻ Ο źƓƷ źƓŅƚ ͲƓĻǣƷ ͳΠ ͳ
ƭƷƩǒĭƷƓƚķĻƷǤƦĻ ƓƚķĻΝb...abh59{Ξͳϔ ʹЊЉЉ ƓƚķĻƭ ğƩĻ ķĻĭƌğƩĻķ ğƭ ğƓ ğƩƩğǤ ƓƚķĻ͵ tƚźƓƷĻƩ Ʒƚ ğ ƓƚķĻ źƭ ƩĻƦƩĻƭĻƓƷĻķ ĬǤ ğƓ ğƩƩğǤ
źƓķĻǣ͵ ŷǒƭ ƦƚźƓƷĻƩ źƭ ğƓ źƓƷĻŭĻƩ ĬΉǞ Љ ε b...abh59{ΏЊ ͵ b...[[ ƦƚźƓƷĻƩ źƭ ƩĻƦƩĻƭĻƓƷĻķ ĬǤ ΏЊ͵
ƓƚķĻΝƦΞ źƭ ǒƭĻķ Ʒƚ ƩĻŅĻƩĻƓĭĻ ƓƚķĻΛƦΜ Ͳ źƓŅƚΛƦΜ źƭ ƩĻŅĻƩĻƓĭĻķ ĬǤ ƓƚķĻΝƦΞ͵źƓŅƚ ε ƓĻǣƷ ĬǤ
ƓƚķĻΝƦΞ͵ƓĻǣƷ͵źź ʹ 5ǤƓğƒźĭ LƒƦƌĻƒĻƓƷğƷźƚƓ ʹ ŷźƭ źƭ ƷŷĻ ƭğƒĻ ğƭ ĭƚķĻƭ ǞƩźƷƷĻƓ ǒƓķĻƩ ķĻŅźƓźƓŭ ƚŅ ƌźƓƉĻķ ƌźƭƷƭ͵ ...ƭźƓŭ ƒğƌƌƚĭΛΜ ğƓķ
ŅƩĻĻƓƚķĻΛΜ ƷŷĻƩĻ źƭ ƷŷĻ ĭğƦğĬźƌźƷǤ ƚŅ ķǤƓğƒźĭğƌƌǤ ğƌƌƚĭğƷźƓŭ ε ŅƩĻĻźƓŭ ǝğƩźğĬƌĻ͵ LƷ źƭ źķĻƓƷźĭğƌ Ʒƚ
ğƩƩğǤ źƒƦƌĻƒĻƓƷğƷźƚƓ ĻǣĭĻƦƷ ƷŷğƷ ƷŷĻ ƓĻǣƷ ŅźĻƌķ źƭ ğƓ ƦƚźƓƷĻƩ ƩğƷŷĻƩ ƷŷğƓ ğƓ źƓƷĻŭĻƩ͵
bh9 ʹ ağƆƚƩ ķĻƒĻƩźƷ ƚŅ ķǤƓğƒźĭ źƒƦƌĻƒĻƓƷğƷźƚƓ źƭ ƷŷğƷ źƷ ƒğǤ ĬĻ ƒƚƩĻ ƷźƒĻ ĭƚƓƭǒƒźƓŭ Ʒƚ ĭğƌƌ
ǒƦƚƓ ƷŷĻ ƭǤƭƷĻƒ Ʒƚ ğƌƌƚĭğƷĻ ε ŅƩĻĻ ƭƷƚƩğŭĻ ƷŷğƓ Ʒƚ ƒğƓźƦǒƌğƷĻ ğ ƦƩƚŭƩğƒƒĻƩΏ ƒğƓğŭĻķ ƌźƭƷ͵
ağƆƚƩ ğķǝğƓƷğŭĻ źƭ ƷŷğƷ ğ ƭĻƷ ƚŅ ƓƚķĻƭ źƭ ƓƚƷ ƩĻƭĻƩǝĻķ źƓ ğķǝğƓĭĻ ŅƚƩ ǒƭĻ͵
SORTING
Introduction
· Sorting is the process of arranging items in a certain sequence or in different sets . · The main purpose of sorting information is to optimize it"s usefulness for a specific tasks. · Sorting is one of the most extensively researched subject because of the need to speed up the operations on thousands or millions of records during a search operation.Types of Sorting :
· Internal Sorting
An internal sort is any data sorting process that takes place entirely within the main memory of a computer. This is possible whenever the data to be sorted is small enough to all be held in the main memory. For sorting larger datasets, it may be necessary to hold only a chunk of data in memory at a time, since it won"t all fit. The rest of the data is normally held on some larger, but slower medium, like a hard-disk. Any reading or writing of data to and from this slower media can slow the sorting process considerably· External Sorting Many important sorting applications involve processing very large files, much too large
to fit into the primary memory of any computer. Methods appropriate for such applications are called external methods, since they involve a large amount of processing external to the central processing unit. There are two major factors which make external algorithms quite different: ڬ First, the cost of accessing an item is orders of magnitude greater than any bookkeeping or calculating costs. ڬ Second, over and above with this higher cost, there are severe restrictions on access, depending on the external storage medium used: for example, items on a magnetic tape can be accessed only in a sequential mannerWell Known Sorting methods : ->Insertion sort, Merge sort, Bubble sort, Selection sort, Heap sort, Quick sort
INSERTION SORT
Insertion sort is the simple sorting algorithm which sorts the array by shifting elements one by one. ->OFFLINE sorting-This is the type of sorting in which whole input sequence is known. The number of inputs is fixed in offline sorting. ->ONLINE sorting-This is the type of sorting in which current input sequence is known and future input sequence is unknown i.e in online sort number inputs may increase. INSERTION SORT ALGORITHM: int a[6]={5,1,6,2,4,3}; int i,j,key; for(i=1;i<6;i++) { key=a[i]; j=i-1; while(j>=0 && keyAs we can see here, in insertion sort, we pick up a key,
andcompares it with elements before of it.
5
In first step, there is one comparison.
( partially sorted list)1 is compared with 5 and is inserted before 5.
6 is greater than 1 and 5, so there is no swap.
2 is smaller than 5 and 6 but greater than 1, so it is inserted after 1. And this goes on...( complete sorted list)
In insertion sort there is a single pass ,but there are many steps.Number of steps utmost in Insertion sort is:
1+2+3......................+n , where n is number of elements in the list. =((n-1)n)/2 =O (n*n) (TIME COMPLEXITY) Ў Њ Џ Ћ Ѝ Ќ Ў Њ Џ Ћ Ѝ Ќ Џ Ћ Ѝ Ќ Њ Ў Џ Ћ Ѝ Ќ ЎЊ Ў
Њ Ў Џ
Њ Ћ Ў Џ Ѝ ЌЊ Ћ Ѝ Ў Џ
Њ Ћ Ќ Ѝ Ў ЏPseudo code for insertion sort: Input: n items Output: sorted items in ascending order. ->compare item1 and item2 if (item1>item2 ),then SWAP else , no swapping A partially sorted list is generated ->Then scan next item and compare with item1 and item2 and then continue .
ADVANTAGES OF INSERTION SORT:
* Simple implementation. * Efficient for small data sets. * Stable i.e does not change the relative order of elements with same values. * Online i.e can sort a list as it receives it.LIMITATIONS OF INSERTION SORT:
* The insertion sort repeatedly scans the list of items, so it takes more time.*With n squared steps required for every n elements to be sorted , the insertion sort does not
deal well with a huge list. Therefore insertion sort is particularly useful when sorting a list of few items.REAL LIFE APPLICATIONS OF INSERTION SORT:
* Insertion sort can used to sort phone numbers of the customers of a particular company. * It can used to sort bank account numbers of the people visiting a particular bank.MERGE SORT Merge sort is a recursive algorithm that continually splits a list .In merge sort parallel
comparisons between the elements is done. It is based on "divide and conquer" paradigm.Algorithm for merge sort:
void mergesort(int a[],int lower,int upper) { int mid; if(upper >lower) { mid=(lower+upper)/2; mergesort(a,lower,mid); mergesort(a,mid+1,upper); merge(a,lower,mid,mid+1,upper); } } void merge(int a[],int lower1,int upper1,int lower2,int upper2) { int p,q,j,n; int d[100]; p=lower1; q=lower2; n=0; while((p<=upper1)&& (q<=upper2)) { d[n++]=(a[p]Б Ћ В Ѝ Ў Ќ Њ Џ
ЏБ Ћ В Ѝ Ў Ќ Њ Џ
Б Ћ В Ѝ Њ Џ Ў Ќ Ћ Ѝ В Џ Њ Ќ Ў Ћ Б Ќ Ў Ѝ В Њ Џ Ћ Ѝ Б В Њ Ќ Ў ЏЊ Ћ Ќ Ѝ Ў Џ Б В
*Divide it in two at the midpoint. *Conquer each side in turn by recursive sorting. *Merge two halves together.TIME COMPLEXITY
: There are total log2 n passes in merge sort and in each pass there are n comparisons atmost.
Therefore total number of comparisons=O (n * log2 n).
In 3 way merge sorting time complexity is O (n log3 n).
*k way merge is possible in merge sort where k is utmost n/2 i.e kLIMITATIONS OF MERGE SORT
: * It uses a lot of memory. * It uses extra space proportional to n. * It slows down when attempting to sort very large data.APPLICATIONS OF MERGE SORT:
* Merge sort operation is useful in online sorting where list to be sorted is received a piece at a
time instead of all at the beginning, for example sorting of bank account numbers.Binary Search Trees and AVL Trees
Introduction
· Binary search trees are an excellent data structure to implement associative arrays, maps, sets, and similar interfaces. · The main difficulty, as discussed in last lecture, is that they are efficient only when they are balanced. · Straightforward sequences of insertions can lead to highly unbalanced trees with poor asymptotic complexity and unacceptable practical efficiency. · The solution is to dynamically rebalance the search tree during insert or search operations. · We have to be careful not to destroy the ordering invariant of the tree while we rebalance. · Because of the importance of binary search trees, researchers have developed many different algorithms for keeping trees in balance, such as AVL trees, red/black trees, splay trees, or randomized binary search trees.·
· In this lecture we discuss AVL trees, which is a simple and efficient data structure to maintain balance. · It is named after its inventors, G.M. Adelson-Velskii and E.M. Landis, who described it in 1962.Height Invariant
. Ordering Invariant. · At any node with key k in a binary search tree, all keys of the elements in the left subtree are strictly less than k, while all keys of the elements in the right subtree are strictly greater than k. · To describe AVL trees we need the concept of tree height, which we define as the maximal length of a path from the root to a leaf. So the empty tree has height 0, the tree with one node has height 1, a balanced tree with three nodes has height 2. · If we add one more node to this last tree is will have height 3. Alternatively, we can define it recursively by saying that the empty tree has height 0, and the height of any node is one greater than the maximal height of its two children.·
· AVL trees maintain a height invariant (also sometimes called a balance invariant).·
Height Invariant.
· At any node in the tree, the heights of the left and right subtrees differs by at most 1.Rotations: How they work
Left Rotation (LL)
Imagine we have this situation:
To fix this, we must perform a left rotation, rooted at A. This is done in the following steps: b becomes the new root. a takes ownership of b"s left child as its right child, or in this case, null. b takes ownership of a as its left child.The tree now looks like this:
Right Rotation (RR) A right rotation is a mirror of the left rotation operation described above. Imagine we have this situation:Figure 1-3
c / b / a To fix this, we will perform a single right rotation, rooted at C. This is done in the following steps: b becomes the new root. c takes ownership of b"s right child, as its left child. In this case, that value is null. b takes ownership of c, as it"s right child.The resulting tree:
5ƚǒĬƌĻ wƚƷğƷźƚƓƭ ΛƌĻŅƷΏƩźŭŷƷΜ
Our initial reaction here is to do a single left rotation. Let"s try that Our left rotation has completed, and we"re stuck in the same situation. If we were to do a single right rotation in this situation, we would be right back where we started. What"s causing this?The answer is that this is a result of the right subtree having a negative balance. In other words,because the right subtree was left heavy, our rotation was not sufficient. What can we do? The answer is to perform a right rotation on the right subtree. Read that again. We will perform a right rotation on the right subtree. We are not rotating on our current root. We are rotating on our right child. Think of our right subtree, isolated from our main tree, and perform a right rotation on it: After performing a rotation on our right subtree, we have prepared our root to be rotated left.Here is our tree now:
Looks like we"re ready for a left rotation.5ƚǒĬƌĻ wƚƷğƷźƚƓƭ ΛƩźŭŷƷΏƌĻŅƷΜ
A double right rotation, or right-left rotation, or simply RL, is a rotation that must be performed when attempting to balance a tree which has a left subtree, that is right heavy. This is a mirror operation of what was illustrated in the section on Left-Right Rotations, or double left rotations. Let"s look at an example of a situation where we need to perform aRight-Left rotation.
In this situation, we have a tree that is unbalanced. The left subtree has a height of 2, and the right subtree has a height of 0. This makes the balance factor of our root node, c, equal to -2. What do we do? Some kind of right rotation is clearly necessary, but a single right rotation will not solve our problem. a \ c / b Looks like that didn"t work. Now we have a tree that has a balance of 2. It would appear that we did not accomplish much. That is true. What do we do? Well, let"s go back to the original tree, before we did our pointless right rotation: The reason our right rotation did not work, is because the left subtree, or "a", has a positive balance factor, and is thus right heavy. Performing a right rotation on a tree that has a left subtree that is right heavy will result in the problem we just witnessed. What do we do? The answer is to make our left subtree left-heavy. We do this by performing a left rotation our left subtree. Doing so leaves us with this situation: This is a tree which can now be balanced using a single right rotation. We can now perform our right rotation rooted at C.LƓĭƩĻğƭźƓŭ ƷŷĻ ƭƦĻĻķ ĬǤ ƒźƓźƒźǩźƓŭ ƷŷĻ ŷĻźŭŷƷ ķźŅŅĻƩĻƓĭĻ źƭ ƷŷĻ ƒğźƓ ƚŅ ![ ƷƩĻĻ͵
hƦĻƩğƷźƚƓƭ ƌźƉĻ źƓƭĻƩƷźƚƓƭͲķĻƌĻƷźƚƓƭ ĻƷĭ ĭğƓ ĬĻ ķƚƓĻ źƓ ƷźƒĻ ƚŅ hΛƌƚŭ ƓΜͲĻǝĻƓ źƓ ƷŷĻ ǞƚƩƭƷ ĭğƭĻ͵
Ļ͵ŭ͵LƓ ğ ĭƚƒƦƌĻƷĻ ĬğƌğƓĭĻķ ƷƩĻĻͲƷŷĻ ƌĻŅƷ ğƓķ ƩźŭŷƷ ƭǒĬƷƩĻĻƭ ƚŅ ğƓǤ ƓƚķĻ Ǟƚǒƌķ ŷğǝĻ ƭğƒĻ ŷĻźŭŷƷ͵
IĻźŭŷƷ ķźŅŅĻƩĻƓĭĻ źƭ Љ͵{ǒƦƦƚƭĻ Iƌ źƭ ƷŷĻ ŷĻźŭŷƷ ƚŅ ƌĻŅƷ ƭǒĬ ƷƩĻĻ ğƓķ IƩ źƭ ƷŷĻ ŷĻźŭŷƷ ƚŅ ƩźŭŷƷ ƭǒĬ ƷƩĻĻͲƷŷĻƓ ŅƚƌƌƚǞźƓŭ ƦƩƚƦĻƩƷźĻƭ
ƒǒƭƷ ĬĻ ƭğƷźƭŅźĻķ ŅƚƩ ƷŷĻ ƷƩĻĻ Ʒƚ ĬĻ ğƓ ![ ƷƩĻĻʹ
Њ͵LƷ ƒǒƭƷ ĬĻ ğ .{͵Ћ͵IĻźŭŷƷ ƚŅ ƌĻŅƷ ƭǒĬ ΑƷƩĻĻ Α IĻźŭŷƷ ƚŅ ƩźŭŷƷ ƭǒĬΏƷƩĻĻѡўЊ͵
ź͵Ļ͵ IƌΏIƩѡўЊ IƌΏIƩўΟΏЊͲЉͲЊΠ Ļ͵ŭ͵ ΛЋΜ ΛЊΜΛЉΜ
.ğƌğƓĭźƓŭ ŅğĭƷƚƩўIƌΏIƩ͵LƓ ƷŷĻ ğĬƚǝĻ ķźğŭƩğƒͲĬğƌğƓĭźƓŭ ŅğĭƷƚƩ ŅƚƩ ƩƚƚƷ ƓƚķĻ źƭ ЋͲƭƚͲźƷ źƭ ƓƚƷ ğƓ ![ ƷƩĻĻ͵ LƓ ƭǒĭŷ ĭğƭĻƭͲƷŷĻ ƷƩĻĻ
ĭğƓ ĬĻ ĬğƌğƓĭĻķ ĬǤ ƩƚƷğƷźƚƓƭ͵
ŷĻƩĻ ğƩĻ Ѝ ƷǤƦĻ ƚŅ ƩƚƷğƷźƚƓƭʹ
Њ͵[[ wƚƷğƷźƚƓΛƌĻŅƷΏƌĻŅƷΜ Ћ͵ww wƚƷğƷźƚƓΛƩźŭŷƷΏƩźŭŷƷΜ Ќ͵[w wƚƷğƷźƚƓΛƌĻŅƷΏƩźŭŷƷΜ Ѝ͵w[ wƚƷğƷźƚƓΛƩźŭŷƷΏƌĻŅƷΜ ! . / [[ wƚƷğƷźƚƓʹ ΛњЋΜ ΛњЊΜ ΛЉΜ.ğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ! źƭ њЋ͵!ƦƦƌǤźƓŭ [[ ƩƚƷğƷźƚƓͲǞĻ ŭĻƷͲ
ΛЉΜΛЉΜ
ΛЉΜbƚǞͲƷŷźƭ źƭ ğ ŷĻźŭŷƷ ĬğƌğƓĭĻķ ƷƩĻĻ͵
ww wƚƷğƷźƚƓʹ ΛΏЋΜ ΛΏЊΜ ΛЉΜ ! . ĭ / . ! ! . /.ğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ! źƭ ΏЋ͵!ƦƦƌǤźƓŭ ww ƩƚƷğƷźƚƓͲǞĻ ŭĻƷͲ
ΛЉΜΛЉΜ
ΛЉΜbƚǞͲ Ʒŷźƭ źƭ ğ ŷĻźŭŷƷ ĬğƌğƓĭĻķ ƷƩĻĻ͵
[w wƚƷğƷźƚƓʹ ΛΏЋΜ ΛΏЊΜ .ğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ! źƭ ΏЋ ΛЉΜ ΛЉΜΛЉΜ
ΛЉΜ
!ƦƦƌǤźƓŭ ww wƚƷğƷźƚƓͲ ǞĻ ŭĻƷ ğ ŷĻźŭŷƷ ĬğƌğƓĭĻķ ƷƩĻĻ͵
w[ wƚƷğƷźƚƓʹ ΛΏЋΜ
ΛњЊΜ
! . . . ! / . ! ! . / ! . . / ΛЉΜ.ğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ! źƭ ΏЋͳğƦƦƌǤźƓŭ w[ wƚƷğƷźƚƓͲǞĻ ŭĻƷͲ
ΛЉΜΛЉΜ
ΛЉΜ
bƚǞͲƷŷźƭ źƭ ğ ŷĻźŭŷƷ ĬğƌğƓĭĻķ ƷƩĻĻ͵
v͵ !ƩƩğƓŭĻ ķğǤƭ ƚŅ ǞĻĻƉʹΏ{ǒƓķğǤͲaƚƓķğǤͲǒĻƭķğǤͲĻķƓĻƭķğǤͲŷǒƩƭķğǤͲCƩźķğǤͲ{ğƷǒƩķğǤͲ źƓ ğƓ ![ ƷƩĻĻ͵
ЊƭƷ ƭƷĻƦʹΏĻ ŷğǝĻ Ʒƚ ğƩƩğƓŭĻ ƷŷĻƭĻ ķğǤƭ ğƌƦŷğĬĻƷźĭğƌƌǤͲğƓķ ƷŷĻ ĭƚƓƭƷƩǒĭƷĻķ ƷƩĻĻ ƭŷƚǒƌķ ƭğƷźƭŅǤ ƷŷĻ
ĭƚƓķźƷźƚƓƭ ƚŅ ğƓ ![ ƩĻĻ͵{ƷğƩƷźƓŭ ǞźƷŷ {ǒƓķğǤΛƭǒƓΜʹ
Λaѡ{ѡΜ
IĻƩĻͲƷŷĻ ĬğƌğƓĭĻ ŅğĭƷƚƩ ŅƚƩ ğƌƌ ƷŷƩĻĻ ƓƚķĻƭ źƭ Љ͵!ƌƭƚͲźƷ źƭ ğ .{͵{ƚͲźƷ ƭğƷźƭŅźĻƭ ğƌƌ ƷŷĻ ĭƚƓķźƷźƚƓƭ ŅƚƩ
ğƓ ![ ƷƩĻĻ͵
ЋƓķ ƭƷĻƦʹΏ bƚǞͲĻķƓĻƭķğǤ źƭ Ʒƚ ĬĻ źƓƭĻƩƷĻķͲ!ƭ ΛΜѢΛΜͲƭƚͲźƷ Ǟźƌƌ ĬĻ ƦƌğĭĻķ ğƷ ƩźŭŷƷ ƚŅ ǒĻƭķğǤ ŅƚƩ
ƭğƷźƭŅǤźƓŭ .{ ĭƚƓķźƷźƚƓƭʹ ! . / {ǒƓǒĻ aƚƓ
{ǒƓbƚǞͲĬğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ {ǒƓķğǤўΏЊ .ğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ aƚƓķğǤўΏЊ .ğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ǒĻƭķğǤўЉ .ğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ĻķƓĻƭķğǤўΏЊ IĻƓĭĻͲźƷ źƭ ğƓ ![ ƷƩĻĻ͵
ЌƩķ ƭƷĻƦʹΏ
bƚǞͲŷǒƩƭķğǤ ŷğƭ Ʒƚ ĬĻ źƓƭĻƩƷĻķ͵!ƭ ğƌƦŷğĬĻƷźĭğƌƌǤͲŷǒƩƭķğǤѡǒĻƭķğǤͲƭƚ źƷ Ǟźƌƌ ĬĻ ğƷ ƷŷĻ ƌĻŅƷ ƚŅ ǒĻƭķğǤ͵
IĻƩĻͲĬğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ƭǒƓўΏЊ
.ğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ƷǒĻͲǞĻķͲƷŷǒўЉ
{ƚͲźƷ źƭ ğƓ ![ ƷƩĻĻ͵ ЍƷŷ ƭƷĻƦʹ
bƚǞͲCƩźķğǤ ğƓķ {ğƷǒƩķğǤ ğƩĻ Ʒƚ ĬĻ źƓƭĻƩƷĻķͲ
aƚƓƒƚƓ
ƭǒƓ
ƒƚƓ Ʒŷǒ
ƷǒĻ
ǞĻķ
Ʒŷǒ
ƭǒƓ
IĻƩĻͲĬğƌğƓĭĻ ŅğĭƷƚƩ ƚŅ ğƌƌ ƷŷĻ ķğǤƭўЉ͵ {ƚͲźƷ źƭ ğƓ ![ ƷƩĻĻ͵
Use :
1. Search is O(log N) since AVL trees are always balanced.
2. Insertion and deletions are also O(logn) 3. The height balancing adds no more than a constant factor to the speed of insertion. 4. AVL Tree height is less than BST. 5. Stores data in balanced way in a disk.Limitations
1. Difficult to program & debug; more space for balance factor.
2. Asymptotically faster but rebalancing costs time. 3. Most large searches are done in database systems on disk and use other structures (e.g. B-trees). 4. May be OK to have O(N) for a single operation if total run time for many consecutive operations is fast (e.g. Splay trees).Threaded BST
A threaded binary tree defined as follows:
"A binary tree is threaded by making all right child pointers that would normally be null point tothe inorder successor of the node (if it exists) , and all left child pointers that would normally be
null point to the inorder predecessor of the node." A threaded binary tree makes it possible to traverse the values in the binary tree via a lineartraversal that is more rapid than a recursive in-order traversal. It is also possible to discover the
parent of a node from a threaded binary tree, without explicit use of parent pointers or a stack, albeit slowly. This can be useful where stack space is limited, or where a stack of parent pointers is unavailable (for finding the parent pointer via DFS).ƷǒĻ
Ʒŷǒ ǞĻ ŅƩź ƭğƷ
ƒƚƓ
7.Types of threaded binary trees
1. Single Threaded: each node is threaded towards either(right)" the in-order
predecessor or" successor.2. Double threaded: each node is threaded towards both(left & right)" the in-order
predecessor and" successor.SPANNING TREE:- ->A tree is a connected undirected graph with no cycles.It is a spanning tree of a graph G if it
spans G (that is, it includes every vertex of G) and is a subgraph of G (every edge in the tree belongs to G). ->A spanning tree of a connected graph G can also be defined as a maximal set of edges of G that contains no cycle, or as a minimal set of edges that connect all vertices. -> So key to spanning tree is number of edges will be 1 less than the number of nodes. ⮚ no. of edges=no. of nodes-1 example:- Weighted Graphs:- A weighted graph is a graph, in which each edge has a weight (some real number). Weight of a Graph:- The sum of the weights of all edges.Minimum SPANNING TREE:-
Minimum spnning tree is the spanning tree in which the sum of weights on edges is minimum. NOTE:- The minimum spanning tree may not be unique. However, if the weights of all the edges are pairwise distinct, it is indeed unique. example:- There are a number of ways to find the minimum spanning tree but out of them most popular methods are prim"s algorithm and kruskal algorithm.PRIM"S ALGORITHM:-
Prim"s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree hat includes every vertex , where the total weight of all the edges in the tree is minimized. steps:-1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the
tree, find the minimum-weight edge, and transfer it to the tree.3. Repeat step 2 (until all vertices are in the tree).
step-0 choose a. step-1 since (a,b) is minimum. step-2 since (b,d) is minimum. step-3 since weight of (d,c)is minimum. step-4 since (c,f) is minimum. step-5 since weight of (f,g) is less than (f,e). step-6 weight of (g,e) is greater than weightof(f,e). kruskal algorithm:- The Kruskal"s Algorithm is based directly on the generic algorithm. Unlike Prim"s algorithm, we make a different choises of cut. · Initially, trees of the forest are the vertices (no edges). · In each step add the cheapest edge that does not create a cycle. · Observe that unlike Prim"s algorithm, which only grows one tree, Kruskal"s algorithm grows a collection of trees(a forest). · Continue until the forest "merge to" a single tree.This is a minimum spanning tree.
example:-I!{ILbD
LƓƷƩƚķǒĭƷźƚƓʹ Hashing involves less key comparison and searching can be performed in constant time. Suppose we have keys which are in the range 0 to n-1 and all of them are unique. We can take an array of size n and store the records in that array based on the condition that key and array index are same. The searching time required is directly proportional to the number of records in the file. Weassume a function f and if this function is applied on key K it returns i, an index so that
i=f(K).then entry in the access table gives the location of record with key value K. Access Table File storage of n recordsINFORMATIONRETRIVAL USINGACCESS TABLE.
HASH FUNCTIONS
The main idea behind any hash function is to find a one to one correspondence between a key value and index in the hash table where the key value can be placed. There are two principal criteria deciding a hash function H:K->I are as follows: i. The function H should be very easy and quick to compute. K1 K2 . . K . . ii. The function H should achieve an even distribution of keys that actually occur across the range of indices. Some of the commonly used hash functions applied in various applications are:DIVISION:
It is obtained by using the modulo operator. First convert the key to an integer then divide it by the size of the index range and take the remainder as the result.H(k)=k%i if indices start from 0
H(k)=(k%i)+1 if indices start from 1
MID -SQUARE:
The hash function H is defined by H(k)=x where x is obtained by selecting an appropriate number of bits or digits from the middle of the square of the key value k.it is criticized as it is time consuming.FOLDING:
The key is partitioned into a number of parts and then the parts are added together. There are many variation in this method one is fold shifting method where the even number parts are each reversed before the addition. Another is the fold boundary method here the two boundary parts are reversed and then are added with all other parts.3. COLLISION RESOLUTION TECHNIQUES
If for a given set of key values the hash functions does not distribute then uniformly over the hash table, some entries are there which are empty and in some entries more than one key value are to be stored. Allotment of more than one key values in one location in the hash table is called collision. H:K->IHASH TABLE
Collision in hashing cannot be ignored whatever the size of the hash tables. There are several techniques to resolve collisions. Two important methods are: i. Closed hashing(linear probing) ii. Open hashing(chaining)CLOSED HASHING:
The simplest method to resolve a collision is closed hashing. Here the hash table is considered as circular so that when the last location is reached the search proceeds to the first location of the table. That is why this is called closed hashing. The search will continue until any one case occurs:1. The key value is found.
2. Unoccupied location is encountered.
3. It reaches to the location where the search was started.
DRAWBACK OF CLOSED HASHING: As the half of the hash table is filled there is a tendency towards clustering. The key values are clustered in large groups and as a result sequential search becomes slower and slower.Some solutions to avoid this are:
a. Random probing b. Double hashing or rehashing c. Quadratic probing 1 0 8 7 8 4 4 3 4 6 19 10 4959 , 31 , 7 7
3343
35,62
RANDOM PROBING: This method uses a pseudo random number generator to generate a random sequence of locations, rather than an ordered sequence as was the case in linear probing method. The random sequence generated by the pseudo random number generator contains all positions between 1 and h, the highest location of the hash table.
I=(i+m)%h+1
i is the number in the sequence m and h are integers that are relatively prime to each other.DOUBLE HASHING:
When two hash functions are used to avoid secondary clustering then it is called double hashing. The second function should be selected in such a way that hash address generated by two hash functions are distinct and the second function generates a value m for the key k so that m and h are relatively prime. (k)=(k%h)+1 (k)=(k%(h-4))+1QUADRATIC PROBING:
It is a collision resolution method that eliminates the primary clustering problem of linear probing. For quadratic probing the next location after i will be i+,i++...... etc.H(k)+%h for i=1,2,3.....
OPEN HASHING
In closed hashing two situations occurs 1. If there is a table overflow situation 2. If the key values are haphazardly intermixed. To solve this problem another hashing is used open chaining.4.ADVANTAGES AND DISADVANTAGES OF CHAINING
1. Overflow situation never arises. Hash table maintains lists which can contain any
number of key values.2. Collision resolution can be achieved very efficiently if the lists maintain an ordering
of keys so that keys can be searched quickly.3. Insertion and deletion become quick and easy task in open hashing. Deletion proceeds
in exactly the same way as deletion of a node in single linked list.4. Open hashing is best suitable in applications where number of key values varies
drastically as it uses dynamic storage management policy.5. The chaining has one disadvantage of maintaining linked lists and extra storage space
for link fields.FILE STRUCTURE
File Organisation:-
It is the organisation of records in a file.Record:-
It is the collection of related fields.Field:-
It is the smallest logically meaningful unit of information in a file. Secondary memory structure:- Seek time:-It is the track access time by R/w haed.
Latency time:- It is the time taken for the sector movement. "L< S" Data access time:-It is the time taken for the file movement.Student file:-
KEY:-
Key is the field which uniquely identify the records. (1) Key must have distinct value. (no duplicate) (2) Key must be in proper order.File:-
Records binary relation:- No. of records(rows) is called cardinality. No. of fields(columns) is called degree. APPLICATION:-
ǤƦĻƭ ƚŅ ŅźƌĻƭ Α Њ͵ {ĻƩźğƌ CźƌĻƭ Ћ͵ {ĻƨǒĻƓƷźğƌ CźƌĻƭ Ќ͵ 5źƩĻĭƷ ƚƩ wğƓķƚƒ CźƌĻƭ Ѝ͵ LƓķĻǣ {ĻƨǒĻƓƷźğƌ CźƌĻƭ {ĻƩźğƌ CźƌĻƭ Α
· ŷźƭ ƷǤƦĻ ƚŅ ŅźƌĻ Ǟğƭ ǒƭĻķ źƓ ЊВЎЉΏЊВЏЉ͵
· ŷĻ ƩĻĭƚƩķƭ ğƩĻ ğƩƩğƓŭĻķ ƚƓĻ ğŅƷĻƩ ğƓƚƷŷĻƩ͵
· bĻǞ ƩĻĭƚƩķ źƭ ğķķĻķ ğƷ ƷŷĻ ĻƓķ ƚŅ ƷŷĻ ŅźƌĻ͵
· ŷĻƭĻ ŅźƌĻƭ ǞĻƩĻ ƭƷƚƩĻķ źƓ ƒğŭƓĻƷźĭ ƷğƦĻƭ͵
· ŷĻƓ ƷŷĻ ƭźǩĻ ƚŅ ƷŷĻ ŅźƌĻ źƓĭƩĻğƭĻƭͲ ƷŷĻ ƷźƒĻ ƩĻƨǒźƩĻķ Ʒƚ ğĭĭĻƭƭ ķğƷğ ĬĻĭƚƒĻƭ ƒƚƩĻ͵ ŷźƭ źƭ
ĬĻĭğǒƭĻ źƷ ĭğƓ ƚƓƌǤ ğƦƦƌǤ ƌźƓĻğƩ ƭĻğƩĭŷ͵
· [ƚŭźĭğƌ ƚƩķĻƩźƓŭ ў tŷǤƭźĭğƌ ƚƩķĻƩźƓŭ
· ŷĻƭĻ ğƩĻ ǒƭĻķ źƓ ƭĻĭƚƓķğƩǤ ŅźƌĻƭ͵
· 9ǣğƒƦƌĻƭ Α ! ƒğƷĻƩźğƌ ǞźƷŷƚǒƷ ƦğŭĻ Ɠƚ͵ IĻƩĻ ƭĻğƩĭŷźƓŭ Ǟźƌƌ ĬĻ ķźŅŅźĭǒƌƷ ķǒĻ Ʒƚ ƌğĭƉ ƚŅ ƦğŭĻ
ƓǒƒĬĻƩ͵
{ĻƨǒĻƓƷźğƌ CźƌĻ Α · ŷĻ ƩĻĭƚƩķƭ ğƩĻ ƚƩķĻƩƭ͵ · ͵ ŷĻƩĻ źƭ Ɠƚ ƉĻǤ ǝğƌǒĻ͵· DğƦƭ ğƩĻ ƌĻŅƷ ƭƚ ƷŷğƷ ƓĻǞ ƩĻĭƚƩķƭ ĭğƓ ĬĻ ğķķĻķ ƷŷĻƩĻ Ʒƚ ƒğźƓƷğźƓ ƚƩķĻƩźƓŭ͵
· bĻǞ ƩĻĭƚƩķ źƭ ğķķĻķ źƓ ŭğƦƭ ƌĻŅƷ ĬĻƷǞĻĻƓ ƩĻĭƚƩķƭ ğĭĭƚƩķźƓŭ Ʒƚ ƚƩķĻƩźƓŭ͵
· ŷĻƭĻ ŅźƌĻƭ ǞĻƩĻ ƭƷƚƩĻķ źƓ ƒğŭƓĻƷźĭ ƷğƦĻƭ͵
· ŷĻƓ ƷŷĻ ƭźǩĻ ƚŅ ƷŷĻ ŅźƌĻ źƓĭƩĻğƭĻƭͲ ƷŷĻ ƷźƒĻ ƩĻƨǒźƩĻķ Ʒƚ ğĭĭĻƭƭ ķğƷğ ĬĻĭƚƒĻƭ ƒƚƩĻ͵ ŷźƭ źƭ
ĬĻĭğǒƭĻ ƷŷĻƩĻ ğƩĻ Ɠƚ ƉĻǤ͵· [ƚŭźĭğƌ ƚƩķĻƩźƓŭ ƒğǤ ƓƚƷ ĬĻ Ļƨǒğƌ Ʒƚ tŷǤƭźĭğƌ ƚƩķĻƩźƓŭ͵
· ŷĻƭĻ ğƩĻ ǒƭĻķ źƓ ƒğƭƷĻƩ ŅźƌĻƭ͵
· 9ǣğƒƦƌĻƭ Α !ƩƩğƓŭźƓŭ ĭğƩķƭ źƓ ƭĻƨǒĻƓƷźğƌ ƚƩķĻƩ Λ! Ћ Ќ Ѝ Ў Џ А Б В ЊЉ W v YΜ
5źƩĻĭƷ ƚƩ wğƓķƚƒ CźƌĻƭΏ
· 9ğĭŷ ƩĻĭƚƩķ źƭ ğƭƭƚĭźğƷĻķ ǞźƷŷ ğ ķźƩĻĭƷ ŅǒƓĭƷźƚƓ͵
· ŷĻƩĻ ğƩĻ ƉĻǤ ǝğƌǒĻƭ͵ · ŷĻ ƩĻĭƚƩķƭ ŷğǝĻ ƒğƦƦźƓŭ͵ · 5źƭƉ ķĻǝźĭĻ ƌźƉĻ /5 ğƩĻ ǒƭĻķ͵ · {ĻğƩĭŷźƓŭ źƭ ƨǒźƷ ŅğƭƷĻƩ͵ · IğƭŷźƓŭ źƭ źƷƭ ĻǣƷĻƓƭźƚƓ͵· 5ǒĻ Ʒƚ ƒğƦƦźƓŭ ƒƚƩĻ ƭƦğĭĻ źƭ ƓĻĻķĻķ͵
· LƷ źƭ ƒƚƩĻ ĭƚƒƦƌĻǣ ƷŷğƓ ƷŷĻ ƦƩĻǝźƚǒƭ Ћ ŅźƌĻƭ͵
LƓķĻǣ {ĻƨǒĻƓƷźğƌ CźƌĻ Α · ŷźƭ Ǟğƭ źƓǝĻƓƷĻķ ĬǤ L.a͵ · ŷĻƭĻ ǒƭĻƭ źƓķźĭĻƭ͵ · !ĭĭĻƭƭ źƭ ƭĻƨǒĻƓƷźğƌ͵· LƓķĻǣźƓŭ ğƓķ ƭƚƩƷźƓŭ źƭ ƩğƓķƚƒ͵
· ŷĻƭĻ ŷğǝĻ ƉĻǤƭ͵· ! ŭƩƚǒƦ ƚŅ ƉĻǤƭ ğƩĻ ŭźǝĻƓ ƚƓĻ źƓķĻǣ͵
· 5źƭƉ ķĻǝźĭĻ źƭ ǒƭĻķ ŅƚƩ ƭƷƚƩğŭĻ͵
· {ĻğƩĭŷźƓŭ źƭ ŅğƭƷ ğƭ ƷŷĻ źƓķĻǣ źƭ ƭĻğƩĭŷĻķ ğƓķ ƷŷĻƓ ƷŷĻ ƉĻǤ źƭ ƭĻğƩĭŷĻķ͵
· ŷźƭ źƭ ǒƭĻķ źƓ ĬğƓƉźƓŭ͵· 9ǣğƒƦƌĻ Α /ƚƓƷĻƓƷƭ ƚŅ ğ ĬƚƚƉ͵ ŷĻ ƷƚƦźĭƭ ğƩĻ ƷŷĻ ƉĻǤƭ͵ ŷĻǤ ŷğǝĻ źƓķźĭĻƭ ƌźƉĻ ƦğŭĻ ƓǒƒĬĻƩ͵
ŷğƷ ƷƚƦźĭ ĭğƓ ĬĻ ŅƚǒƓķ źƓ ƷŷğƷ ƦğŭĻ Ɠƚ͵ ŷĻƓ ƓĻǞ źƓŅƚƩƒğƷźƚƓ ƓĻĻķƭ Ʒƚ ĬĻ ğķķĻķͲ ğ ƦƚźƓƷĻƩ źƭ
ƷğƉĻƓ Ʒƚ ƦƚźƓƷ Ʒƚ ğ ƓĻǞ ƌƚĭğƷźƚƓ ƌźƉĻ źƓ ğƦƦĻƓķźǣ ƚŅ ğ ĬƚƚƉ͵ ŷźƭ ƭğǝĻƭ ƷŷĻ ƷźƒĻ ğƓķ ĻƩƩƚƩƭ ƷŷğƷ
ƚĭĭǒƩ ķǒĻ Ʒƚ ƭŷźŅƷźƓŭ ƷŷĻ ƌğƷĻƩ ķğƷğ ğŅƷĻƩ źƓƭĻƩƷźƚƓ͵
YĻǤΏ ! ǝźƷğƌͲ ĭƩǒĭźğƌ ĻƌĻƒĻƓƷ ƓƚƷĭŷĻķ ğƓķ ŭƩƚƚǝĻķͲ ǒƭǒğƌƌǤ ƒĻƷğƌ źƒƦƌĻƒĻƓƷ ƷŷğƷ źƭ ƷǒƩƓĻķ Ʒƚ ƚƦĻƓ ƚƩ ĭƌƚƭĻ ğ
ƌƚĭƉ͵ ŷĻ ƉĻǤƭ ŷğǝĻ ƷŷĻ ĭŷğƩğĭƷĻƩźƭƷźĭƭ ƚŅ ŷğǝźƓŭ ǒƓźƨǒĻ ğƷƷƩźĬǒƷĻ͵
LƓ ķğƷğĬğƭĻ ƒğƓğŭĻƒĻƓƷ ƭǤƭƷĻƒƭͲ ğ ƉĻǤ źƭ ğ ŅźĻƌķ ƷŷğƷ Ǥƚǒ ǒƭĻ Ʒƚ ƭƚƩƷ ķğƷğ͵
LƷ ĭğƓ ğƌƭƚ ĬĻ ĭğƌƌĻķ ğ ƉĻǤ ŅźĻƌķ Ͳ ƭƚƩƷ ƉĻǤͲ źƓķĻǣͲ ƚƩ ƉĻǤ ǞƚƩķ͵
CƚƩ ĻǣğƒƦƌĻͲ źŅ Ǥƚǒ ƭƚƩƷ ƩĻĭƚƩķƭ ĬǤ ğŭĻͲ ƷŷĻƓ ƷŷĻ ğŭĻ ŅźĻƌķ źƭ ğ ƉĻǤ͵
aƚƭƷ ķğƷğĬğƭĻ ƒğƓğŭĻƒĻƓƷ ƭǤƭƷĻƒƭ ğƌƌƚǞ Ǥƚǒ Ʒƚ ŷğǝĻ ƒƚƩĻ ƷŷğƓ ƚƓĻ ƉĻǤ ƭƚ ƷŷğƷ Ǥƚǒ ĭğƓ ƭƚƩƷ ƩĻĭƚƩķƭ
źƓ ķźŅŅĻƩĻƓƷ ǞğǤƭ͵hƓĻ ƚŅ ƷŷĻ ƉĻǤƭ źƭ ķĻƭźŭƓğƷĻķ ƷŷĻ ƦƩźƒğƩǤ ƉĻǤͲ ğƓķ ƒǒƭƷ ŷƚƌķ ğ ǒƓźƨǒĻ ǝğƌǒĻ ŅƚƩ Ļğĭŷ ƩĻĭƚƩķ͵
! ƉĻǤ ŅźĻƌķ ƷŷğƷ źķĻƓƷźŅźĻƭ ƩĻĭƚƩķƭ źƓ ğ ķźŅŅĻƩĻƓƷ ƷğĬƌĻ źƭ ĭğƌƌĻķ ğ ŅƚƩĻźŭƓ ƉĻǤ͵
[h/Yʹ LƓ ŭĻƓĻƩğƌ ğ ķĻǝźĭĻ ƚƦĻƩğƷĻķ ĬǤ ğ ƉĻǤͲ ĭƚƒĬźƓğƷźƚƓͲ ƚƩ ƉĻǤĭğƩķ ğƓķ ǒƭĻķ ŅƚƩ ŷƚƌķźƓŭͲ ĭƌƚƭźƓŭ ƚƩ
ƭĻĭǒƩźƓŭ ƷŷĻ ķğƷğ͵ŷĻ ƉĻǤ ƌƚĭƉ ƦƩźƓĭźƦƌĻ ƭƷğƷĻƭ ƷŷğƷ ƚƓĭĻ ƌƚĭƉ ĭğƓ ĬĻ ƚƦĻƓĻķ ƚƩ ŅğƭƷĻƓĻķ ĬǤ ƭƦĻĭźŅźĭ ƚƓĻ ƷǤƦĻ ƚŅ ƉĻǤƭ ƚƓƌǤ͵
LƓ ķźŭźƷğƌ ĻƌĻĭƷƩƚƓźĭƭ ƌğƷĭŷ źƭ ǒƭĻķ ŅƚƩ ƷĻƒƦƚƩğƩǤ ƭĻĭǒƩźƷǤ ǞŷźƌĻ ƌƚĭƉ źƭ ǒƭĻķ ŅƚƩ ƦĻƩƒğƓĻƓƷ ƭĻĭǒƩźƷǤ͵
CL[9 hwD!bL{!Lhb 9/IbLv...9{ʹ
ŷĻ ƭƷƩǒĭƷǒƩĻ ƚŅ ğ ŅźƌĻ ΛĻƭƦĻĭźğƌƌǤ ğ ķğƷğ ŅźƌĻΜͲ ķĻŅźƓĻķ źƓ ƷĻƩƒƭ ƚŅ źƷƭ ĭƚƒƦƚƓĻƓƷƭ ğƓķ ŷƚǞ ƷŷĻǤ ğƩĻ
ƒğƦƦĻķ ƚƓƷƚ ĬğĭƉźƓŭ ƭƷƚƩĻ͵!ƓǤ ŭźǝĻƓ ŅźƌĻ ƚƩŭğƓźǩğƷźƚƓ ƭǒƦƦƚƩƷƭ ƚƓĻ ƚƩ ƒƚƩĻ ŅźƌĻ ğĭĭĻƭƭ ƒĻƷŷƚķƭ͵
hƩŭğƓźǩğƷźƚƓ źƭ Ʒŷǒƭ ĭƌƚƭĻƌǤ ƩĻƌğƷĻķ Ʒƚ ĬǒƷ ĭƚƓĭĻƦƷǒğƌƌǤ ķźƭƷźƓĭƷ ŅƩƚƒ ğĭĭĻƭƭ ƒĻƷŷƚķƭ͵
ŷĻ ķźƭƷźƓĭƷźƚƓ źƭ ƭźƒźƌğƩ Ʒƚ ƷŷğƷ ĬĻƷǞĻĻƓ ķğƷğ ƭƷƩǒĭƷǒƩĻ ğƓķ ƷŷĻ ƦƩƚĭĻķǒƩĻƭ ğƓķ ŅǒƓĭƷźƚƓƭ ƷŷğƷ ƚƦĻƩğƷĻ
ƚƓ ƷŷĻƒ ΛźƓķĻĻķ ğ ŅźƌĻ ƚƩŭğƓźǩğƷźƚƓ źƭ ğ ƌğƩŭĻΏƭĭğƌĻ ķğƷğ ƭƷƩǒĭƷǒƩĻΜͲ ƚƩ Ʒƚ ƷŷğƷ ĬĻƷǞĻĻƓ ğ ƌƚŭźĭğƌ ƭĭŷĻƒğ
ƚŅ ğ ķğƷğĬğƭĻ ğƓķ ƷŷĻ ŅğĭźƌźƷźĻƭ źƓ ğ ķğƷğ ƒğƓźƦǒƌğƷźƚƓ ƌğƓŭǒğŭĻ͵
ŷĻƩĻ źƭ Ɠƚ ǝĻƩǤ ǒƭĻŅǒƌ ƚƩ ĭƚƒƒƚƓƌǤ ğĭĭĻƦƷĻķ ƷğǣƚƓƚƒǤ ƚŅ ƒĻƷŷƚķƭ ƚŅ ŅźƌĻ ƚƩŭğƓźǩğƷźƚƓʹ ƒƚƭƷ ğƷƷĻƒƦƷƭ
ĭƚƓŅǒƭĻ ƚƩŭğƓźǩğƷźƚƓ ǞźƷŷ ğĭĭĻƭƭ ƒĻƷŷƚķƭ͵
/ŷƚƚƭźƓŭ ğ ŅźƌĻ ƚƩŭğƓźǩğƷźƚƓ źƭ ğ ķĻƭźŭƓ ķĻĭźƭźƚƓͲ ŷĻƓĭĻ źƷ ƒǒƭƷ ĬĻ ķƚƓĻ ŷğǝźƓŭ źƓ ƒźƓķ ƷŷĻ ğĭŷźĻǝĻƒĻƓƷ
ƚŅ ŭƚƚķ ƦĻƩŅƚƩƒğƓĭĻ ǞźƷŷ ƩĻƭƦĻĭƷ Ʒƚ ƷŷĻ ƒƚƭƷ ƌźƉĻƌǤ ǒƭğŭĻ ƚŅ ƷŷĻ ŅźƌĻ͵
ŷĻ ĭƩźƷĻƩźğ ǒƭǒğƌƌǤ ĭƚƓƭźķĻƩĻķ źƒƦƚƩƷğƓƷ ğƩĻʹ Њ͵ CğƭƷ ğĭĭĻƭƭ Ʒƚ ƭźƓŭƌĻ ƩĻĭƚƩķ ƚƩ ĭƚƌƌĻĭƷźƚƓ ƚŅ ƩĻƌğƷĻķ ƩĻĭƚƩķƭ͵
Ћ͵ 9ğƭǤ ƩĻĭƚƩķ ğķķźƓŭΉǒƦķğƷĻΉƩĻƒƚǝğƌͲ ǞźƷŷƚǒƷ ķźƭƩǒƦƷźƓŭ
Ќ͵ {ƷƚƩğŭĻ ĻŅŅźĭźĻƓĭǤ͵Ѝ͵ wĻķǒƓķğƓĭǤ ğƭ ğ ǞğƩƩğƓƷǤ ğŭğźƓƭƷ ķğƷğ ĭƚƩƩǒƦƷźƚƓ͵
ƚ ƩĻğķ ğ ƭƦĻĭźŅźĭ ƩĻĭƚƩķ ŅƩƚƒ ğƓ źƓķĻǣĻķ ƭĻƨǒĻƓƷźğƌ ŅźƌĻͲ Ǥƚǒ Ǟƚǒƌķ źƓĭƌǒķĻ ƷŷĻ Y9ў ƦğƩğƒĻƷĻƩ źƓ ƷŷĻ
w9!5 ΛƚƩ ğƭƭƚĭźğƷĻķ źƓƦǒƷΜ ƭƷğƷĻƒĻƓƷ͵
ŷĻ δƉĻǤδ źƓ Ʒŷźƭ ĭğƭĻ Ǟƚǒƌķ ĬĻ ğ ƭƦĻĭźŅźĭ ƩĻĭƚƩķ ƓǒƒĬĻƩ ΛĻ͵ŭ͵Ͳ ƷŷĻ ƓǒƒĬĻƩ ЌЎ Ǟƚǒƌķ ƩĻƦƩĻƭĻƓƷ ƷŷĻ ЌЎƷŷ
ƩĻĭƚƩķ źƓ ƷŷĻ ŅźƌĻΜ͵ŷĻ ķźƩĻĭƷ ğĭĭĻƭƭ Ʒƚ ğ ƩĻĭƚƩķ ƒƚǝĻƭ ƷŷĻ ƩĻĭƚƩķ ƦƚźƓƷĻƩͲ ƭƚ ƷŷğƷ ƭǒĬƭĻƨǒĻƓƷ ƭĻƨǒĻƓƷźğƌ ğĭĭĻƭƭ Ǟƚǒƌķ ƷğƉĻ
ƦƌğĭĻ ŅƩƚƒ ƷŷĻ ƓĻǞ ƩĻĭƚƩķ ƦƚźƓƷĻƩ ƌƚĭğƷźƚƓͲ ƩğƷŷĻƩ ƷŷğƓ ƷŷĻ ĬĻŭźƓƓźƓŭ ƚŅ ƷŷĻ ŅźƌĻ͵
bƚǞ ƨǒĻƭƷźƚƓ ğƩźƭĻƭ ŷƚǞ Ʒƚ ğĭĭĻƭ ƷŷĻƭĻ ŅźƌĻƭ͵ Ļ ƓĻĻķ Y9{ Ʒƚ ğĭĻƭƭ ƷŷĻ ŅźƌĻ͵
t9{ hC Y9{ʹ
twLa!w Y9{ʹ ŷĻ ƦƩźƒğƩǤ ƉĻǤ ƚŅ ğ ƩĻƌğƷźƚƓğƌ ƷğĬƌĻ ǒƓźƨǒĻƌǤ źķĻƓƷźŅźĻƭ Ļğĭŷ ƩĻĭƚƩķ źƓ ƷŷĻ ƷğĬƌĻ͵
LƷ ĭğƓ ĻźƷŷĻƩ ĬĻ ğ ƓƚƩƒğƌ ğƷƷƩźĬǒƷĻ ƷŷğƷ źƭ ŭǒğƩğƓƷĻĻķ Ʒƚ ĬĻ ǒƓźƨǒĻ Λƭǒĭŷ ğƭ {ƚĭźğƌ {ĻĭǒƩźƷǤ bǒƒĬĻƩ źƓ ğ
ƷğĬƌĻ ǞźƷŷ Ɠƚ ƒƚƩĻ ƷŷğƓ ƚƓĻ ƩĻĭƚƩķ ƦĻƩ ƦĻƩƭƚƓΜ ƚƩ źƷ ĭğƓ ĬĻ ŭĻƓĻƩğƷĻķ ĬǤ ƷŷĻ 5.a{ Λƭǒĭŷ ğƭ ğ ŭƌƚĬğƌƌǤ
ǒƓźƨǒĻ źķĻƓƷźŅźĻƩͲ ƚƩ D...L5Ͳ źƓ aźĭƩƚƭƚŅƷ {v[ {ĻƩǝĻƩΜ͵
tƩźƒğƩǤ ƉĻǤƭ ƒğǤ ĭƚƓƭźƭƷ ƚŅ ğ ƭźƓŭƌĻ ğƷƷƩźĬǒƷĻ ƚƩ ƒǒƌƷźƦƌĻ ğƷƷƩźĬǒƷĻƭ źƓ ĭƚƒĬźƓğƷźƚƓ͵
9ǣğƒƦƌĻƭʹ LƒğŭźƓĻ ǞĻ ŷğǝĻ ğ {...59b{ ƷğĬƌĻ ƷŷğƷ ĭƚƓƷğźƓƭ ğ ƩĻĭƚƩķ ŅƚƩ Ļğĭŷ ƭƷǒķĻƓƷ ğƷ ğ ǒƓźǝĻƩƭźƷǤ͵
ŷĻ ƭƷǒķĻƓƷγƭ ǒƓźƨǒĻ ƭƷǒķĻƓƷ L5 ƓǒƒĬĻƩ Ǟƚǒƌķ ĬĻ ğ ŭƚƚķ ĭŷƚźĭĻ ŅƚƩ ğ ƦƩźƒğƩǤ ƉĻǤ źƓ ƷŷĻ {...59b{
ƷğĬƌĻ͵
ŷĻ ƭƷǒķĻƓƷγƭ ŅźƩƭƷ ğƓķ ƌğƭƷ ƓğƒĻ Ǟƚǒƌķ ƓƚƷ ĬĻ ğ ŭƚƚķ ĭŷƚźĭĻͲ ğƭ ƷŷĻƩĻ źƭ ğƌǞğǤƭ ƷŷĻ ĭŷğƓĭĻ ƷŷğƷ ƒƚƩĻ
ƷŷğƓ ƚƓĻ ƭƷǒķĻƓƷ ƒźŭŷƷ ŷğǝĻ ƷŷĻ ƭğƒĻ ƓğƒĻ͵
![9wb!9 Y9ʹ ŷĻ ƉĻǤƭ ƚƷŷĻƩ ƷŷğƓ ƷŷĻ ƦƩźƒğƩǤ ƉĻǤƭ ğƩĻ ƉƓƚǞƓ ğƭ ğƌƷĻƩƓğƷĻ ƉĻǤ͵
/!b5L5!9 Y9ʹ ŷĻ /ğƓķźķğƷĻ YĻǤƭ ğƩĻ ƭǒƦĻƩ ƉĻǤƭ ŅƚƩ Ǟŷźĭŷ Ɠƚ ƦƩƚƦĻƩ ƭǒĬƭĻƷ źƭ ğ ƭǒƦĻƩ ƉĻǤ͵ LƓ ƚƷŷĻƩ
ǞƚƩķƭ ĭğƓķźķğƷĻ ƉĻǤƭ ğƩĻ ƒźƓźƒğƌ ƭǒƦĻƩ ƉĻǤƭ͵
{...t9w Y9ʹ {ǒƦĻƩ ƉĻǤ ƭƷğƓķƭ ŅƚƩ ƭǒƦĻƩƭĻƷ ƚŅ ğ ƉĻǤ͵ ! {ǒƦĻƩ YĻǤ źƭ ğ ƭĻƷ ƚŅ ƚƓĻ ƚƩ ƒƚƩĻ ğƷƷƩźĬǒƷĻƭ ƷŷğƷ
ğƩĻ ƷğƉĻƓ ĭƚƌƌĻĭƷźǝĻƌǤ ğƓķ ĭğƓ źķĻƓƷźŅǤ ğƌƌ ƚƷŷĻƩ ğƷƷƩźĬǒƷĻƭ ǒƓźƨǒĻƌǤ͵
{9/hb5!w Y9ʹ !ƓǤ ŅźĻƌķ źƓ ğ ƩĻĭƚƩķ ƒğǤ ĬĻ ğ ƭĻĭƚƓķğƩǤ ƉĻǤ͵
ŷĻ ƦƩƚĬƌĻƒ ǞźƷŷ ƭĻĭƚƓķğƩǤ ƉĻǤƭ źƭ ƷŷğƷ ƷŷĻǤ ğƩĻ ƓƚƷ ǒƓźƨǒĻ ğƓķ ğƩĻ ƷŷĻƩĻŅƚƩĻ ƌźƉĻƌǤ Ʒƚ ƩĻƷǒƩƓ ƒƚƩĻ
ƷŷğƓ ƚƓĻ ƩĻĭƚƩķ ŅƚƩ ğ ƦğƩƷźĭǒƌğƩ ǝğƌǒĻ ƚŅ ƷŷĻ ƉĻǤ͵
{ƚƒĻ ŅźĻƌķƭ ŷğǝĻ ğ ƌğƩŭĻ ĻƓƚǒŭŷ ƩğƓŭĻ ƚŅ ǝğƌǒĻƭ ƷŷğƷ ğ ƭĻğƩĭŷ ŅƚƩ ğ ƭƦĻĭźŅźĭ ǝğƌǒĻ Ǟźƌƌ ƦƩƚķǒĭĻ ƚƓƌǤ ğ ŅĻǞ
ƩĻĭƚƩķƭͳ ƚƷŷĻƩ ŅźĻƌķƭ ŷğǝĻ ğ ǝĻƩǤ ƌźƒźƷĻķ ƩğƓŭĻ ƚŅ ǝğƌǒĻƭ ğƓķ ğ ƭĻğƩĭŷ ŅƚƩ ğ ƭƦĻĭźŅźĭ ǝğƌǒĻ Ǟźƌƌ ƩĻƷǒƩƓ ğ
ƌğƩŭĻ ƦƩƚƦƚƩƷźƚƓ ƚŅ ƷŷĻ ŅźƌĻ͵
!Ɠ ĻǣğƒƦƌĻ ƚŅ ƷŷĻ ƌğƷƷĻƩ Ǟƚǒƌķ Ǟƚǒƌķ ĬĻ ğ ƭĻğƩĭŷ źƓ ƭƷǒķĻƓƷ ƩĻĭƚƩķƭ ŅƚƩ ƭƷǒķĻƓƷƭ ĭƌğƭƭźŅźĻķ ğƭ ŅƩĻƭŷƒĻƓ͵
Chw9LDb Y9 ʹ CƚƩĻźŭƓ YĻǤ ΛwĻŅĻƩĻƓƷźğƌ źƓƷĻŭƩźƷǤΜ źƭ ğ ƦƩƚƦĻƩƷǤ ƚŅ ķğƷğ ǞŷźĭŷͲ ǞŷĻƓ ƭğƷźƭŅźĻķͲ ƩĻƨǒźƩĻƭ
ĻǝĻƩǤ ǝğƌǒĻ ƚŅ ƚƓĻ ğƷƷƩźĬǒƷĻ ƚŅ ğ ƩĻƌğƷźƚƓ Ʒƚ ĻǣźƭƷ ğƭ ğ ǝğƌǒĻ ƚŅ ğƓƚƷŷĻƩ ğƷƷƩźĬǒƷĻ źƓ ğ ķźŅŅĻƩĻƓƷ ƩĻƌğƷźƚƓ͵
CƚƩ ƩĻŅĻƩĻƓƷźğƌ źƓƷĻŭƩźƷǤ Ʒƚ ŷƚƌķ źƓ ğ ƩĻƌğƷźƚƓğƌ ķğƷğĬğƭĻͲ ğƓǤ ŅźĻƌķ źƓ ğ ƷğĬƌĻ ƷŷğƷ źƭ ķĻĭƌğƩĻķ ğ ŅƚƩĻźŭƓ ƉĻǤ
ĭğƓ ĭƚƓƷğźƓ ĻźƷŷĻƩ ğ Ɠǒƌƌ ǝğƌǒĻͲ ƚƩ ƚƓƌǤ ǝğƌǒĻƭ ŅƩƚƒ ğ ƦğƩĻƓƷ ƷğĬƌĻγƭ ƦƩźƒğƩǤ ƉĻǤ ƚƩ ğ ĭğƓķźķğƷĻ ƉĻǤ͵
LƓ ƚƷŷĻƩ ǞƚƩķƭͲ ǞŷĻƓ ğ ŅƚƩĻźŭƓ ƉĻǤ ǝğƌǒĻ źƭ ǒƭĻķ źƷ ƒǒƭƷ ƩĻŅĻƩĻƓĭĻ ğ ǝğƌźķͲ ĻǣźƭƷźƓŭ ƦƩźƒğƩǤ ƉĻǤ źƓ ƷŷĻ
ƦğƩĻƓƷ ƷğĬƌĻ͵CƚƩ źƓƭƷğƓĭĻͲ ķĻƌĻƷźƓŭ ğ ƩĻĭƚƩķ ƷŷğƷ ĭƚƓƷğźƓƭ ğ ǝğƌǒĻ ƩĻŅĻƩƩĻķ Ʒƚ ĬǤ ğ ŅƚƩĻźŭƓ ƉĻǤ źƓ ğƓƚƷŷĻƩ ƷğĬƌĻ Ǟƚǒƌķ
ĬƩĻğƉ ƩĻŅĻƩĻƓƷźğƌ źƓƷĻŭƩźƷǤ͵
{ƚƒĻ ƩĻƌğƷźƚƓğƌ ķğƷğĬğƭĻ ƒğƓğŭĻƒĻƓƷ ƭǤƭƷĻƒƭ ĭğƓ ĻƓŅƚƩĭĻ ƩĻŅĻƩĻƓƷźğƌ źƓƷĻŭƩźƷǤͲ ƓƚƩƒğƌƌǤ ĻźƷŷĻƩ ĬǤ
ķĻƌĻƷźƓŭ ƷŷĻ ŅƚƩĻźŭƓ ƉĻǤ ƩƚǞƭ ğƭ ǞĻƌƌ Ʒƚ ƒğźƓƷğźƓ źƓƷĻŭƩźƷǤͲ ƚƩ ĬǤ ƩĻƷǒƩƓźƓŭ ğƓ ĻƩƩƚƩ ğƓķ ƓƚƷ ƦĻƩŅƚƩƒźƓŭ
ƷŷĻ ķĻƌĻƷĻ͵
ŷźĭŷ ƒĻƷŷƚķ źƭ ǒƭĻķ ƒğǤ ĬĻ ķĻƷĻƩƒźƓĻķ ĬǤ ğ ƩĻŅĻƩĻƓƷźğƌ źƓƷĻŭƩźƷǤ ĭƚƓƭƷƩğźƓƷ ķĻŅźƓĻķ źƓ ğ ķğƷğ
ķźĭƷźƚƓğƩǤ͵ δwĻŅĻƩĻƓƷźğƌδ ƷŷĻ ğķƆĻĭƷźǝĻ ķĻƭĭƩźĬĻƭ ƷŷĻ ğĭƷźƚƓ ƷŷğƷ ğ ŅƚƩĻźŭƓ ƉĻǤ ƦĻƩŅƚƩƒƭͲ γƩĻŅĻƩƩźƓŭγ Ʒƚ ğ
ƌźƓƉ ŅźĻƌķ źƓ ğƓƚƷŷĻƩ ƷğĬƌĻ͵
LƓ ƭźƒƦƌĻ ƷĻƩƒƭͲ γƩĻŅĻƩĻƓƷźğƌ źƓƷĻŭƩźƷǤγ źƭ ğ ŭǒğƩğƓƷĻĻ ƷŷğƷ ƷŷĻ ƷğƩŭĻƷ źƷ γƩĻŅĻƩƭγ Ʒƚ Ǟźƌƌ ĬĻ ŅƚǒƓķ͵
! ƌğĭƉ ƚŅ ƩĻŅĻƩĻƓƷźğƌ źƓƷĻŭƩźƷǤ źƓ ğ ķğƷğĬğƭĻ ĭğƓ ƌĻğķ ƩĻƌğƷźƚƓğƌ ķğƷğĬğƭĻƭ Ʒƚ ƩĻƷǒƩƓ źƓĭƚƒƦƌĻƷĻ ķğƷğͲ
ǒƭǒğƌƌǤ ǞźƷŷ Ɠƚ źƓķźĭğƷźƚƓ ƚŅ ğƓ ĻƩƩƚƩ͵
! ĭƚƒƒƚƓ ƦƩƚĬƌĻƒ ƚĭĭǒƩƭ ǞźƷŷ ƩĻƌğƷźƚƓğƌ ķğƷğĬğƭĻ ƷğĬƌĻƭ ƌźƓƉĻķ ǞźƷŷ ğƓ γźƓƓĻƩ ƆƚźƓγ Ǟŷźĭŷ ƩĻƨǒźƩĻƭ ƓƚƓΏ
b...[[ ǝğƌǒĻƭ źƓ ĬƚƷŷ ƷğĬƌĻƭͲ ğ ƩĻƨǒźƩĻƒĻƓƷ ƷŷğƷ ĭğƓ ƚƓƌǤ ĬĻ ƒĻƷ ƷŷƩƚǒŭŷ ĭğƩĻŅǒƌ ķĻƭźŭƓ ğƓķ ƩĻŅĻƩĻƓƷźğƌ
źƓƷĻŭƩźƷǤ͵
9bL Lb9DwLʹ
LƓ ƷŷĻ ƩĻƌğƷźƚƓğƌ ķğƷğ ƒƚķĻƌͲ ĻƓƷźƷǤ źƓƷĻŭƩźƷǤ źƭ ƚƓĻ ƚŅ ƷŷĻ ƷŷƩĻĻ źƓŷĻƩĻƓƷ źƓƷĻŭƩźƷǤ ƩǒƌĻƭ͵
9ƓƷźƷǤ źƓƷĻŭƩźƷǤ źƭ ğƓ źƓƷĻŭƩźƷǤ ƩǒƌĻ Ǟŷźĭŷ ƭƷğƷĻƭ ƷŷğƷ ĻǝĻƩǤ ƷğĬƌĻ ƒǒƭƷ ŷğǝĻ ğ ƦƩźƒğƩǤ ƉĻǤ ğƓķ ƷŷğƷ ƷŷĻ
ĭƚƌǒƒƓ ƚƩ ĭƚƌǒƒƓƭ ĭŷƚƭĻƓ Ʒƚ ĬĻ ƷŷĻ ƦƩźƒğƩǤ ƉĻǤ ƭŷƚǒƌķ ĬĻ ǒƓźƨǒĻ ğƓķ ƓƚƷ b...[[͵
źƷŷźƓ ƩĻƌğƷźƚƓğƌ ķğƷğĬğƭĻƭ ǒƭźƓŭ {v[Ͳ ĻƓƷźƷǤ źƓƷĻŭƩźƷǤ źƭ ĻƓŅƚƩĭĻķ ĬǤ ğķķźƓŭ ğ ƦƩźƒğƩǤ ƉĻǤ ĭƌğǒƭĻ Ʒƚ ğ
ƭĭŷĻƒğ ķĻŅźƓźƷźƚƓ͵ŷĻ ƭǤƭƷĻƒ ĻƓŅƚƩĭĻƭ 9ƓƷźƷǤ LƓƷĻŭƩźƷǤ ĬǤ ƓƚƷ ğƌƌƚǞźƓŭ ƚƦĻƩğƷźƚƓ ΛLb{9wͲ ...t5!9Μ Ʒƚ ƦƩƚķǒĭĻ ğƓ źƓǝğƌźķ
ƦƩźƒğƩǤ ƉĻǤ͵
!ƓǤ ƚƦĻƩğƷźƚƓ ƷŷğƷ źƭ ƌźƉĻƌǤ Ʒƚ ĭƩĻğƷĻ ğ ķǒƦƌźĭğƷĻ ƦƩźƒğƩǤ ƉĻǤ ƚƩ ƚƓĻ ĭƚƓƷğźƓźƓŭ Ɠǒƌƌƭ źƭ ƩĻƆĻĭƷĻķ͵
ŷĻ 9ƓƷźƷǤ LƓƷĻŭƩźƷǤ ĻƓƭǒƩĻƭ ƷŷğƷ ƷŷĻ ķğƷğ ƷŷğƷ Ǥƚǒ ƭƷƚƩĻ ƩĻƒğźƓƭ źƓ ƷŷĻ ƦƩƚƦĻƩ ŅƚƩƒğƷ ğƭ ǞĻƌƌ ğƭ
ĭƚƒƦƩĻŷĻƓƭźĬƌĻ͵ {...