Transcript
GATE 2015
Praneeth A S (UG201110023)
B.Tech(Computer Science & Engineering)
Indian Institute of Technology Jodhpur
Jodhpur, Rajasthan 342011, India
August 4, 2014
Dedicated to my beloved parents who have stood beside me entire my career.
Acknowledgements
Many Sources have been used.
Preface
To be used for GATE Preparation.
Contents
I
Algorithms
1
1 Test
2
2 Complexity Analysis(Asymptotic Notations)
2.1 Θ Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Big O Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Ω Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3
3
3
3 Solving Recurrences
3.1 Substitution Method . .
3.1.1 Example . . . . .
3.2 Recurrence Tree Method
3.3 Master Method . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
4
4
5
4 Sorting
4.1 Insertion Sort 3
4.2 Bubble Sort 4 .
4.3 Bucket Sort 9 .
4.4 Heap Sort 8 . .
4.5 Quick Sort 6 . .
4.6 Merge Sort 5 . .
4.7 Summary . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6
6
6
6
6
6
6
6
5 Searching
5.1 Linear Search . . . . . .
5.2 Binary Search . . . . . .
5.3 Interpolation Search [1]
5.4 Summary . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
7
7
7
7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
6 Divide & Conquer
8
7 Greedy Algorithms
9
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.3 Activity Selection Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
8 Dynamic Programming
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 Fibonacci Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.3 Ugly Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
iv
11
11
11
11
Contents
Contents
9 NP Classes
12
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
9.2 Problem Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
II
Data Structures
14
10 Hashing
15
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
10.2 ReHashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
III
Theory Of Computation
18
11 Finite Automaton
20
12 Undecidability
21
12.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
13 Turing Machines
22
13.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
14 Regular Sets
24
14.1 Pumping Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
IV
Computer Organization [3]
25
15 Machine Instructions & Addressing
15.1 Definitions . . . . . . . . . . . . . .
15.2 Design Principles . . . . . . . . . .
15.3 Machine Instructions [3, p.67,90] .
Modes
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
16 Pipelining
16.1 Designing Instruction sets for pipelining
16.2 Pipeline Hazards . . . . . . . . . . . . .
16.2.1 Structural Hazards . . . . . . . .
16.2.2 Data Hazards . . . . . . . . . . .
16.2.3 Hazards . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26
26
27
28
29
29
30
30
30
30
17 Arithmetic for Computers
31
17.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
18 Speedup
32
V
33
First Order Logic
19 Propositional Logic
19.1 Introduction . . . .
19.2 Truth Table . . . .
19.3 Rules . . . . . . . .
19.4 Conditional Proof .
19.5 Indirect Proof . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
v
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
34
34
35
37
37
38
Contents
Contents
20 Predicate Logic
39
20.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
VI
Probability
40
21 Definitions
42
21.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
22 Probability
22.1 Terms . . . . . . . . . . . . . . . . . . . . . .
22.2 Propositions . . . . . . . . . . . . . . . . . . .
22.3 Conditional Probability . . . . . . . . . . . .
22.3.1 Bayes Formula . . . . . . . . . . . . .
22.4 Mean, Median, Mode and Standard Deviation
22.5 Distributions . . . . . . . . . . . . . . . . . .
22.5.1 Bernoulli . . . . . . . . . . . . . . . .
22.5.2 HyperGeometric . . . . . . . . . . . .
22.5.3 Uniform . . . . . . . . . . . . . . . . .
22.5.4 Normal . . . . . . . . . . . . . . . . .
22.5.5 Exponential . . . . . . . . . . . . . . .
22.5.6 Poisson . . . . . . . . . . . . . . . . .
22.5.7 Binomial . . . . . . . . . . . . . . . .
22.5.8 Summary . . . . . . . . . . . . . . . .
VII
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
HTML
44
44
44
44
45
45
47
47
47
47
47
47
47
47
48
51
23 Basic Commands
52
23.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
23.2 Tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
23.3 Tags Reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
VIII
Numerical Analysis
56
24 Numerical solutions to non-algebraic
24.1 Bisection Method . . . . . . . . . . .
24.2 Newton-Raphson Method . . . . . .
24.3 Secant Method . . . . . . . . . . . .
linear
. . . .
. . . .
. . . .
equations
57
. . . . . . . . . . . . . . . . . . . . . 57
. . . . . . . . . . . . . . . . . . . . . 58
. . . . . . . . . . . . . . . . . . . . . 58
25 Numerical Integration
25.1 Introduction . . . . .
25.2 Trapezoidal Rule . .
25.3 Simpson’s 1/3 Rule .
25.4 Simpson’s 3/8 Rule .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
26 LU decomposition for system
26.1 Introduction . . . . . . . . .
26.2 Factorizing A as L and U .
26.2.1 Example . . . . . . .
26.3 Algorithm For solving . . .
.
.
.
.
.
.
.
.
of
. .
. .
. .
. .
.
.
.
.
.
.
.
.
.
.
.
.
linear
. . . .
. . . .
. . . .
. . . .
vi
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
59
59
59
60
60
equations
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
61
61
61
61
62
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Contents
IX
XML
27 Basic Information
27.1 Basics . . . . . . . .
27.2 Rules for XML Docs
27.3 XML Elements . . .
27.4 XML Attributes . .
X
Contents
63
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Computer Networks
64
64
65
65
66
67
28 Network Security
28.0.1 Substitution Ciphers . . . . .
28.1 Public Key Algorithms . . . . . . . .
28.1.1 Diffie-Hellman Key Exchange
28.1.2 RSA . . . . . . . . . . . . . .
28.1.3 Knapsack Algorithm . . . . .
28.1.4 El Gamal Algorithm . . . . .
28.2 Digital Signatures . . . . . . . . . .
28.2.1 Symmetric Key Signatures .
28.2.2 Public Key Signatures . . . .
28.2.3 Message Digests . . . . . . .
28.3 Communication Security . . . . . . .
28.3.1 Firewalls . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
68
68
68
68
68
69
69
69
69
69
70
72
72
29 Application Layer
29.1 DNS - Domain Name System . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29.1.1 Name Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29.2 HTTP - Hyper Text Transfer Protocol . . . . . . . . . . . . . . . . . . . . . . . .
74
74
75
75
30 Routing Algorithms
30.1 Introduction . . . . . . . . . . . . . . . . . .
30.2 Shortest Path Algorithm - Dijsktra . . . . .
30.3 Flooding . . . . . . . . . . . . . . . . . . . .
30.4 Distance Vector Routing - Bellman Ford . .
30.5 Link State Routing . . . . . . . . . . . . . .
30.5.1 Learning abput neighbours . . . . .
30.5.2 Setting Link Costs . . . . . . . . . .
30.5.3 Building Link State Packets . . . . .
30.5.4 Distributing the Link State Packets
30.5.5 Computing Shortest Path . . . . . .
30.6 Hierarchial Routing . . . . . . . . . . . . . .
30.7 Broadcast Routing . . . . . . . . . . . . . .
30.8 Multicast Routing . . . . . . . . . . . . . .
30.9 IPv4 - Network Layer . . . . . . . . . . . .
30.9.1 Communication in Internet . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
77
77
78
79
79
80
80
81
81
81
82
82
83
84
84
84
31 Error & Flow control - Data Link
31.1 Introduction . . . . . . . . . . . .
31.1.1 Byte Count . . . . . . . .
31.1.2 Byte Stuffing . . . . . . .
31.1.3 Bit Stuffing . . . . . . . .
31.2 Error Correction & Detection . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
86
86
86
87
88
89
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Layer
. . . .
. . . .
. . . .
. . . .
. . . .
vii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Contents
Contents
31.2.1 Error Correcting Codes . . . . . . . . . .
31.2.2 Error Detecting Codes . . . . . . . . . . .
31.3 Data Link Protocols . . . . . . . . . . . . . . . .
31.3.1 Simplex Protocol . . . . . . . . . . . . . .
31.3.2 Stop & Wait Protocol for Error free . . .
31.3.3 Stop & Wait Protocol for Noisy Channel .
31.3.4 Sliding Window Protocols . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
89
91
93
93
93
94
94
32 Data Link Layer Switching
98
32.1 Bridges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
32.1.1 Learning Bridges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
32.1.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
33 Transport Layer
101
33.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
34 Internet Protocol - IP
102
34.1 IPv4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
35 Network Layer
103
35.1 Subnetting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
35.2 Classless Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
36 Physical Layer
106
36.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
XI
Calculus
107
37 Continuity
108
38 Differentiation
109
39 Integration
110
40 Definite Integrals & Improper Integrals
112
XII
113
Linear Algebra
41 Determinants
41.1 Introduction . . . . . . . . .
41.2 Properties . . . . . . . . . .
41.3 Determinants & Eigenvalues
41.4 Eigenvectors & Eigenvalues
41.5 Cramer’s rule . . . . . . . .
41.6 Rank of a Matrix . . . . . .
41.7 System of Linear Equations
XIII
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Set Theory & Algebra
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
114
114
114
115
115
117
117
117
119
42 Sets
120
viii
Contents
Contents
43 Relations
121
43.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
43.2 Other Properties Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
44 Functions
123
45 Group
124
46 Lattices
125
47 Partial Orders
126
XIV
Combinatory
127
48 Generating Functions
128
49 Recurrence Relations
129
XV
C Programs for Algorithms I [6]
130
50 Sorting
131
51 Spanning Trees
149
52 Dynamic Programming
154
XVI
169
C Programs for Testing
Index
174
ix
List of Algorithms
1
2
3
Calculate y = xn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Calculate the shortest path from source node to all destination nodes . . . . . . . 78
Calculate the shortest path from source node to all destination nodes . . . . . . . 79
x
List of Figures
3.1
Master Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13.1 Turing machine accepting 0n 1n for n ≥ 1
5
. . . . . . . . . . . . . . . . . . . . . . 23
28.1 Digital Signatures using public key . . . . . . . . . . . . . . . . . . . . . . . . . . 69
28.2 SHA-1 algorithm from Alice to Bob . . . . . . . . . . . . . . . . . . . . . . . . . 70
28.3 Firewall Protecting internal network . . . . . . . . . . . . . . . . . . . . . . . . . 72
29.1
29.2
29.3
29.4
30.1
30.2
30.3
30.4
30.5
30.6
A portion of the Internet domain name space . . . . . . . . . . . . . . . . . . .
Domain Name Space mapped to zones . . . . . . . . . . . . . . . . . . . . . . .
DNS Resource Records Types . . . . . . . . . . . . . . . . . . . . . . . . . . . .
HTTP 1.1 with (a) multiple connections and sequential requests. (b)A persistent
connection and sequential requests. (c) A persistent connection and pipelined
requests. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 74
. 74
. 75
Sample run of Dijsktra’s Algorithm . . .
Sample run of Bellman Ford’s Algorithm
Link Sate Packets . . . . . . . . . . . . .
Packet Buffer for Router B . . . . . . .
Hierarchial Routing . . . . . . . . . . . .
IPv4 Header . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
31.1 Byte Count (a) Without errors. (b) With one error. . . . . . . . . . . . . . . .
31.2 Byte Stuffing (a) A frame delimited by flag bytes. (b) Four examples of byte
sequences before and after byte stuffing. . . . . . . . . . . . . . . . . . . . . . .
31.3 Bit Stuffing (a) The original data. (b) The data as they appear on the line. (c)
The data as they are stored in the receiver’s memory after destuffing. . . . . .
31.4 Hamming Codes for (11, 7) for even parity . . . . . . . . . . . . . . . . . . . . .
31.5 Convolution Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31.6 Interleaving parity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31.7 Calculating CRC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31.8 A sliding window of size 1, with a 3-bit sequence number. (a) Initially. (b) After
the first frame has been sent. (c) After the first frame has been received. (d)
After the first acknowledgement has been received. . . . . . . . . . . . . . . . .
31.9 (a) Normal case. (b) Abnormal case. The notation is (seq, ack, packet number).
An asterisk indicates where a network layer accepts a packet. . . . . . . . . . .
31.10Pipelining and error recovery. Effect of an error when (a) receiver’s window size
is 1(Go Back n) and (b) receiver’s window size is large(Selective Repeat). . . .
31.11(a) Initial situation with a window of size 7. (b) After 7 frames have been sent
and received but not acknowledged. (c) Initial situation with a window size of
4. (d) After 4 frames have been sent and received but not acknowledged. . . . .
xi
. 76
78
80
81
82
83
85
. 87
. 88
.
.
.
.
.
89
90
91
92
93
. 94
. 95
. 96
. 97
List of Figures
List of Figures
32.1 a) Bridge connecting two multidrop LANs. (b) Bridges (and a hub) connecting
seven point-to-point stations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
32.2 Bridges with two parallel links. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
32.3 (a) Which device is in which layer. (b) Frames, packets, and headers. . . . . . . . 100
33.1 The primitives of Transport Layer. . . . . . . . . . . . . . . . . . . . . . . . . . . 101
33.2 The primitives of TCP socket. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
34.1 IPv4 Header . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
xii
List of Tables
4.1
Summary of Sorting Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
5.1
Summary of Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
10.1 Empty Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.2 Empty Table for Quadratic Probing . . . . . . . . . . . . . . . . . . . . . . . . . 16
10.3 Empty Table for Double Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
22.1 Probability Formula Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
22.2 Probability Formula Table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
xiii
List of listings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Binary Search in C (Recursive) . . . . . . . . . . . . . . . . .
Binary Search in C (Iterative) . . . . . . . . . . . . . . . . . .
Insertion Sort in C . . . . . . . . . . . . . . . . . . . . . . . .
Bubble Sort in C . . . . . . . . . . . . . . . . . . . . . . . . .
Merge Sort in C . . . . . . . . . . . . . . . . . . . . . . . . . .
Quick Sort in C . . . . . . . . . . . . . . . . . . . . . . . . . .
Quick Sort in C (Iterative) . . . . . . . . . . . . . . . . . . . .
Heap Sort in C . . . . . . . . . . . . . . . . . . . . . . . . . .
Bucket Sort in C++ . . . . . . . . . . . . . . . . . . . . . . .
Kruskal MST in C . . . . . . . . . . . . . . . . . . . . . . . .
Fibonacci Numbers in C . . . . . . . . . . . . . . . . . . . . .
Fibonacci Numbers in C(Memoization) . . . . . . . . . . . . .
Fibonacci Numbers in C(Tabulation) . . . . . . . . . . . . . .
Ugly Numbers Numbers in C . . . . . . . . . . . . . . . . . .
Ugly Numbers in C(Dynamic Programming) . . . . . . . . . .
Longest Increasing Subsequence in C . . . . . . . . . . . . . .
Longest Increasing Subsequence in C(Dynamic Programming)
Longest Common Subsequence in C . . . . . . . . . . . . . .
Longest Common Subsequence in C(Dynamic Programming)
Edit Distance in C . . . . . . . . . . . . . . . . . . . . . . . .
xiv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
132
133
135
136
139
141
143
147
148
153
154
155
156
158
160
162
163
164
165
168
Todo list
Is the size of register = word size always? Interesting Point:The word size of an
Architecture is often (but not always!) defined by the Size of the General Purpose
Registers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Check for theorem’s name . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Check for Newton’s forward difference polynomial formula . . . . . . . . . . . . . . . . .
Check the formula for Error of Simpson’s 3/8 rule . . . . . . . . . . . . . . . . . . . . .
Use a 32-bit sequence number. With one link state packet per second, it would take 137
2no. of bits
. Here BW = 1lsp/sec. no. of bits = 32 .
years to wrap around. Time =
BW
did not understand . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Suppose 111110 is in data, does receiver destuff that leading to wrong information (in Bit
Stuffing)? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
How to calculate and detect errors in checksum? . . . . . . . . . . . . . . . . . . . . . .
How are error detected in CRC? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Please understand seletive repeat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Check about net mask . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Learn about DHCP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Check this part for m, n comaprison condition for no, infintely many solutions. Also for
m = n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xv
.
.
.
.
26
58
59
60
. 82
. 83
.
.
.
.
.
.
88
92
92
96
103
104
. 118
Part I
Algorithms
1
Chapter 1
Test
Algorithm 1 Calculate y = xn
Input: n ≥ 0 ∨ x 6= 0
Output: y = xn
1. y ← 1
2. if n < 0 then
3.
X ← x1
4.
N ← −n
5. else
6.
X←x
7.
N ←n
8. end if
9. while N 6= 0 do
10.
if N is even then
11.
X ←X ×X
12.
N ← N/2
13.
else
14.
y ←y×X
15.
N ←N −1
16.
end if
17. end while
// N is odd
// end of while
2
Chapter 2
Complexity Analysis(Asymptotic
Notations)
2.1
Θ Notation
Θ((g(n)) = f(n): ∃ positive constants c1 ,c2 and n0 such that
0 ≤ c1 g(n) ≤ f (n) ≤ c2 g(n)
2.2
∀n ≥ n0
(2.1)
Big O Notation
O((g(n)) = f(n): ∃ positive constants c0 and n0 such that
0 ≤ f (n) ≤ c0 g(n)
2.3
∀n ≥ n0
(2.2)
Ω Notation
Ω((g(n)) = f(n): ∃ positive constants c0 and n0 such that
0 ≤ c0 g(n) ≤ f (n)
3
∀n ≥ n0
(2.3)
Chapter 3
Solving Recurrences
3.1
Substitution Method
Definition 1 - Substitution Method.
We make a guess for the solution and then we use mathematical induction to
prove the the
n
guess is correct or incorrect. For example consider the recurrence T (n) = 2T
+ n.
2
3.1.1
Example
We guess the solution as T (n) = O(n log n). Now we use induction to prove our guess. We
need to prove that T (n) ≤ cn log n. We can assume that it is true for values smaller than n.
n
T (n) = 2T
+n
n
n 2
log
+n
≤c
2
2
= cn log n − cn log 2 + n
= cn log n − cn + n
≤ cn log n
3.2
Recurrence Tree Method
Read it from here Recurrence Tree Method
4
Chapter 3. Solving Recurrences
3.3
3.3. Master Method
Master Method
Figure 3.1: Master Theorem
T (n) = aT
n
b
+ f (n)
where a ≥ 1 and b > 1
3 cases:
1. If f(n) = Θ (nc ) where c < logb a then T (n) = Θ nlogb a
2. If f(n) = Θ (nc ) where c = logb a then T (n) = Θ (nc log n)
3. If f(n) = Θ (nc ) where c > logb a then T (n) = Θ (f (n))
5
Chapter 4
Sorting
4.1
Insertion Sort 3
4.2
Bubble Sort 4
4.3
Bucket Sort 9
4.4
Heap Sort 8
4.5
Quick Sort 6
4.6
Merge Sort 5
4.7
Summary
Sorting
Method
Insertion Sort
Bucket Sort
Bubble Sort
Heap Sort
Quick Sort
Merge Sort
Usage
Time Complexity
Best Average Worst
Space
Complexity
No. of
swaps
Stability
X
X
×
×
X
Table 4.1: Summary of Sorting Methods
Auxiliary Space is the extra space or temporary space used by an algorithm.
Space Complexity of an algorithm is total space taken by the algorithm with respect to the
input size. Space complexity includes both Auxiliary space and space used by input.
Stability: If two objects with equal keys appear in the same order in sorted output as they
appear in the input unsorted array.
6
Chapter 5
Searching
5.1
Linear Search
5.2
Binary Search
5.3
Interpolation Search [1]
5.4
This is a margin note
using the geometry
package, set at 0cm
vertical offset to the
first line it is typeset.
Summary
Method
Time Complexity
Table 5.1: Summary of Search Methods
7
Chapter 6
Divide & Conquer
8
Chapter 7
Greedy Algorithms
7.1
Introduction
Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing
the next piece that offers the most obvious and immediate benefit. Greedy algorithms are used
for optimization problems. An optimization problem can be solved using Greedy if the problem
has the following property: At every step, we can make a choice that looks best at the moment,
and we get the optimal solution of the complete problem.
Examples: Kruskal MST, Prim MST, Dijsktra Shortest Path, Huffman Coding, Activity Selection Problem etc.,
1. Kruskal’s Minimum Spanning Tree (MST): In Kruskal’s algorithm, we create a
MST by picking edges one by one. The Greedy Choice is to pick the smallest weight edge
that doesn’t cause a cycle in the MST constructed so far.
2. Prim’s Minimum Spanning Tree: In Prim’s algorithm also, we create a MST by
picking edges one by one. We maintain two sets: set of the vertices already included
in MST and the set of the vertices not yet included. The Greedy Choice is to pick the
smallest weight edge that connects the two sets.
3. Dijkstra’s Shortest Path: The Dijkstra’s algorithm is very similar to Prim’s algorithm.
The shortest path tree is built up, edge by edge. We maintain two sets: set of the vertices
already included in the tree and the set of the vertices not yet included. The Greedy
Choice is to pick the edge that connects the two sets and is on the smallest weight path
from source to the set that contains not yet included vertices.
4. Huffman Coding: Huffman Coding is a loss-less compression technique. It assigns
variable length bit codes to different characters. The Greedy Choice is to assign least bit
length code to the most frequent character.
7.2
Spanning Trees
MST
Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is
a tree and connects all the vertices together. A single graph can have many different spanning
trees. A minimum spanning tree (MST) or minimum weight spanning tree for a weighted,
connected and undirected graph is a spanning tree with weight less than or equal to the weight
of every other spanning tree. The weight of a spanning tree is the sum of weights given to each
9
Chapter 7. Greedy Algorithms
7.3. Activity Selection Problem
edge of the spanning tree.
A minimum spanning tree has (V − 1) edges where V is the number of vertices in the given
graph.
Kruskal’s MST Algorithm
7.3
Activity Selection Problem
Definition 2 - Activity Selection Problem.
You are given n activities with their start and finish times. Select the maximum number
of activities that can be performed by a single person, assuming that a person can only work
on a single activity at a time.
10
Chapter 8
Dynamic Programming
8.1
Introduction
Dynamic Programming is an algorithmic paradigm that solves a given complex problem
by breaking it into subproblems and stores the results of subproblems to avoid computing the
same results again. Following are the two main properties of a problem that suggest that the
given problem can be solved using Dynamic programming.
Example: Floyd Warshall Algorithm, Bellman Ford Algorithm
1. Overlapping Subproblems: Dynamic Programming is mainly used when solutions of
same subproblems are needed again and again. In dynamic programming, computed
solutions to subproblems are stored in a table so that these donâĂŹt have to recomputed.
Uses: Fibonacci Numbers
2. Optimal Substructure: A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its
subproblems.
For example the shortest path problem has following optimal substructure property: If
a node x lies in the shortest path from a source node u to destination node v then the
shortest path from u to v is combination of shortest path from u to x and shortest path
from x to v.
Uses: Longest Increasing Subsequence, Shortest Path.
Two Approaches:
1. Memoization (Top Down)
2. Tabulation (Bottom Up)
8.2
Fibonacci Numbers
8.3
Ugly Numbers
Definition 3 - Ugly Numbers.
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, . . .
shows the first 11 ugly numbers. By convention, 1 is included.
See 15 for Dynamic Programming version of problem.
11
Chapter 9
NP Classes
9.1
Introduction
Definition 4 - P.
A decision problem that can be solved in polynomial time. That is, given an instance of
the problem, the answer yes or no can be decided in polynomial time.
Definition 5 - NP.
NP - Non-Deterministic Polynomial Time. A decision problem where instances of the problem
for which the answer is yes have proofs that can be verified in polynomial time. This means that
if someone gives us an instance of the problem and a certificate (sometimes called a witness)
to the answer being yes, we can check that it is correct in polynomial time.
A non-deterministically solvable problem by a turing machine(non-deterministic turing machine) in polynomial time.
Definition 6 - NP Complete.
A decision problem L is NP-complete if it is in the set of NP problems and also in the
set of NP-hard problems. NP-complete is a subset of NP, the set of all decision problems
whose solutions can be verified in polynomial time; NP may be equivalently defined as the set
of decision problems that can be solved in polynomial time on a non-deterministic Turing machine. A problem p in NP is also NP-complete if every other problem in NP can be transformed
into p in polynomial time.
A decision problem C is NP-complete if:
1. C is in NP, and
2. Every problem in NP is reducible to C in polynomial time.
Consequence: If we had a polynomial time algorithm (on a UTM, or any other Turingequivalent abstract machine) for C, we could solve all problems in NP in polynomial time. ie.,
P = NP = NP-Complete
Examples:Boolean satisfiability problem (Sat.), Knapsack problem, Hamiltonian path problem, Travelling salesman problem, Subgraph isomorphism problem, Subset sum problem, Clique
problem, Vertex cover problem, Independent set problem, Dominating set problem, Graph coloring problem etc.,
Definition 7 - NP Hard.
The precise definition here is that a problem X is NP-hard if there is an NP-complete problem
Y such that Y is reducible to X in polynomial time. But since any NP-complete problem can
12
Chapter 9. NP Classes
9.2. Problem Definitions
be reduced to any other NP-complete problem in polynomial time, all NP-complete problems
can be reduced to any NP-hard problem in polynomial time. Then if there is a solution to
one NP-hard problem in polynomial time, there is a solution to all NP problems in polynomial
time.
If a problem is NP-hard, this means I can reduce any problem in NP to that problem. This
means if I can solve that problem, I can easily solve any problem in NP. If we could solve an
NP-hard problem in polynomial time, this would prove P = NP.
Examples: The halting problem is the classic NP-hard problem. This is the problem that
given a program P and input I, will it halt?
Definition 8 - Polynomial Reducible.
Can arbitrary instances of problem Y be solved using a polynomial number of standard computational steps, plus a polynomial number of calls to a black box that solves problem X?
Suppose Y ≤P X. If X can be solved in polynomial time, then Y can be solved in polynomial
time. X is at least as hard as Y (with respect to polynomial time). Y is polynomial-time
reducible to X. Suppose Y ≤P X. If Y cannot be solved in polynomial time, then X cannot be
solved in polynomial time.
9.2
Problem Definitions
Definition 9 - Circuit SAT.
Definition 10.
13
Part II
Data Structures
14
Chapter 10
Hashing
10.1
Introduction
• Prime number to be used for hashing should be very large to avoid collisions.
• Two keys hash to the same value (this is known as a collision).
• This hash function involves all
characters in the key and can generally be expected to
PKeySize-1
distribute well (it computes i=0
Key(KeySize - i - 1) ×37i and brings the result
into proper range). The code computes a polynomial function (of 37) by use of Horner’s
rule. For instance, another way of computing hk = k0 + 37 × k1 + 372 k2 is by the formula
hk = ((k2 ) × 7 + k1 ) × 37 + k0 . HornerâĂŹs rule extends this to an nth degree polynomial.
/**
* A hash routine for string objects.
*/
unsigned int hash( const string & key, int tableSize ){
unsigned int hashVal = 0;
for( char ch : key )
hashVal = 37 * hashVal + ch;
return hashVal % tableSize;
}
• The first strategy, commonly known as separate chaining, is to keep a list of all elements
that hash to the same value. Might be preferable to avoid their use (since these lists are
doubly linked and waste space)
• We define the load factor, λ, of a hash table to be the ratio of the number of elements in
the hash table to the table size.
• The average length of a list is λ. The effort required to perform a search is the constant
time required to evaluate the hash function plus the time to traverse the list.
• In an unsuccessful search, the number of nodes to examine is λ on average.
• A successful search requires that about 1 + ( λ2 ) links be traversed.
• The general rule for separate chaining hashing is to make the table size about as large as
the number of elements expected (in other words, let λ ≈ 1). If the load factor exceeds
1, we expand the table size by calling rehash.
15
Chapter 10. Hashing
10.1. Introduction
Table 10.1: Empty Table
0
1
2
3
4
5
6
7
8
9
Table 10.2: Empty Table for Quadratic Probing
0
1
2
3
4
5
6
7
8
9
• Generally, the load factor should be below λ = 0.5 for a hash table that doesnâĂŹt use
separate chaining. We call such tables probing hash tables.
• Three common collision resolution strategies:
– Linear Probing
– Quadratic Probing
– Double Hashing
• Linear Probing
– In linear probing, f is a linear function of i, typically f(i) = i. This amounts to trying
cells sequentially (with wraparound) in search of an empty cell. Table 10.3 shows
the result of inserting keys 89, 18, 49, 58, 69 into a hash table using the same hash
function as before and the collision resolution strategy, f (i) = i.
–
0
1
0
49
0
49
2
1
3
2
1
58
4
3
2
69
5
4
3
6
5
4
7
6
5
8
7
6
9
89
8
18
7
0
9
89
8
18
1
0
49
2
3
4
5
6
7
1
58
2
3
4
5
6
8
18
7
9
89
8
9
18 89
9
89
– Primary clustering, means that any key that hashes into the cluster will require
several attempts to resolve the collision, and then it will add to the cluster.
• Quadratic Probing:
– f (i) = i2
– When 49 collides with 89, the next position attempted is one cell away. This cell is
empty, so 49 is placed there. Next, 58 collides at position 8. Then the cell one away
is tried, but another collision occurs. A vacant cell is found at the next cell tried,
which is 22 = 4 away. 58 is thus placed in cell 2.
–
0
0
49
0
49
1
2
3
1
2
1
2
58
4
3
5
4
3
69
6
5
4
7
6
5
8
7
6
9
89
8
18
7
8
18
–
16
0
9
89
9
89
1
0
49
2
1
3
4
5
6
7
2
58
3
4
5
6
8
18
7
9
89
8
9
18 89
Chapter 10. Hashing
10.2. ReHashing
Table 10.3: Empty Table for Double Hashing
0
1
2
3
4
5
6
7
8
9
Theorem 1.
If quadratic probing is used, and the table size is prime, then a new element can
always be inserted if the table is at least half empty.
• Double Hashing
– For double hash- ing, one popular choice is f(i) = i.hash2 (x).
– hash2 (x) must be never evaluated to 0.
– hash2 (x) = R - (x mod R), with R = 7, a prime smaller than TableSize
– The first collision occurs when 49 is inserted. hash2 (49) = 7 - 0 = 7, so 49 is inserted
in position 6. hash2 (58) = 7 - 2 = 5, so 58 is inserted at location 3. Finally, 69
collides and is inserted at a distance hash2 (69) = 7 - 6 = 1 away. If we tried to insert
60 in position 0, we would have a collision. Since hash2 (60) = 7 - 4 = 3, we would
then try positions 3, 6, 9, and then 2 until an empty spot is found.
–
0
1
2
3
4
5
6
0
1
2
3
4
5
6
49
0
69
1
2
3
58
4
5
7
6
49
8
7
9
89
8
18
7
8
18
0
9
89
1
0
2
1
3
2
4
3
58
5
4
6
5
7
6
49
8
18
7
9
89
8
9
18 89
9
89
– If the table size is not prime, it is possible to run out of alternative locations prematurely.
10.2
ReHashing
• As an example, suppose the elements 13, 15, 24, and 6 are inserted into a linear probing
0 1 2 3 4 5 6
hash table of size 7. The hash function is h(x) = x mod 7.
6 15
24
13
• If 23 is inserted into the table, the resulting table will be over 70 percent full. Because
the table is so full, a new table is created. The size of this table is 17, because this is the
first prime that is twice as large as the old table size. The new hash function is then h(x)
= x mod 17. The old table is scanned, and elements 6, 15, 23, 24, and 13 are inserted
into the new table. The resulting table:
0 1 2 3 4 5 6 7
8 9 10 11 12 13 14 15 16
6 23 24
13
15
17
Part III
Theory Of Computation
18
References [2], Wikipedia articles for definitions of Halting Problem, Recursive Sets etc.,
19
Chapter 11
Finite Automaton
Definition 11 - DFA,NFA, − N F A.
M = (Q, Σ, δ, q0 , F )
Q : Set of states. In − N F A is also a state.
Σ : Set of alphabets
δ : Moving function
q0 : Initial State
F : Set of Final States. In NFA 2Q is the total no. of possible final states.
In − N F A δ(q0 , 01) = − CLOSU RE(δ()δ(q0 , 0), 1)).
Theorem 2.
If L is accepted by an NFA, there exists an equivalent DFA accepting by L.
Definition 12 - -closure.
-closure denote the set of all vertices p such that there is a path from q to p labelled .
Definition 13.
If L is accepted by an NFA with transitions, then L is accepted by an NFA without transitions.
Definition 14.
i
+
∞
i
L∗ = ∪∞
i=0 L . L = ∪i=1 L
Theorem 3.
Let r be a regular expression. Then there exists an NFA with -transitions that accepts L(r).
Definition 15 - Regular Language.
If L is accepted by DFA, then L is denoted by a regular expression.
k−1
k−1 ∗ k−1
k−1
k
Rij
= Rik
(Rik
) Rkj ∪ Rij
0
Rij = {a|δ(qi , a) = qj }if i 6= j
{a|δ(qi , a) = qj } ∪ {}if i = j
k
Rij
is the set of all strings that take the finite automaton from state qi to state qj without
going through any state numbered higher than k.
20
Chapter 12
Undecidability
12.1
Definitions
Definition 16 - Undecidable Problems.
An undecidable problem is a decision problem for which it is known to be impossible to
construct a single algorithm that always leads to a correct yes-or-no answer.
Definition 17 - Halting Problem.
Given the description of an arbitrary program and a finite input, decide whether the program
finishes running or will run forever. (Undecidable)
Definition 18 - Recursive Sets.
A set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a
given number belongs to the set.
Definition 19 - Recursively Enumerable Sets.
A set S of natural numbers is called recursively enumerable, computably enumerable,
semidecidable, provable or Turing-recognizable if: there is an algorithm such that the set of
input numbers for which the algorithm halts is exactly S.
Example: Set of languages we can accept using a Turing machine.
NOTE: There is no algorithm that decides the mebership of a particular string in a language.
21
Chapter 13
Turing Machines
13.1
Notation
M = (Q, Σ, Γ, δ, q0 , B, F )
1. Q: The finite set of states of the finite control.
2. Σ: The finite set of input symbols.
3. Γ: The complete set of tape symbols; Σ is always a subset of Γ.
4. δ: The transition function. The arguments of δ(q, X) are a state q and a tape symbol
X. The value of δ(q, X), if it is defined, is a triple (p, Y, D ), where:
(a) p is the next state, in Q.
(b) Y is the symbol, in Γ , written in the cell being scanned, replacing whatever symbol
was there.
(c) D is a direction, either Lor R, standing for "left" or "right" respectively, and telling
us the direction in which the head moves.
5. q0 : The start state, a member of Q, in which the finite control is found initially.
6. B: The blank symbol. This symbol is in Γ but not in E; i.e., it is not an input symbol.
T he blank appears initially in all but the finite number of initial cells that hold input
symbols.
7. F: The set of final or accepting states, a subset of Q.
Use the string X1 X2 . . . Xi−1 qXi Xi+1 . . . Xn to represent an ID in which
1. q is the state of the Turing machine.
2. The tape head is scanning the ith symbol from the left.
3. X1 X2 . . . Xn the portion of the tape between the leftmost and the rightmost nonblank.
As an exception, if the head is to the left of the leftmost nonblank or to the right of the
rightmost nonblank, t hen some prefix or suffix of X1 X2 . . . Xn will be blank, and i will
be 1 or n, respectively.
22
Chapter 13. Turing Machines
13.1. Notation
A move M is defined as X1 X2 . . . Xi−1 qXi Xi+1 . . . Xn `M X1 X2 . . . Xi−2 pXi−1 Xi Xi+1 . . . Xn
Figure 13.1: Turing machine accepting 0n 1n for n ≥ 1
23
Chapter 14
Regular Sets
14.1
Pumping Lemma
Pumping Lemma is used to test whether a language is regular or not based on the property
that languages obatined from regular languages are regular. If a language is regular, it is
accepted by a DFA M = (Q, Σ, δ, q0 , F ) with some particular number of states, say n.
Lemma 3.1 - Pumping Lemma.
Let L be a regular set. Then there is a constant n such that if z is any word in L, and
|z| > n, we may write z = uvw in such a way that |uv| ≤ n, |v| ≥ 1, and for all i > 0, uv i w is
in L. Furthermore, n is no greater than the number of states of the smallest FA accepting L.
Examples:
2
1. 0i isnotaregularlanguage.
2. L be the set of strings of 0’s and 1’s, beginning with a 1, whose value treated as a binary
number is a prime. is not a regular language.
Theorem 4.
The regular sets are closed under union (L1 ∪ L2 ), concatenation (L1 .L2 ), and Kleene closure
(L∗ ).
Theorem 5.
The class of regular sets is closed under complementation. That is, if L is a regular set and
L ∈ Σ∗ , then σ ∗ − L is a regular set.
Theorem 6.
The regular sets are closed under intersection.
24
Part IV
Computer Organization [3]
25
Chapter 15
Machine Instructions & Addressing
Modes
15.1
Definitions
Definition 20 - Instruction Set.
Instruction set The vocabulary of commands understood by a given architecture.
Definition 21 - Stored Program Concept.
Stored-program concept The idea that instructions and data of many types can be stored
in memory as numbers, leading to the stored program computer.
Definition 22 - Word.
Word The natural unit of access in a computer, usually a group of 32 bits; corresponds to
the size of a register in the MIPS architecture.
Definition 23 - Registers.
Registers are limited number of special locations built directly in hardware. The size of a
register in the MIPS architecture is 32 bits.
Definition 24 - Data transfer Instructions.
Data transfer instruction A command that moves data between memory and registers.
Definition 25 - Address.
Address A value used to delineate the location of a specific data element within a memory
array. To access a word in memory, the instruction must supply the memory address.
Memory is just a large, single-dimensional array, with the address acting as the index to
that array, starting at 0.
Definition 26 - Base Register.
Definition 27 - Offset.
Definition 28 - Alignment Restriction.
Words must start at addresses that are multiples of 4(for MIPS). This requirement is called an
alignment restriction.
26
Is the size of register = word size
always? Interesting Point:The word
size of an Architecture is often (but
not always!) defined
by the Size of the
General Purpose
Registers.
Chapter 15. Machine Instructions & Addressing Modes 15.2. Design Principles
Definition 29 - Little & Big Endian.
Computers divide into those that use the address of the leftmost or “big end”byte as the
word address versus those that use the rightmost or “little end”byte.
Definition 30 - Instruction Format.
Instruction format A form of representation of an instruction composed of fields of binary
numbers. Example: add $t0, $s1, $s2 t0 = 8(reg. no.) s0 = 16(reg.no)
0
17
18
8
0
32
000000 10001 10010 01000 00000 100000
6 bits
5 bits 5 bits 5 bits 5 bits
6 bits
op
rs
rt
rd
shamt funct
1. op Basic operation of the instruction, traditionally called the opcode.
2. rs The first register source operand.
3. rt The second register source operand.
4. rd The register destination operand. It gets the result of the operation.
5. shamt Shift amount. (Section 2.5 explains shift instructions and this term; it will not be
used until then, and hence the field contains zero.)
6. funct Function. This field selects the specific variant of the operation in the op field and
is sometimes called the function code.
Definition 31 - Opcode.
An opcode (operation code) is the portion of a machine language instruction that specifies
the operation to be performed.
Definition 32 - Program Counter.
Program counter (PC) The register containing the address of the instruction in the program being executed.
Definition 33 - Addressing Modes.
Addressing mode One of several addressing regimes delimited by their varied use of operands
and/or addresses.
15.2
Design Principles
1. Simplicity favors regularity.
2. Samller is faster A very large number of registers may increase the clock cycle time
simply because it takes electronic signals longer when they must travel farther.
3. Make common case fast Constant operands occur frequently, and by including constants inside arithmetic instructions, they are much faster than if constants were loaded
from memory.
4. Good design demands good compromises. Different kinds of instruction formats for
different kinds of instructions.
27
Chapter 15. Machine Instructions & Addressing
15.3. Machine
Modes Instructions [3, p.67,90]
15.3
Machine Instructions [3, p.67,90]
1. Load lw: copies data from memory to a register. Format: lw register, mem loc. of
data(num,reg. where base add. is stored) item Store sw: copies data from register to
memory. Format: sw register, mem loc. of data(num,reg. where base add. is stored)
2. Add add:
3. Add Immediate addi:
4. Subtract sub:
lw $t0,8($s3) # Temporary reg $t0 gets A[8]
28
Chapter 16
Pipelining
Definition 34 - Pipelining.
Pipelining is an implementation technique in which multiple instructions are overlapped in
execution.
Pipelining doesn’t decrease the time to finish a work but increases the throughput in a given
time. MIPS instrructions takes 5 steps:
1. Fetch instruction from memory.
2. Read registers while decoding the instruction. The format of MIPS instructions allows
reading and decoding to occur simultaneously.
3. Execute the operation or calculate an address.
4. Access an operand in data memory.
5. Write the result into a register.
Time between instructionsnonpipelined
Number of pipe stages
Speedup due to pipelining ≈ No. of pipe stages. 5 stage piplelined process is 5 times faster.
(Only for perfectly balanced processes).
But process involve overhead. So speedup will be quite less.
Time between instructionspipelined =
16.1
Designing Instruction sets for pipelining
1. All MIPS instructions are the same length. This restriction makes it much easier to fetch
instructions in the first pipeline stage and to decode them in the second stage.
2. MIPS has only a few instruction formats, with the source register fields being located in
the same place in each instruction. This symmetry means that the second stage can begin
reading the register file at the same time that the hardware is determining what type of
instruction was fetched.
3. Memory operands only appear in loads or stores in MIPS. This restriction means we can
use the execute stage to calculate the memory address and then access memory in the
following stage.
4. Operands must be aligned in memory. Hence, we need not worry about a single data
transfer instruction requiring two data memory accesses; the requested data can be transferred between processor and memory in a single pipeline stage.
29
Chapter 16. Pipelining
16.2
Pipeline Hazards
16.2.1
Structural Hazards
16.2. Pipeline Hazards
It means that the hardware cannot support the combination of instructions that we want to
execute in the same clock cycle.
16.2.2
Data Hazards
Data hazards occur when the pipeline must be stalled because one step must wait for another
to complete. For example, suppose we have an add instruction followed immediately by a
subtract instruction that uses the sum ($s0):
add \$s0, \$t0, \$t1
sub \$t2, \$s0, \$t3
Without intervention, a data hazard could severely stall the pipeline.
Solution
Forwarding also called bypassing. A method of resolving a data hazard by retrieving the
missing data element from internal buffers rather than waiting for it to arrive from programmervisible registers or memory.
Load-use data hazard A specific form of data hazard in which the data requested by a
load instruction has not yet become available when it is requested. Pipeline stall Also called
bubble. A stall initiated in order to resolve a hazard.
For example If first instruction were load instead of add then $s0 would not be available until
4th stage resulting in a pipeline stall.
16.2.3
Hazards
30
Chapter 17
Arithmetic for Computers
17.1
Definitions
Definition 35 - LSB & MSB.
LSB : right-most bit .MSB : left-most bit.
31
Chapter 18
Speedup
Definition 36 - Amdahl’s Law.
content...
32
Part V
First Order Logic
33
Chapter 19
Propositional Logic
19.1
Introduction
• Simple Statement: A simple statement is one that does not contain any other statement
as a component.
Ex., Fast foods tend to be unhealthy.
• Compound Statement: A compound statement is one that contains at least one simple
statement as a component.
Ex., Dianne Reeves sings jazz, and Christina Aguilera sings pop.
•
Operator
∼
∧
∨
→
↔
Name
tilde
dot
wedge
horseshoe
triple bar
Logical function
negation
conjunction
disjunction
implication
equivalence
34
Used to translate
not, it is not the case that
and, also, moreover
or, unless
if . . . then . . . , only if
if and only if
Chapter 19. Propositional Logic
Symbol
∼
19.2. Truth Table
Words
doesnot
not the case
false that
and
∧
•
1
→
but
however
if . . .,then . . . (S → P)
. . . if . . . (P → S)
. . . only if . . . (S → P)
. . . provided that . . . (P → S)
. . . provided that . . . (P → S)
. . . provided that . . . (S → P)
Either . . . or
∨
Unless
↔
. . . if and only if . . . (S → P)
. . . sufficient and necessary
condition that . . . (S → P)
Usage
Rolex does not make computers.
It is not the case that Rolex makes computers.
It is false that Rolex makes computers.
Tiff any sells jewelry, and Gucci sells cologne.
Tiff any and Ben Bridge sell jewelry.
Tiff any sells jewelry, but Gucci sells cologne.
Tiff any sells jewelry; however, Gucci sells cologne.
If Purdue raises tuition, then so does Notre Dame.
Notre Dame raises tuition if Purdue does.
Purdue raises tuition only if Notre Dame does.
Cornell cuts enrollment provided that Brown does.
Cornell cuts enrollment on condition that Brown does.
BrownâĂŹs cutting enrollment implies that Cornell does.
Aspen allows snowboards or Telluride does.
Either Aspen allows snowboards or Telluride does.
Aspen allows snowboards unless Telluride does.
Unless Aspen allows snowboards, Telluride does.
JFK tightens security if and only if OâĂŹHare does.
JFKâĂŹs tightening security is a suffi cient and necessary condition for OâĂŹHareâĂŹs doing so.
• The → symbol is also used to translate statements phrased in terms of sufficient conditions
and necessary conditions. Event A is said to be a sufficient condition for event B whenever
the occurrence of A is all that is required for the occurrence of B. On the other hand, event
A is said to be a necessary condition for event B whenever B cannot occur without the
occurrence of A. For example, having the flu is a sufficient condition for feeling miserable,
whereas having air to breathe is a necessary condition for survival. Other things besides
having the flu might cause a person to feel miserable, but that by itself is suffi cient; other
things besides having air to breathe are required for survival, but without air survival is
impossible. In other words, air is necessary.
• To translate statements involving sufficient and necessary conditions into symbolic form,
place the statement that names the sufficient condition in the antecedent of the conditional
and the statement that names the necessary condition in the consequent.
1. HiltonâĂŹs opening a new hotel is a sufficient condition for MarriottâĂŹs doing so.
H→M
2. HiltonâĂŹs opening a new hotel is a necessary condition for MarriottâĂŹs doing so.
M→H
Not either A or B.
Either not A or not B.
Not both A and B.
Both not A and not B.
•
19.2
Truth Table
p
• NEGATION 0
1
1S
∼(A ∨ B)
∼A ∨ ∼B
∼(A ∧ B)
∼A ∧ ∼B
p
0
• AND 0
1
1
∼p
1
0
- First Part, P - Second Part
35
q
0
1
0
1
p∧q
0
0
0
1
Chapter 19. Propositional Logic
p
0
• OR 0
1
1
p
0
• IF 0
1
1
q
0
1
0
1
q
0
1
0
1
19.2. Truth Table
p∨q
0
1
1
1
Column
under Statement classifimain operator
cation
all true tautologous (logically true)
• all false
self-contradictory
(logically false)
at least one true, at contingent
least one false
p→q
1
1
0
1
p
0
• IF AND ONLY IF 0
1
1
• If all Premises are true and conclusion is
false, then argument is invalid.
• Assume argument invalid (true premises,
false conclusion)
q
0
1
0
1
p↔q
1
0
0
1
1. Contradiction → Argument is valid
2. No Contradiction → Argument is as
assumed (i.e., invalid)
• Assume statements consistent (assume
all of them true)
• To find truth value of long propositions
(B∧C)→(E→A)
(T∧T)→(F→T)
T
→
T
1. Contradiction → Statements is consistent
2. No Contradiction → Statements is
as assumed (i.e., inconsistent)
T
36
Chapter 19. Propositional Logic
19.3
19.3. Rules
Rules
Rules of Implication
Name
Premises1
Premises2
Modus Ponens(MP)
p→q
p
Modus Tollens(MT)
p→q
∼q
Hypothetical Syllogism(HS)
p→q
q→r
Disjunctive Syllogism(DS)
p∨q
∼p
Constructive Dilemma(CD) (p → q) ∧ (r → s)
p∨r
Destructive Dilemma(DD)
(p → q) ∧ (r → s) ∼ q ∨ ∼ s
Conjunction
p
q
Addition
p
Simplification
p∧q
Rules of Replacement
∼(p ∧ q)
(∼p ∨ ∼q)
De-Morgan’s Rule
∼(p ∨ q)
(∼p ∧ ∼q)
(p ∨ q)
(q ∨ p)
Commutative
(p ∧ q)
(q ∧ p)
p ∨ (q ∨ r)
(p ∨ q) ∨ r
Associative
p ∧ (q ∧ r)
(p ∧ q) ∧ r
p ∧ (q ∨ r)
(p ∧ q) ∨ (p ∧ r)
Distributive
p ∨ (q ∧ r)
(p ∨ q) ∧ (p ∨ r)
Double-Negation
p
∼∼p
Transposition
p→q
∼ q →∼ p
Exportation
(p ∧ q) → r
p → (q → r)
Material Implication
p→q
∼p∧q
p∧p
Tautology
p
p∨p
(p → q) ∧ (q → p)
Material Equivalence
p↔q
(p ∧ q) ∨ (∼ p ∧ ∼ q)
19.4
Conclusion
q
∼p
p→r
q
q∨s
∼p∨∼r
p∧q
p∨q
p
Conditional Proof
Conditional proof is a method for deriving a conditional statement (either the conclusion or
some intermediate line) that off ers the usual advantage of being both shorter and simpler to
use than the direct method.
Let us suppose, for a moment, that we do have A. We could then derive B ∧ C from the
first premise via modus ponens. Simplifying this expression we could derive B, and from this
we could get B ∨ D via addition. E would then follow from the second premise via modus
ponens. In other words, if we assume that we have A, we can get E. But this is exactly what
the conclusion says. Thus, we have just proved that the conclusion follows from the premises.
1. A → (B ∧ C)
2.(B ∨ D) → E / A → E
3. A
ACP
4. B ∧ C 1,3 MP
5. B
4 Simp
6. B ∨ D 5 Add
7. E
2,6 MP
8. A → E 3-7 CP
37
Chapter 19. Propositional Logic
19.5
19.5. Indirect Proof
Indirect Proof
It consists of assuming the negation of the statement to be obtained, using this assumption to
derive a contradiction, and then concluding that the original assumption is false. Th is last
step, of course, establishes the truth of the statement to be obtained. Th e following proof
sequence uses indirect proof to derive the conclusion:
1. (A ∨ B) → (C ∧ D)
2. C → ∼D / ∼A
3. A
AIP
4. A ∨ B
3 Add
5. C ∧ D
1,4 MP
6. C
5 Simp
7. ∼D
2,6 MP
8. D ∧ C
5 Com
9. D
8 Simp
10. D ∧ ∼D 7,9 Conj
11. ∼A 3-10 IP
38
Chapter 20
Predicate Logic
20.1
Introduction
39
Part VI
Probability
40
Syllabus: Conditional Probability; Mean, Median, Mode and Standard Deviation; Random Variables; Distributions; uniform, normal, exponential, Poisson, Binomial.
41
Chapter 21
Definitions
21.1
Definitions
1. Probability Density Function
Z
Pr[a ≤ X ≤ b] =
b
fX (x) dx
a
.
2. Cumulative Distributive Function
Z
x
FX (x) =
fX (u) du
−∞
fX (x) =
.
d
FX (x)
dx
FX (x) = P(X ≤ x)
P(a < X ≤ b) = FX (b) − FX (a)
3. Chebysev’s Inequality
1
k2
where X be a random variable with finite expected value µ and finite non-zero variance
σ2 . k > 0
Pr(|X − µ| ≥ kσ) ≤
4. Let x
¯ and s be the sample mean and sample standard deviation of the data set consisting
of the data x1 , . . . , xn where s > 0. Let
Sk = i, 1 ≤ i ≤ n : |xi − x
¯| < ks
and let N (Sk ) be the number of elements in the set Sk . Then, for any k ≥ 1,
N (Sk )
n−1
1
≥1−
≥1− 2
2
n
nk
k
5. One sided Chebysev’s Inequality. For k > 0
N (k)
1
≤
n
1 + k2
42
Chapter 21. Definitions
21.1. Definitions
6. Weak Law of Large Numbers
Xn =
1
(X1 + · · · + Xn )
n
converges to the expected value
for
Xn → µ
n→∞
where X1 , X2 , . . . is an infinite sequence of independent and identically distributed random
variables.
7. Markov’s Equality If X is a random variable that takes only nonnegative values, then
for any value a > 0
E[X]
P (x ≥ a) ≤
a
8. Chebysev’s Inequality If X is a random variable with mean µ and variance σ 2 , then
for any value k > 0
σ2
P (|X − µ|) ≤ 2
k
1
P (|X − µ| ≥ kσ) ≤ 2
k
9. Baye’s Theorem Assume come an event E to happen with A as well as B.
P (E) =
=
P (E ∩ A) + P (E ∩ B)
E
E
P (A)P
+ P (B)P
A
B
Given that E has already happened:
A
P
=
E
=
P (A ∩ E)
P (E)
E
P (A)P
A
E
E
P (A)P
+ P (B)P
A
B
43
(21.1)
(21.2)
(21.3)
(21.4)
Chapter 22
Probability
22.1
Terms
• Independent Events: Since P (E|F ) =
P (E ∩ F )
, we see that E is independent of F if
P (F )
P (E ∩ F ) = P (E)P (F )
• The three events E, F, and G are said to be independent if
P (E ∩ F ∩ G) = P (E)P (F )P (G)
P (E ∩ F ) = P (E)P (F )
P (E ∩ G) = P (E)P (G)
P (F ∩ G) = P (F )P (G)
22.2
Propositions
• If E and F are independent, then so are E and Fc .
• Mean : X = Distribution, P (Xi ) = Probability of Xi , Xi is the distribution
E [X] =
n
X
Xi P (Xi )
i=0
• Median :
• Mode :
• Standard Deviation :
22.3
Conditional Probability
• Conditional probability of E given that F has occurred, is denoted by P (E|F )
•
P (E|F ) =
P (E ∩ F )
.
P (F )
Defined only when P(F) > 0 and hence P(E|F) is defined only when P(F) > 0.
44
Chapter 22. Probability
22.4. Mean, Median, Mode and Standard Deviation
• Suppose that one rolls a pair of dice. The sample space S of this experiment can be taken
to be the following set of 36 outcomes
S = (i, j), i = 1, 2, 3, 4, 5, 6, j = 1, 2, 3, 4, 5, 6
where we say that the outcome is (i, j) if the first die lands on side i and the second on
side j.
Suppose further that we observe that the first die lands on side 3. Then, given this
information, what is the probability that the sum of the two dice equals 8?
Answer: Given that the initial die is a 3, there can be at most 6 possible outcomes of our
experiment, namely, (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), and (3, 6). In addition, because
each of these outcomes originally had the same probability of occurring, they should still
have equal probabilities. That is, given that the first die is a 3, then the (conditional)
probability of each of the outcomes (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (3, 6) is 16 , whereas
the (conditional) probability of the other 30 points in the sample space is 0. Hence, the
desired probability will be 16 .
22.3.1
Bayes Formula
• Let E and F be events. We may express E as
E = E ∩ F ∪ E ∩ Fc
for, in order for a point to be in E, it must either be in both E and F or be in E but not
in F.
• As E ∩ F & E ∩ F c are clearly mutually exclusive,
P (E)
(22.1)
= P (E ∩ F ) + P (E ∩ F c )
c
c
= P (E|F )P (F ) + P (E ∩ F )P (F )
c
= P (E|F )P (F ) + P (E ∩ F )[1 − P (F )]
22.4
Mean, Median, Mode and Standard Deviation
• Properties of Mean:
1. General Formula for continuous distributions:
Z ∞
E [X] =
xf (x)dx
−∞
2. General Formula for continuous distributions:
Z ∞
E [g(X)] =
g(x)f (x)dx
−∞
3. E [c] = c where c is a constant
4. Linearity: E [X] ≤ E [Y ]
5. General Linearity: E [aX + bY + c] = aE [X] + bE [Y ] + c
6.
E [X|Y = y] =
X
x
7. E [X] = E [E [X|Y ]]
45
x.P (X = x|Y = y)
(22.2)
(22.3)
Chapter 22. Probability
22.4. Mean, Median, Mode and Standard Deviation
8.
|E [X]| ≤ E [|X|]
9. Cov(X, Y) = E [XY ] − E [X] E [Y ]
10. if Cov(X, Y) = 0: X & Y are are said to be uncorrelated (independent variables are
a notable case of uncorrelated variables).
11. Variance = E X 2 − (E [X])2
• Properties of Median:
1. Value of m for discrete distributions:
1
2
1
P (X ≤ m) ≥
2
2. Value of m for continuous distributions:
Z
1
dF (x) ≥
2
(−∞,m]
Z
1
dF (x) ≥
2
(m,∞]
P (X ≥ m) ≥
where F (x) is the cumulative distriution function.
3. All three measures have the following property: If the random variable (or each value
from the sample) is subjected to the linear or affine transformation which replaces
X by aX+b, so are the mean, median and mode.
4. However, if there is an arbitrary monotonic transformation, only the median follows;
for example, if X is replaced by exp(X), the median changes from m to exp(m) but
the mean and mode won’t.
5. In continuous unimodal distributions the median lies, as a rule of thumb, between
the mean and the mode, about one third of the way going from mean to mode. In
a formula, median ≈ (2 × mean + mode)/3. This rule, due to Karl Pearson, often
applies to slightly non-symmetric distributions that resemble a normal distribution,
but it is not always true and in general the three statistics can appear in any order.
√
6. or unimodal distributions, the mode is within 3 standard deviations of the mean,
and the root mean square deviation about the mode is between the standard deviation and twice the standard deviation.
• Properties of Standard Deviation:
1. Represented by σ.
2.
σ
=
=
(22.4)
p
E [(X − µ)2 ]
p
E [X 2 ] − (E [X])2
(22.5)
3. σ 2 = Variance
4. Continuous Random Variable: The standard deviation of a continuous realvalued random variable X with probability density function p(x) is:
sZ
Z
(x − µ)2 p(x)dx,
σ=
X
where µ =
xp(x)dx
X
46
Chapter 22. Probability
22.5. Distributions
• Discrete Raqndom Variable: In the case where X takes random values from a finite
data set x1 , x2 , . . . , xN , let x1 have probability p1 , x2 have probability p2 , . . . , xN have
probability pN . In this case, the standard deviation will be
v
uN
N
uX
X
σ=t
pi (xi − µ)2 , where µ =
pi xi
i=1
22.5
22.5.1
i=1
Distributions
Bernoulli
• Suppose that a trial, or an experiment, whose outcome can be classified as either a
"success" or as a "failure" is performed. If we let X = 1 when the outcome is a success
and X = 0 when it is a failure, then the probability mass function of X is given by
(22.6)
1−p
P (X = 0)
=
P (X = 1)
= p
(22.7)
where p, 0 ≤ p ≤ 1, is the probability that the trial is a "success."
22.5.2
HyperGeometric
A bin contains N + M batteries, of which N are of acceptable quality and the other M are
defective. A sample of size n is to be randomly chosen (without replacements)
in the sense that
the set of sampled batteries is equally likely to be any of the N +M
subsets
of
size n. If we let
n
X denote the number of acceptable batteries in the sample, then
M
N
P (X = i) =
22.5.3
Uniform
f (x) =
22.5.4
0
Normal
−(x−µ)2
1
e 2σ2
2πσ
Exponential
f (x) =
22.5.6
if α ≤ x ≤ β
otherwise
1
β−α
f (x) = √
22.5.5
i
n−i
N +M
n
λe−λx
0
if x ≥ 0
if x < 0
Poisson
P (X = i) = e−λ
22.5.7
λi
i!
Binomial
n k
P (X = i) =
p (1 − p)n−k
k
47
i≤n
Chapter 22. Probability
22.5.8
22.5. Distributions
Summary
48
49
(B(n, p))
Binomial
Exponential
Normal
Poisson
Bernoulli
Notation
Name
Bernoulli
np
Mean
p
Mode
b(n + 1)pc
b(n + 1)p − 1c
Median
bnpc
dnpe
Table 22.1: Probability Formula Table
np(1 - p)
Variance
Chapter 22. Probability
22.5. Distributions
Bernoulli
Binomial
Exponential
Normal
Poisson
Name
Probability Generating
Function(PMF)
n
G(z) = [(1 − p) + pz]
Probability Generating
Function(PGF)
(1 − p + pet )n
Moment Generating
Function(MGF)
Table 22.2: Probability Formula Table
(1 − p + peit )n
Cumulative Distributive
Function(CDF)
Chapter 22. Probability
22.5. Distributions
50
Part VII
HTML
51
Chapter 23
Basic Commands
23.1
Basics
1. The DOCTYPE declaration defines the document type.
2. The text between and describes the web page.
3. The text between and is the visible page content.
4. The text between
and
is displayed as a heading.
5. The text between
and
is displayed as a paragraph.
6. HTML stands for Hyper Text Markup Language.
7. HTML is a markup language.
8. HTML tags are not case sensitive.
9. HTML elements with no content are called empty elements.
10. HTML elements can have attributes.
11. Attributes provide additional information about an element.
12. Attributes are always specified in the start tag.
13. Attributes come in name/value pairs like: name="value".
14. Attribute names and attribute values are case-insensitive(lower case recommended).
15.
tag creates a horizontal line in an HTML page.
23.2
Tags
1.
...
2.
3.
4.
![]()
5.
is an empty element without a closing tag
52
Chapter 23. Basic Commands
23.3
23.3. Tags Reference
Tags Reference
Tag
Basic
<body>
<h1> to <h6>
<p>
<br>
<hr>
<!–...–>
Formatting
<acronym>
<abbr>
<address>
<b>
<bdi>
<bdo>
<big>
<blockquote>
<center>
<cite>
<code>
<del>
<dfn>
<em>
<font>
<i>
<ins>
<kbd>
<mark>
<meter>
<pre>
<progress>
<q>
<rp>
<rt>
<ruby>
<s>
<samp>
<small>
Description
Defines the document type
Defines an HTML document
Defines a title for the document
Defines the document’s body
Defines HTML headings
Defines a paragraph
Inserts a single line break
Defines a thematic change in the content
Defines a comment
Not supported in HTML5. Use <abbr> instead. Defines an
acronym
Defines an abbreviation
Defines contact information for the author/owner of a document/article
Defines bold text
New Isolates a part of text that might be formatted in a different
direction from other text outside it
Overrides the current text direction
Not supported in HTML5. Use CSS instead. Defines big text
Defines a section that is quoted from another source
Not supported in HTML5. Use CSS instead. Defines centered
text
Defines the title of a work
Defines a piece of computer code
Defines text that has been deleted from a document
Defines a definition term
Defines emphasized text
Not supported in HTML5. Use CSS instead. Defines font,
color, and size for text
Defines a part of text in an alternate voice or mood
Defines a text that has been inserted into a document
Defines keyboard input
New Defines marked/highlighted text
New Defines a scalar measurement within a known range (a gauge)
Defines preformatted text
New Represents the progress of a task
Defines a short quotation
New Defines what to show in browsers that do not support ruby
annotations
New Defines an explanation/pronunciation of characters (for East
Asian typography)
New Defines a ruby annotation (for East Asian typography)
Defines text that is no longer correct
Defines sample output from a computer program
Defines smaller text
53
Chapter 23. Basic Commands
<strike>
<strong>
<sub>
<sup>
<time>
<tt>
<u>
<var>
<wbr>
Forms
<form>
<input>
<textarea>
<button>
<select>
<optgroup>
<option>
<label>
<fieldset>
<legend>
<datalist>
<keygen>
<output>
Frames
<frame>
<frameset>
<noframes>
<iframe>
Images
<img>
<map>
<area>
<canvas>
<figcaption>
<figure>
<audio>
<source>
<track>
<video>
<a>
<link>
<nav>
23.3. Tags Reference
Not supported in HTML5. Use <del> instead. Defines
strikethrough text
Defines important text
Defines subscripted text
Defines superscripted text
New Defines a date/time
Not supported in HTML5. Use CSS instead. Defines teletype
text
Defines text that should be stylistically different from normal text
Defines a variable
New Defines a possible line-break
Defines an HTML form for user input
Defines an input control
Defines a multiline input control (text area)
Defines a clickable button
Defines a drop-down list
Defines a group of related options in a drop-down list
Defines an option in a drop-down list
Defines a label for an <input> element
Groups related elements in a form
Defines a caption for a <fieldset> element
New Specifies a list of pre-defined options for input controls
New Defines a key-pair generator field (for forms)
New Defines the result of a calculation
Not supported in HTML5. Defines a window (a frame) in a
frameset
Not supported in HTML5. Defines a set of frames
Not supported in HTML5. Defines an alternate content for
users that do not support frames
Defines an inline frame
Defines an image
Defines a client-side image-map
Defines an area inside an image-map
New Used to draw graphics, on the fly, via scripting (usually
JavaScript)
New Defines a caption for a <figure> element
New Specifies self-contained content Audio/Video
New Defines sound content
New Defines multiple media resources for media elements
(<video> and <audio>)
New Defines text tracks for media elements (<video> and <audio>)
New Defines a video or movie Links
Defines a hyperlink
Defines the relationship between a document and an external resource (most used to link to style sheets)
New Defines navigation links Lists
54
Chapter 23. Basic Commands
<ul>
<ol>
<li>
<dir>
<dl>
<dt>
<dd>
<menu>
<command>
Tables
<table>
<caption>
<th>
<tr>
<td>
<thead>
<tbody>
<tfoot>
<col>
<colgroup>
Style/Sections
<style>
<div>
<span>
<header>
<footer>
<section>
<article>
<aside>
<details>
<dialog>
<summary>
Meta Info
<head>
<meta>
<base>
<basefont>
Programming
<script>
<noscript>
<applet>
<embed>
<object>
<param>
23.3. Tags Reference
Defines an unordered list
Defines an ordered list
Defines a list item
Not supported in HTML5. Use <ul> instead. Defines a
directory list
Defines a description list
Defines a term/name in a description list
Defines a description of a term/name in a description list
Defines a list/menu of commands
New Defines a command button that a user can invoke
Defines a table
Defines a table caption
Defines a header cell in a table
Defines a row in a table
Defines a cell in a table
Groups the header content in a table
Groups the body content in a table
Groups the footer content in a table
Specifies column properties for each column within a <colgroup>
element
Specifies a group of one or more columns in a table for formatting
Defines style information for a document
Defines a section in a document
Defines a section in a document
New Defines a header for a document or section
New Defines a footer for a document or section
New Defines a section in a document
New Defines an article
New Defines content aside from the page content
New Defines additional details that the user can view or hide
New Defines a dialog box or window
New Defines a visible heading for a <details> element
Defines information about the document
Defines metadata about an HTML document
Specifies the base URL/target for all relative URLs in a document
Not supported in HTML5. Use CSS instead. Specifies a
default color, size, and font for all text in a document
Defines a client-side script
Defines an alternate content for users that do not support clientside scripts
Not supported in HTML5. Use <object> instead. Defines an
embedded applet
New Defines a container for an external (non-HTML) application
Defines an embedded object
Defines a parameter for an object
55
Part VIII
Numerical Analysis
56
Chapter 24
Numerical solutions to
non-algebraic linear equations
24.1
Bisection Method
Theorem 7.
If a function f (x) is continuous between a and b, and f(a) and f(b) are of opposite signs,
then ∃ atleast one root between a and b.
1. Choose two real numbers a and b such that f (a) and f (b) < 0
2. Set xr =
(a+b)
2
3. (a) If f (a)f (xr ) < 0, the root lies in the interval (a, xr ). Then set b = xr and go to step
2 above.
(b) If f (a)f (xr ) > 0, the root lies in the interval (xr , b). Then set a = xr and go to step
2 above.
(c) If f (a)f (xr ) = 0, it means that xr is the root of the equation and the computation
can be terminated.
Important Points:
1. Percentage error r is defined as
0
x − x
r
r
r =
× 100%
x0r
(24.1)
0
where xr is the new computed value of xr
2. To find the number of iterations required for achieving particular accuracy is
loge |b−a|
n≥
loge 2
57
(24.2)
Chapter 24. Numerical solutions to non-algebraic24.2.
linearNewton-Raphson
equations
Method
24.2
Newton-Raphson Method
Let x0 be the approximate root of f (x) = 0. Let x1 = x0 + h be the correct root so that
f (x1 ) = 0. Expanding f (x0 + h) by taylor series we get,
0
f (x0 + h) = f (x0 ) + hf (x0 ) +
h2 00
f (x0 ) + . . . = 0
2!
Neglecting higher order terms we get
0
h=−
f (x0 ) + hf (x0 ) = 0
f (x0 )
f 0 (x0 )
xn+1 = xn −
x1 = x0 −
f (xn )
f 0 (xn )
f (x0 )
f 0 (x0 )
(24.3)
24.3 is called Newton Raphson Formula. This methods assumes that the function f (x) has
0
00
f (x) & f (x) existing. For f (x) having multiple roots method converges slowly.
00
1 2 f (ξ)
2 n f 0 (ξ)
n+1 ≈
(24.4)
where ξ is the exact value of the root of f (x).
24.3
Secant Method
Also called Modified Newton’s Method. In newton’s method it is not always possible that
0
f (x) exists. So we use Mean Value Theorem :
Theorem 8.
If a function f (x) is continuous on the closed interval [a, b], where a < b, and differentiable
on the open interval (a, b), then ∃ a point c in (a, b) such that
f (b) − f (a)
b−a
0
f (c) =
0
Using 8 we replace f (xi ) by
f (xi )−f (xi−1 )
xi −xi−1
xn+1 = xn −
and obtain the formula:
f (xn )(xn − xn−1 )
f (xn ) − f (xn−1 )
58
(24.5)
Check for theorem’s
name
Chapter 25
Numerical Integration
25.1
Introduction
Numerical Integration over [a, b] on f (x):
b
Z
I=
f (x)dx
(25.1)
a
For numerical integration f (x) in 25.1 is replaced by an interpolation polynomial φ(x) & obtains
on integration value of the definite integral. Here we use Newton’s forward difference polynomial
. Let the interval [a, b] be divided into n equal sub-intervals such that a = x0 < x1 < . . . <
xn = b. xn = x0 + nh.
Z
xn
I=
ydx
(25.2)
x0
xn
p(p − 1)(p − 2) 3
p(p − 1) 2
I=
4 y0 +
4 y0 + . . . dx
y0 + p4y0 +
2
6
x0
Z n
p(p − 1)(p − 2) 3
p(p − 1) 2
4 y0 +
4 y0 + . . . dp
I=h
y0 + p4y0 +
2
6
0
Z xn
n
n(2n − 3) 2
n(n − 2)2 3
ydx = nh y0 + 4y0 +
4 y0 +
4 y0 + . . .
2
12
24
x0
Z
(25.3a)
(25.3b)
(25.3c)
x = x0 + ph, dx = hdp
25.2
Trapezoidal Rule
Put n = 1 in 25.3c we get(all other differnces would become zero),
Z x1
1
h
1
ydx = h y0 + 4y0 = h y0 + (y1 − y0 ) = (y0 + y1 )
2
2
2
x0
For interval [x1 , x2 ]
Z
x2
ydx =
x1
For interval [xn−1 , xn ]
Z
xn
ydx =
xn−1
(25.4a)
h
(y1 + y2 )
2
(25.4b)
h
(yn−1 + yn )
2
(25.4c)
59
Check for Newton’s
forward difference
polynomial formula
Chapter 25. Numerical Integration
Summing up,
Z
xn
25.3. Simpson’s 1/3 Rule
h
[y0 + 2(y1 + y2 + . . . + yn−1 ) + yn ]
2
ydx =
x0
(25.4d)
Total Error E:
−1 3 00
(b − a) 2 00
h ny (¯
x) = −
h y (¯
x)
12
12
nh = b − a. 25.5 is called Error of Trapezoidal Rule.
E=
25.3
Simpson’s 1/3 Rule
Put n = 2 in 25.3c we get(all other differnces would become zero),
Z x2
1 2
h
ydx = 2h y0 + 4y0 + 4 y0 = (y0 + 4y1 + y2 )
6
3
x0
Z
x4
(25.6b)
h
(yn−2 + 4yn−1 + yn )
3
(25.6c)
x2
Z
xn
ydx =
xn−2
xn
ydx =
x0
(25.6a)
h
(y2 + 4y3 + y4 )
3
ydx =
Z
(25.5)
h
[y0 + 4(y1 + y3 + y5 + . . . + yn−1 ) + 2(y2 + y4 + y6 + . . . + yn−2 ) + yn ] (25.6d)
3
25.6d is called Simpson’s 1/3 rule.
Total Error E:
E=−
b−a 4 4
h y (¯
x)
180
(25.7)
25.7 is the Error E for Simpson’s 1/3 Rule.
25.4
Simpson’s 3/8 Rule
Put n = 3 in 25.3c we get(all other differnces would become zero),
Z x3
3
3 2
1 3
3h
ydx = 3h y0 + 4y0 + 4 y0 + 4 y0 =
(y0 + 3y1 + 3y2 + y3 )
2
4
8
8
x0
Z
x6
ydx =
x3
Z
3h
(y3 + 3y4 + 3y5 + y6 )
8
(25.8a)
(25.8b)
xn
3h
[y0 + 3y1 + 3y2 + 2y3 + 3y4 + 3y5 + 2y6 + . . . + 2yn−3 + 3yn−2 + 3yn−1 + yn ]
8
x0
(25.8c)
25.8c is called Simpson’s 3/8 rule.
Total Error E:
ydx =
E=−
3 5 4
h y (¯
x)
80
25.9 is the Error E for Simpson’s 3/8 Rule .
60
(25.9)
Check the formula
for Error of Simpson’s 3/8 rule
Chapter 26
LU decomposition for system of
linear equations
26.1
Introduction
LU factorization without pivoting:
A = LU
where A is any matrix, L is any lower triangular matrix, U is any upper triangular matrix.
26.2
Factorizing A as L and U
a11 A12
1
0
u
U12
A=
,L=
, U = 11
A21 A22
L21 L22
0 U22
a11 A12
1
0
u11 U12
u11
=
=
A21 A22
L21 L22
0 U22
u11 + L21
U12
L21 U12 + L22 U22
we get
u11 = a11 , U12 = A12 , L21 =
26.2.1
A21
a11
Example
8
A = 4
6
2
9
7
9
4
9
Split A as A = LU where L is the lower triangular matrix & U is theupper triangular matrix.
8 2 9
1
0
0
u11 u12 u13
0 0 u22 u23
A = 4 9 4 = l21 1
6 7 9
l31 l32 l33
0
0 u33
u11
u12
u13
l21 u12 + u22
l21 u13 + u23
= l21 u11
l31 u11 l31 u12 + l32 u22 l31 u13 + l32 u23 + l33 u33
Obtained Values:
u11 = 8, u12 = 2, u13 = 9
61
Chapter 26. LU decomposition for system of linear equations
26.3. Algorithm For solving
To obtain other values:
4
1
=
(∵ u11 = 8)
8
2
1
9 = l21 u12 + u22 =⇒ 9 = ∗ 2 + u22 =⇒ u22 = 8
2
1
1
4 = l21 u13 + u23 =⇒ 4 = ∗ 9 + u23 =⇒ u23 = −
2
2
3
6
(∵ u11 = 8)
l31 u11 = 6 =⇒ l31 = =
8
4
3
11
7 = l31 u12 + l32 u22 =⇒ 7 = ∗ 2 + l32 ∗ 8 =⇒ l32 =
4
16
3
11
1
27 11
83
9 = l31 u13 +l32 u23 +l33 u33 =⇒ 9 = ∗9+ ∗ − +u33 =⇒ u33 = 9− +
=⇒ u33 =
4
16
2
4 32
32
l21 u11 = 4 =⇒ l21 =
Therefore,
8
4
6
2
9
7
1
9
1
4 = 2
3
9
4
0
1
8
0
0 0
2
8
11
16
1
0
0
9
1
−2
83
32
1
Every non-singular A cannot be factorized as A= LU. Example:0
0
26.3
Algorithm For solving
1. AX = b =⇒ LUX = b. Solve for L and U using above algorithm.
z
2. LZ = b where Z = 1
z2
x
3. UX = Z where X = 1
x2
62
0
0
1
0
2
−1
Part IX
XML
63
Chapter 27
Basic Information
27.1
Basics
1. XML stands for eXtensible Markup Language.
2. XML is designed to transport and store data.
3. XML is important to know, and very easy to learn.
4. XML was designed to carry data, not to display data.
5. XML tags are not predefined. You must define your own tags.
6. XML is designed to be self-descriptive.
7. XML is a W3C Recommendation.
Difference between XML and HTML:
1. XML was designed to transport and store data, with focus on what data is.
2. HTML was designed to display data, with focus on how data looks.
Use of XML:
1. If you need to display dynamic data in your HTML document, it will take a lot of work
to edit the HTML each time the data changes.
2. With XML, data can be stored in separate XML files. This way you can concentrate on
using HTML/CSS for display and layout, and be sure that changes in the underlying data
will not require any changes to the HTML.
3. With a few lines of JavaScript code, you can read an external XML file and update the
data content of your web page.
4. Different applications can access your data, not only in HTML pages, but also from XML
data sources.
5. With XML, your data can be available to all kinds of "reading machines" (Handheld
computers, voice machines, news feeds, etc), and make it more available for blind people,
or people with other disabilities.
64
Chapter 27. Basic Information
27.2
27.2. Rules for XML Docs
Rules for XML Docs
1. In XML, it is illegal to omit the closing tag. All elements must have a closing tag.
2. XML tags are case sensitive. The tag <Letter> is different from the tag <letter>.
3. In XML, all elements must be properly nested within each other.
4. XML documents must contain one element that is the parent of all other elements. This
element is called the root element.
5. XML elements can have attributes in name/value pairs just like in HTML. In XML, the
attribute values must always be quoted.
6. Some characters have a special meaning in XML. If you place a character like "<" inside
an XML element, it will generate an error because the parser interprets it as the start of
a new element.
7. The syntax for writing comments in XML is similar to that of HTML. <!– This is a
comment –>
8. With XML, the white-space in a document is not truncated.
<
>
9. XML stores a new line as LF(Line Feed). Special Pre-Defined Symbols in XML: &
'
"
10. XML elements can be extended to carry more information without breaking applications.
27.3
XML Elements
An XML element is everything from (including) the element’s start tag to (including) the
element’s end tag.
An element can contain:
1. other elements
2. text
3. attributes
4. or a mix of all of the above...
Naming Rules:
XML elements must follow these naming rules:
1. Names can contain letters, numbers, and other characters
2. Names cannot start with a number or punctuation character
3. Names cannot start with the letters xml (or XML, or Xml, etc)
4. Names cannot contain spaces Any name can be used, no words are reserved.
65
<
>
&
’
"
less than
greater than
ampersand
apostrophe
quotation mark
Chapter 27. Basic Information
27.4
27.4. XML Attributes
XML Attributes
1. Attributes often provide information that is not a part of the data.
2. Attribute values must always be quoted. Either single or double quotes can be used.
3. Some of the problems with using attributes are:
(a) attributes cannot contain multiple values (elements can)
(b) attributes cannot contain tree structures (elements can)
(c) attributes are not easily expandable (for future changes) Attributes are difficult to
read and maintain. Use elements for data. Use attributes for information that is not
relevant to the data.
4. Sometimes ID references are assigned to elements. These IDs can be used to identify
XML elements in much the same way as the id attribute in HTML.
<messages>
<note id="501">
<to>Tove</to>
<from>Jani</from>
<heading>Reminder</heading>
<body>Don't forget me this weekend!</body>
</note>
<note id="502">
<to>Jani</to>
<from>Tove</from>
<heading>Re: Reminder</heading>
<body>I will not</body>
</note>
</messages>
5. DTD - Document Type Definition
6. The purpose of a DTD is to define the structure of an XML document. It defines the
structure with a list of legal elements.
7. A "Valid" XML document is a "Well Formed" XML document, which also conforms to
the rules of a Document Type Definition (DTD).
8. XML with correct syntax is "Well Formed" XML. XML validated against a DTD is
"Valid" XML.
9. XSLT is the recommended style sheet language of XML. XSLT (eXtensible Stylesheet
Language Transformations) is far more sophisticated than CSS. XSLT can be used to
transform XML into HTML, before it is displayed by a browser
66
Part X
Computer Networks
67
Chapter 28
Network Security
Definition 37 - Kerckhoff ’s principle.
Kerckhoff’s principle: All algorithms must be public; only the keys are secret.
28.0.1
Substitution Ciphers
Ceaser Cipher: Shift of letters by k position. KEY: k
Transposition Cipher: Reordering of letters without disguising them. KEY: Word or phrase
not containing any repeated letters.
One-time Pad:
Quantum Cryptography:
Cryptographic Principles:
1. Messages must contain some redundancy.
2. Some method is needed to foil replay attacks.
28.1
Public Key Algorithms
28.1.1
Diffie-Hellman Key Exchange
28.1.2
RSA
Requirements:
1. Choose two large primes, p and q (typically 1024 bits).
2. Compute n = p × q and z = (p − 1) × (q − 1).
3. Choose a number relatively prime to z and call it d.
4. Find e such that e × d = 1 mod z.
Steps:
1. Divide the plaintext (regarded as a bit string) into blocks, so that each plaintext message,
P , falls in the interval 0 ≤ P < n.
2. Do that by grouping the plaintext into blocks of k bits, where k is the largest integer for
which 2k < n is true.
68
Chapter 28. Network Security
28.2. Digital Signatures
3. To encrypt a message, P , compute C = P e ( mod n). To decrypt C, compute P =
C d ( mod n).
4. The public key consists of the pair (e, n) and the private key consists of (d, n).
28.1.3
Knapsack Algorithm
28.1.4
El Gamal Algorithm
28.2
Digital Signatures
28.2.1
Symmetric Key Signatures
A central authority that knows everything and whom everyone trusts, say, Big Brother (BB).
Each user then chooses a secret key and carries it by hand to BB’s office.
1. When Alice wants to send a signed plaintext message, P , to her banker, Bob, she generates
KA (B, RA , t, P ), where B is Bob’s identity, RA is a random number chosen by Alice, t is
a timestamp to ensure freshness, and KA (B, RA , t, P ) is the message encrypted with her
key, KA .
2. BB sees that the message is from Alice, decrypts it, and sends a message to Bob as shown.
3. The message to Bob contains the plaintext of Alice’s message and also the signed message
KBB (A, t, P ). Bob now carries out Alice’s request.
4. To guard against instant replay attacks, Bob just checks the RA of every incoming message
to see if such a message has been received from Alice in the past hour.
28.2.2
Public Key Signatures
Figure 28.1: Digital Signatures using public key
Problems:
1. If DA is changed, then applying old key doesnot lead to message P which is a porblem.
2. If DA is secret, then Bob can prove any forgery case against him. If DA is public, then
problem arises.
Digital Signature Standard (DSS) used a variant of El Gamal encrytpion with 1024 bit
keys.
69
Chapter 28. Network Security
28.2.3
28.2. Digital Signatures
Message Digests
Authentication scheme that does not require encrypting the entire message.
This scheme is based on the idea of a one-way hash function that takes an arbitrarily long piece
of plaintext and from it computes a fixed-length bit string.
This hash function, MD, often called a message digest, has four important properties:
1. Given P , it is easy to compute M D(P ).
2. Given M D(P ), it is effectively impossible to find P .
3. Given P , no one can find P 0 such that M D(P 0 ) = M D(P ).
4. A change to the input of even 1 bit produces a very different output.
Message digests save encryption time and message transport costs. In the Fig 28.1 Instead,
of signing P with KBB (A, t, P ), BB now computes the message digest by applying MD to P ,
yielding M D(P ). BB then encloses KBB (A, t, M D(P )) as the fifth item in the list encrypted
with KB that is sent to Bob, instead of KBB (A, t, P ).
In public key cryptosystems: Here, Alice first computes the message digest of her plaintext.
She then signs the message digest and sends both the signed digest and the plaintext to Bob.
If Trudy replaces P along the way, Bob will see this when he computes M D(P ).
SHA-1 & SHA-2
SHA: Secure Hash Algorithm.
SHA-1: It processes input data in 512-bit blocks, and it generates a 160-bit message digest.
Figure 28.2: SHA-1 algorithm from Alice to Bob
After receiving the message, Bob computes the SHA-1 hash himself and also applies AliceâĂŹs public key to the signed hash to get the original hash, H. If the two agree, the message
is considered valid. Since there is no way for Trudy to modify the (plaintext) message while it
is in transit and produce a new one that hashes to H, Bob can easily detect any changes Trudy
has made to the message. Used for integrity but not secrecy.
Working of SHA-1
1. It starts out by padding the message by adding a 1 bit to the end, followed by as many
0 bits as are necessary, but at least 64, to make the length a multiple of 512 bits.
70
Chapter 28. Network Security
28.2. Digital Signatures
2. Then a 64-bit number containing the message length before padding is ORed into the
low-order 64 bits.
3. During the computation, SHA-1 maintains five 32-bit variables, H0 through H4 , where
the hash accumulates. They are initialized to constants specified in the standard.
4. Each of the blocks M0 through Mn1 is now processed in turn.
5. For the current block, the 16 words are first copied into the start of an auxiliary 80-word
array, W. Then the other 64 words in W are filled in using the formula
Wi = S 1 (Wi−3 XOR Wi−8 XOR Wi−14 XOR Wi−16 )(16 ≤ i ≤ 79)
where S b (W ) represents the left circular rotation of the 32-bit word, W, by b bits.
6. Now five scratch variables, A through E, are initialized from H0 through H4 , respectively.
7. The actual calculation can be expressed in pseudo-C as
/*for (i = 0; i < 80; i++) {
temp = S 5 (A) + fi (B, C, D) + E + Wi + Ki ;
E = D; D = C; C = S 30 (B); B = A; A = temp;
}*/
where the Ki constants are defined in the standard.
8. The mixing functions fi are defined as
fi (B, C, D) = (B AND C)OR( NOT B AND D)
fi (B, C, D) = B XOR C XOR D
fi (B, C, D) = (B AND C)OR(B AND D)OR(C AND D)
fi (B, C, D) = B XOR C XOR D
(0 ≤ i ≤ 19)
(20 ≤ i ≤ 39)
(40 ≤ i ≤ 59)
(60 ≤ i ≤ 79)
9. When all 80 iterations of the loop are completed, A through E are added to H0 through
H4 , respectively.
10. Now that the first 512-bit block has been processed, the next one is started. The W array
is reinitialized from the new block, but H is left as it was.
11. When this block is finished, the next one is started, and so on, until all the 512-bit message
blocks have been tossed into the soup.
12. When the last block has been finished, the five 32-bit words in the H array are output as
the 160-bit cryptographic hash.
New versions of SHA-1 have been developed that produce hashes of 224, 256, 384, and 512 bits.
Collectively, these versions are called SHA-2.
MD5
1. The message is padded to a length of 448 bits (modulo 512).
2. Then the original length of the message is appended as a 64-bit integer to give a total
input whose length is a multiple of 512 bits.
3. Each round of the computation takes a 512-bit block of input and mixes it thoroughly
with a running 128-bit buffer.
71
Chapter 28. Network Security
28.3. Communication Security
4. For good measure, the mixing uses a table constructed from the sine function.
5. The point of using a known function is to avoid any suspicion that the designer built in
a clever back door through which only he can enter.
6. This process continues until all the input blocks have been consumed. The contents of
the 128-bit buffer form the message digest.
Birthday Attack
One might think that it would take on the order of 2m operations to subvert an m-bit message
m
digest. In fact, 2 2 operations will often do using the birthday attack. Birthday attack takes a
lot of time in computing message digrsts from SHA-1.
28.3
28.3.1
Communication Security
Firewalls
Keeps digital pests & intruders from using company’s LAN. A company can have many LANs
connected in arbitrary ways, but all traffic to or from the company is forced through an electronic
drawbridge (firewall), as shown in Fig. 28.3. No other route exists.
Figure 28.3: Firewall Protecting internal network
The firewall acts as a packet filter. It inspects each and every incoming and outgoing
packet. Packets meeting some criterion described in rules formulated by the network administrator are forwarded normally. Those that fail the test are uncermoniously dropped.
The filtering criterion is typically given as rules or tables that list sources and destinations that
are acceptable, sources and destinations that are blocked, and default rules about what to do
with packets coming from or going to other machines.
In the common case of a TCP/IP setting, a source or destination might consist of an IP address
and a port. Ports indicate which service is desired.
The DMZ is the part of the company network that lies outside of the security perimeter. Anything goes here. By placing a machine such as a Web server in the DMZ, computers on the
Internet can contact it to browse the company Web site. Now the firewall can be configured to
block incoming TCP traffic to port 80 so that computers on the Internet cannot use this port
72
Chapter 28. Network Security
28.3. Communication Security
to attack computers on the internal network.
Stateful firewalls map packets to connections and use TCP/IP header fields to keep track of
connections.
Another level of sophistication up from stateful processing is for the firewall to implement
application-level gateways.
Looking inside packets, beyond even the TCP header, to see what the application is doing.
With this capability, it is possible to distinguish HTTP traffic used for Web browsing from
HTTP traffic used for peer-to-peer file sharing.
Firewalls cannot prevent Denial of Service attacks, where an intruder sends thoudsands of
req. after establishing connection to bring own the web server.
73
Chapter 29
Application Layer
29.1
DNS - Domain Name System
The essence of DNS is the invention of a hierarchical, domain-based naming scheme and a
distributed database system for implementing this naming scheme. It is primarily used for
mapping host names to IP addresses but can also be used for other purposes.
1. To map a name onto an IP address, an application program calls a library procedure
called the resolver, passing it the name as a parameter.
2. The resolver sends a query containing the name to a local DNS server, which looks up
the name and returns a response containing the IP address to the resolver, which then
returns it to the caller.
3. The query and response messages are sent as UDP packets.
4. Armed with the IP address, the program can then establish a TCP connection with the
host or send it UDP packets.
DNS Name Space:
Figure 29.1: A portion of the Internet domain Figure 29.2: Domain Name Space mapped to
name space
zones
Each domain is named by the path upward from it to the (unnamed) root. The components
are separated by periods. Thus, the engineering department at Cisco might be eng.cisco.com.,
rather than a UNIX -style name such as /com/cisco/eng. Notice that this hierarchical naming
74
Chapter 29. Application Layer
29.2. HTTP - Hyper Text Transfer Protocol
means that eng.cisco.com. does not conflict with a potential use of eng in eng.washington.edu.,
which might be used by the English department at the University of Washington.
Domain Names: absolute or relative, case-insensitive .
Domain Resource Records: Every domain, whether it is a single host or a top-level domain,
can have a set of resource records associated with it. These records are the DNS database.
The primary function of DNS is to map domain names onto resource records. A resource record
is a five-tuple.
Domain_name
Time_to_live
Class
Type
Value
1. Domain name Tells the domain to which this record applies. Primary Key
2. Time to live Field gives an indication of how stable the record is. Seconds
3. Class For Internet information, it is always IN. For non-Internet information, other codes
can be used, but in practice these are rarely seen.
4. Type Tells what kind of record this is.
5. Value This field can be a number, a domain name, or an ASCII string. The semantics
depend on the record type.
Figure 29.3: DNS Resource Records Types
29.1.1
Name Servers
A single name server could contain the entire DNS database and respond to all queries about
it. The DNS name space is divided into nonoverlapping zones. Where the zone boundaries are
placed within a zone is up to that zone’s administrator.
29.2
HTTP - Hyper Text Transfer Protocol
Used to transport all this information between Web servers and clients. HTTP is a simple
request-response protocol that normally runs over TCP. It specifies what messages clients may
75
Chapter 29. Application Layer
29.2. HTTP - Hyper Text Transfer Protocol
send to servers and what responses they get back in return.
The request and response headers are given in ASCII, just like in SMTP. The contents are given
in a MIME-like format, also like in SMTP. Default Port: 80.
HTTP 1.0 After the connection was established a single request was sent over and a single response was sent back. HTTP 1.1
Figure 29.4: HTTP 1.1 with (a) multiple connections and sequential requests. (b)A persistent
connection and sequential requests. (c) A persistent connection and pipelined requests.
76
Chapter 30
Routing Algorithms
30.1
Introduction
1. The routing algorithm is that part of the network layer software responsible for
deciding which output line an incoming packet should be transmitted on.
2. If the network uses datagrams internally, this decision must be made anew for every
arriving data packet since the best route may have changed since last time.
3. If the network uses virtual circuits internally, routing decisions are made only when a new
virtual circuit is being set up. (Session Routing)
4. Difference between routing & forwarding: Routing - making the decision which routes
to use (filling & updating routing tables). Forwarding - handles each packet as it arrives,
looking up the outgoing line to use for it in the routing tables.
5. Desirable in a routing algorithm: correctness, simplicity, robustness, stability, fairness,
and efficiency.
6. Desired: Minimizing the mean packet delay, maximizing total network throughput.
7. Routing algorithms can be grouped into two major classes: nonadaptive and adaptive.
(a) Non Adaptive: Static Routing
(b) Adaptive: Dynamic Routing
8. Optimality Principle: It states that if router J is on the optimal path from router I to
router K, then the optimal path from J to K also falls along the same route.
9. The set of optimal routes from all sources to a given destination form a tree rooted at the
destination. Such a tree is called a sink tree.
10. DAG - Directed Acyclic Graphs. No Loops.
77
Chapter 30. Routing Algorithms
30.2
30.2. Shortest Path Algorithm - Dijsktra
Shortest Path Algorithm - Dijsktra
Algorithm 2 Calculate the shortest path from source node to all destination nodes
Input: A weighted undirected graph with source node and non-negative weights
Output: Shortest path between source node and all other nodes
1. Source node labelled(permanent : path fixed)
2. Other nodes unalbelled(temporary : path not fixed)
3. Node labelling ← (∞, −) : represents predecessor in shortest path route.
4. while All nodes are not visited do
5.
while All adjacent nodes are not visited do
6.
dist. ← distance between previous node and visited node.
7.
pred. ← Previous node
8.
Mark visited nodes with as(dist., pred.)
9.
end while
10.
Mark remaining nodes as (∞, −)
11.
Mark the smallest dist. node as permanent
12. end while
Figure 30.1: Sample run of Dijsktra’s Algorithm
78
Chapter 30. Routing Algorithms
30.3
30.3. Flooding
Flooding
1. Every incoming packet is sent out on every outgoing line except the one it arrived on.
2. Measures to prevent duplication:
(a) Hop counter contained in the header of each packet that is decremented at each
hop, with the packet being discarded when the counter reaches zero. Ideally, the hop
counter should be initialized to the length of the path from source to destination.
(b) Have routers keep track of which packets have been flooded, to avoid sending them
out a second time. One way to achieve this goal is to have the source router put a
sequence number in each packet it receives from its hosts.
30.4
Distance Vector Routing - Bellman Ford
A distance vector routing algorithm operates by having each router maintain a table (i.e.,
a vector) giving the best known distance to each destination and which link to use to get there.
These tables are updated by exchanging information with the neighbors. Eventually, every
router knows the best link to reach each destination.
Algorithm 3 Calculate the shortest path from source node to all destination nodes
Input: A weighted undirected graph with source node and non-negative weights
Output: Shortest path between any node and any nodes
1. shortestPath[n][n] ← Vector table containing shortest distances from Vi to Vj
2. distArray[n][n] ← distance array containing distance between distance between any node
to any node
3. distArray[i][j] ← distance between Vi & Vj .
4. delay[n][n] ← delay from any node to its neighbour nodes.
5. delay[i][j] ← delay from Vi to Vj . - if not a neighbour. k ∈ W if neighbour.
6. while all nodes are not visited do
7.
Vi ← visited, adj = 0
8.
for All nodes Vj adjacent to Vi do
9.
Calculate delay[i][j]
10.
adj++
11.
end for
12.
paths[adj] = 0
13.
for All nodes Vk do
14.
for All nodes Vj adjacent to Vi do
15.
paths[j] = delay[i][j] + distArray[j][k];
16.
end for
17.
min ← minimum value in paths[].
18.
shortestPath[i][k] = min
19.
end for
20. end while
79
Chapter 30. Routing Algorithms
30.5. Link State Routing
Figure 30.2: Sample run of Bellman Ford’s Algorithm
Count to infinity Problem: The settling of routes to best paths across the network is
called convergence.
30.5
Link State Routing
Variants of link state routing called IS-IS (Intermediate System-Intermediate System)
and OSPF (Open Shortest Path First).
Each router must do the following things to make it work:
1. Discover its neighbors and learn their network addresses.
2. Set the distance or cost metric to each of its neighbors.
3. Construct a packet telling all it has just learned.
4. Send this packet to and receive packets from all other routers.
5. Compute the shortest path to every other router.
In effect, the complete topology is distributed to every router. Then DijkstraâĂŹs algorithm
can be run at each router to find the shortest path to every other router. Compared to distance
vector routing, link state routing requires more memory and computation. But no problem of
slow convergence as in distance vector routing.
30.5.1
Learning abput neighbours
Sending a special HELLO packet on each point-to-point line. The router on the other end is
expected to send back a reply giving its name. A better way to model the LAN connecting
different routers is to consider it as a node itself.
80
Chapter 30. Routing Algorithms
30.5.2
30.5. Link State Routing
Setting Link Costs
A common choice is to make the cost inversely proportional to the bandwidth of the link. For
example, 1-Gbps Ethernet may have a cost of 1 and 100-Mbps Ethernet a cost of 10. This makes
higher-capacity paths better choices. Ig routers geogfraphoically spread, then delay could be
link cost.
30.5.3
Building Link State Packets
One possibility is to build them periodically, that is, at regular intervals. Another possibility
is to build them when some significant event occurs, such as a line or neighbor going down or
coming back up again or changing its properties appreciably.
Figure 30.3: Link Sate Packets
30.5.4
Distributing the Link State Packets
All of the routers must get all of the link state packets quickly and reliably.
Fundamental Idea
Use flooding to distribute the link state packets to all routers. To keep the flood in check, each
packet contains a sequence number that is incremented for each new packet sent. Routers keep
track of all the (source router, sequence) pairs they see. When a new link state packet comes
in, it is checked against the list of packets already seen. If it is new, it is forwarded on all lines
except the one it arrived on. If it is a duplicate, it is discarded.
Problems
1. Wrap around of sequence numbers: Solution - Use 32 bit seq. numbers.
2. If a router ever crashes, it will lose track of its sequence number.
3. If a sequence number is ever corrupted and 65,540 is received instead of 4 (a 1-bit error),
packets 5 through 65,540 will be rejected as obsolete, since the current sequence number
will be thought to be 65,540. Solution: include age of packet amd decrement it once per
second.
The send flags mean that the packet must be sent on the indicated link. The acknowledgement
flags mean that it must be acknowledged there. The situation with the third packet, from E,
is different. It arrives twice, once via EAB and once via EFB. Consequently, it has to be sent
only to C but must be acknowledged to both A and F, as indicated by the bits.
If a duplicate arrives while the original is still in the buffer, bits have to be changed. For
81
Chapter 30. Routing Algorithms
30.6. Hierarchial Routing
example, if a copy of CâĂŹs state arrives from F before the fourth entry in the table has
been forwarded, the six bits will be changed to 100011 to in- dicate that the packet must be
acknowledged to F but not sent there.
Figure 30.4: Packet Buffer for Router B
30.5.5
Computing Shortest Path
Every link in the newtwork graph is, in fact, represented twice, once for each direction.Dijkstra’s
algorithm can be run locally to construct the shortest paths to all possible destinations. The
results of this algorithm tell the router which link to use to reach each destination. This
information is installed in the routing tables, and normal operation is resumed.
30.6
Hierarchial Routing
When hierarchical routing is used, the routers are divided into what we will call regions. Each
router knows all the details about how to route packets to destinations within its own region
but knows nothing about the internal structure of other regions. For huge networks, a two-level
hierarchy may be insufficient; it may be necessary to group the regions into clusters, the clusters
into zones, the zones into groups, and so on.
82
Use a 32-bit sequence number.
With one link state
packet per second, it would take
137 years to wrap
around. Time =
2no. of bits
. Here
BW
BW = 1lsp/sec. no.
of bits = 32
Chapter 30. Routing Algorithms
30.7. Broadcast Routing
Figure 30.5: Hierarchial Routing
For example, consider a network with 720 routers. If there is no hierarchy, each router needs
720 routing table entries. If the network is partitioned into 24 regions of 30 routers each, each
router needs 30 local entries plus 23 remote entries for a total of 53 entries. If a three-level
hierarchy is chosen, with 8 clusters each containing 9 regions of 10 routers, each router needs
10 entries for local routers, 8 entries for routing to other regions within its own cluster, and 7
entries for distant clusters, for a total of 25 entries. Optimal no. of levels in N routers is ln N
making total of e ln N no. of entries per router.
30.7
Broadcast Routing
Sending a packet to all destinations simultaneously is called broadcasting. The network bandwidth is therefore used more efficiently.
Problems: Source to know all the destinations, Router to determine where to send one multidestination packet as it is for multiple distinct packets.
Better broadcast routing technique: Flooding. When implemented with a sequence number per source, flooding uses links efficiently with a decision rule at routers.
Reverse path forwarding: Spanning tree Algorithm: A spanning tree is a subset of the
network that includes all the routers but contains no loops. Sink trees are spanning trees. If
each router knows which of its lines belong to the spanning tree, it can copy an incoming broadcast packet onto all the spanning tree lines except the one it arrived on. This method makes
excellent use of bandwidth, generating the absolute minimum number of packets necessary to
do the job.
83
did not understand
Chapter 30. Routing Algorithms
30.8
30.8. Multicast Routing
Multicast Routing
Sending a message to such a group is called multicasting, and the routing algorithm used is
called multicast routing. All multicasting schemes require some way to create and destroy
groups and to identify which routers are members of a group.
Multicast routing schemes build on the broadcast routing schemes we have already studied,
sending packets along spanning trees to deliver the packets to the members of the group while
making efficient use of bandwidth.
Types of pruning spanning trees:
1. MOSPF (Multicast OSPF)
(a) If link state routing is used and each router is aware of the complete topology,
including which hosts belong to which groups.
(b) Each router can then construct its own pruned spanning tree for each sender to
the group in question by constructing a sink tree for the sender as usual and then
removing all links that do not connect group members to the sink node.
2. DVMRP (Distance Vector Multicast Routing Protocol)
(a) With distance vector routing, a different pruning strategy can be followed.
(b) The basic algorithm is reverse path forwarding. However, whenever a router with
no hosts interested in a particular group and no connections to other routers receives
a multicast message for that group, it responds with a PRUNE message, telling the
neighbor that sent the message not to send it any more multicasts from the sender
for that group.
(c) When a router with no group members among its own hosts has received such messages on all the lines to which it sends the multicast, it, too, can respond with a
PRUNE message.
30.9
30.9.1
IPv4 - Network Layer
Communication in Internet
The transport layer takes data streams and breaks them up so that they may be sent as IP
packets. In theory, packets can be up to 64 KB each, but in practice they are usually not
more than 1500 bytes (so they fit in one Ethernet frame). IP routers forward each packet
through the Internet, along a path from one router to the next, until the destination is reached.
At the destination, the network layer hands the data to the transport layer, which gives it
to the receiving process. When all the pieces finally get to the destination machine, they are
reassembled by the network layer into the original datagram. This datagram is then handed to
the transport layer.
84
Chapter 30. Routing Algorithms
30.9. IPv4 - Network Layer
Figure 30.6: IPv4 Header
85
Chapter 31
Error & Flow control - Data Link
Layer
31.1
Introduction
The data link layer uses the services of the physical layer to send and receive bits over communication channels. It has a number of functions, including:
1. Providing a well-defined service interface to the network layer.
2. Dealing with transmission errors.
3. Regulating the flow of data so that slow receivers are not swamped by fast senders.
4 methods to break bit streams into frames:
1. Byte count.
2. Flag bytes with byte stuffing.
3. Flag bits with bit stuffing.
31.1.1
Byte Count
A field in the header to specify the number of bytes in the frame. When the data link layer at
the destination sees the byte count, it knows how many bytes follow and hence where the end
of the frame is.
86
Chapter 31. Error & Flow control - Data Link Layer
31.1. Introduction
Figure 31.1: Byte Count (a) Without errors. (b) With one error.
31.1.2
Byte Stuffing
1. Add FLAG byte at the start and end of each frame. Two consecutive flag bytes indicate
the end of one frame and the start of the next.
2. If FLAG byte in data of the frame, then add ESC byte to the before of FLAG byte.
3. If ESC occurs in th e middle of the data, then stuff it with an ESC byte.
Byte Stuffing is used in PPP(Point to Point Protocol).
87
Chapter 31. Error & Flow control - Data Link Layer
31.1. Introduction
Figure 31.2: Byte Stuffing (a) A frame delimited by flag bytes. (b) Four examples of byte
sequences before and after byte stuffing.
31.1.3
Bit Stuffing
Used in HDLC(High-level Data Link Control).
1. Each frame begins and ends with a special bit pattern, 01111110 or 0x7E in hexadecimal.
- FLAG Byte.
2. Whenever the sender’s data link layer encounters five consecutive 1s in the data, it automatically stuffs a 0 bit into the outgoing bit stream - ESC Byte.
3. When the receiver sees five consecutive incoming 1 bits, followed by a 0 bit, it automatically destuffs (i.e., deletes) the 0 bit.
Suppose 111110 is in
data, does receiver
destuff that leading
to wrong information (in Bit Stuffing)?
88
Chapter 31. Error & Flow control - Data Link
31.2.
Layer
Error Correction & Detection
Figure 31.3: Bit Stuffing (a) The original data. (b) The data as they appear on the line. (c)
The data as they are stored in the receiver’s memory after destuffing.
31.2
31.2.1
Error Correction & Detection
Error Correcting Codes
1. Hamming codes.
2. Binary convolutional codes.
3. Reed-Solomon codes.
4. Low-Density Parity Check codes.
In a systematic code, the m data bits are sent directly, along with the check bits, rather
than being encoded themselves before they are sent. In a linear code, the r check bits are
computed as a linear function of the m data bits.
Definition 38 - Codeword.
A frame generally consists of m data bits (message) and r code (redundant/check) bits to
form an n bit codeword where n = m + r.
Hamming Codes
Definition 39 - Hamming distance.
The number of different digits d(x, y) between two codewords x and y. For example, 000
and 111 have a Hamming distance of 3.
Definition 40 - Coderate.
The fraction of the codeword that carries information that is not redundant, or
m
.
n
Definition 41 - Even Parity.
In the case of even parity, the number of bits whose value is 1 in a given set are
counted. If that total is odd, the parity bit value is set to 1, making the total count of 1’s in
the set an even number. If the count of ones in a given set of bits is already even, the parity
bit’s value remains 0.
Definition 42 - Odd Parity.
In the case of odd parity, the situation is reversed. Instead, if the sum of bits with a value of
1 is odd, the parity bit’s value is set to zero. And if the sum of bits with a value of 1 is even,
the parity bit value is set to 1, making the total count of 1’s in the set an odd number.
89
Chapter 31. Error & Flow control - Data Link
31.2.
Layer
Error Correction & Detection
If two codewords are a Hamming distance d apart, it will require d single-bit errors to convert
one into the other. To reliably detect d errors, you need a distance d + 1 code because with
such a code there is no way that d single-bit errors can change a valid codeword into another
valid codeword. To correct d errors, you need a distance 2d + 1 code because that way the legal
codewords are so far apart that even with d changes the original codeword is still closer than
any other codeword. Number of check bits needed to correct single errors: (m + r + 1) ≤ 2r .
The bits that are powers of 2 (1, 2, 4, 8, 16, etc.) are check bits. The rest (3, 5, 6, 7, 9, etc.)
are filled up with the m data bits. This construction gives a code with a Hamming distance of
3 (11 = 1 + 2 + 8. max 3 numbers), which means that it can correct single errors (or detect
double errors).
Example: Message - 1000001. To compute check bits: express rest of bits in as a summation
of check bits. ex., 11 = 1 + 2 + 8. No. of 2’s in expanded sum gives the parity for 2 in new
message. Sent Message: 0 0 1 0 0 0 0 1 0 0 1, Received Mwssage: 0 0 1 0 1 0 0 1 0 0 1.
Check bits should be computed including check bits: 1 : 1, 2 : 0, 4 : 1, 8 : 0. Recheck parity bits:
1 : 1, 2 : 0, 4 : 1, 8 : 1. A single-bit error occurred on the channel so the check results are 0, 1,
0, and 1 for k = 8, 4, 2, and 1. Parity bits of 4 and 1 are changed. Therefore, bit 4 + 1 = 5
should be flipped.
Figure 31.4: Hamming Codes for (11, 7) for even parity
Convolution Codes
Not a block code. An encoder processes a sequence of input bits and generates a sequence of
output bits. Output depends on current and previous input bits(memory). The number of
previous bits on which the output depends is called the constraint length of the code.
90
Chapter 31. Error & Flow control - Data Link
31.2.
Layer
Error Correction & Detection
Figure 31.5: Convolution Codes
Reed Solomon Codes
Reed-Solomon codes are linear block codes. Reed-Solomon codes are based on the fact that
every n degree polynomial is uniquely determined by n + 1 points. we have two data points
that represent a line and we send those two data points plus two check points chosen to lie on
the same line. If one of the points is received in error, we can still recover the data points by
fitting a line to the received points. Three of the points will lie on the line, and one point, the
one in error, will not. By finding the line we have corrected the error.
For m bit symbols, the codewords are 2m − 1 symbols long. A popular choice is to make m = 8
so that symbols are bytes. A codeword is then 255 bytes long. The (255, 233) code is widely
used; it adds 32 redundant symbols to 233 data symbols.
They are based on m bit symbols, a single-bit error and an m-bit burst error are both treated
simply as one symbol error. When 2t redundant symbols are added, a Reed-Solomon code is
able to correct up to t errors in any of the transmitted symbols. This means, for example, that
the (255, 233) code, which has 32 redundant symbols, can correct up to 16 symbol errors. Since
the symbols may be consecutive and they are each 8 bits, an error burst of up to 128 bits can
be corrected.
31.2.2
Error Detecting Codes
1. Parity.
2. Checksums.
3. Cyclic Redundancy Checks (CRCs).
Parity
A single parity bit is appended to the data. The parity bit is chosen so that the number of 1
bits in the codeword is even (or odd). For example, when 1011010 is sent in even parity, a bit
is added to the end to make it 10110100. With odd parity 1011010 becomes 10110101. A code
with a single parity bit has a distance of 2, since any single-bit error produces a codeword with
the wrong parity. This means that it can detect single-bit errors.
91
Chapter 31. Error & Flow control - Data Link
31.2.
Layer
Error Correction & Detection
Figure 31.6: Interleaving parity
Checksums
The checksum is usually placed at the end of the message, as the complement of the sum
function. This way, errors may be detected by summing the entire received codeword, both
data bits and checksum. If the result comes out to be zero, no error has been detected.
CRC(Cyclic Redundancy Check)
How to calculate
and detect errors in
checksum?
For example, 110001 has 6 bits and thus represents a six-term polynomial with coefficients 1,
1, 0, 0, 0, and 1: 1x5 + 1x4 + 0x3 + 0x2 + 0x1 + 1x0 . Addition and substraction in XOR format.
When the polynomial code method is employed, the sender and receiver must agree upon a
generator polynomial, G(x), in advance. Both the high and low-order bits of the generator
must be 1. To compute the CRC for some frame with m bits corresponding to the polynomial
M (x), the frame must be longer than the generator polynomial. The idea is to append a CRC
to the end of the frame in such a way that the polynomial represented by the checksummed
frame is divisible by G(x). When the receiver gets the checksummed frame, it tries dividing it
by G(x). If there is a remainder, there has been a transmission error.
1. Let r be the degree of G(x). Append r zero bits to the low-order end of the frame so it
now contains m + r bits and corresponds to the polynomial xr M (x).
2. Divide the bit string corresponding to G(x) into the bit string corresponding to xr M (x),
using modulo 2 division.
3. Subtract the remainder (which is always r or fewer bits) from the bit string corresponding
to xr M (x) using modulo 2 subtraction. The result is the checksummed frame to be
transmitted. Call its polynomial T (x).
How are error detected in CRC?
92
Chapter 31. Error & Flow control - Data Link Layer 31.3. Data Link Protocols
Figure 31.7: Calculating CRC
31.3
31.3.1
Data Link Protocols
Simplex Protocol
Assumptions: Error free flow of information, simplex protocol. Sender: The sender in data
link layer receives packet fom the network layer of sender. The data link layer breaks the packets
into frames and passes onto the receiver in the data link layer. Receiver: The receiver receives
the frames from the sender of data link layer. It then passes it to network layer of receiver and
waits foor other frames..
31.3.2
Stop & Wait Protocol for Error free
Preventing the sender from flooding the receiver with frames faster than the latter is able to
process them. After having passed a packet to its network layer, the receiver sends a little
dummy frame back to the sender which, in effect, gives the sender permission to transmit the
next frame. After having sent a frame, the sender is required by the protocol to bide its time
until the little dummy (i.e., acknowledgement) frame arrives.
93
Chapter 31. Error & Flow control - Data Link Layer 31.3. Data Link Protocols
31.3.3
Stop & Wait Protocol for Noisy Channel
Example: ARQ (Automatic Repeat reQuest)
31.3.4
Sliding Window Protocols
Piggybacking: Sender of data link layer sends frames to data link layer of receiver and starts
timer for acknowledgement to come. After receiving the frame, instead of sending acknowledgement the receiver waits for packet from network layer and attaches the ack to it and sends it
to the sender of dll. If n/w layer doesn’t send any packet ack frame is sent separately. Use of
sequence nos. to avoid duplication. Use of kind field in header to find out if frame is data or
control(ack) in full-duplex channel(two way communication).
The sender maintains a set of sequence numbers corresponding to frames it is permitted to
send. These frames are said to fall within the sending window. Similarly, the receiver also
maintains a receiving window corresponding to the set of frames it is permitted to accept.
The sequence numbers within the sender’s window represent frames that have been sent or can
be sent but are as yet not acknowledged. Whenever a new packet arrives from the network layer,
it is given the next highest sequence number, and the upper edge of the window is advanced by
one. When an acknowledgement comes in, the lower edge is advanced by one. In this way the
window continuously maintains a list of unacknowledged frames.
Figure 31.8: A sliding window of size 1, with a 3-bit sequence number. (a) Initially. (b) After
the first frame has been sent. (c) After the first frame has been received. (d) After the first
acknowledgement has been received.
1 bit Sliding Window Protocol
Assume that computer A is trying to send its frame 0 to computer B and that B is trying to
send its frame 0 to A. Suppose that A sends a frame to B, but A’s timeout interval is a little too
94
Chapter 31. Error & Flow control - Data Link Layer 31.3. Data Link Protocols
short. Consequently, A may time out repeatedly, sending a series of identical frames, all with
seq = 0 and ack = 1. When the first valid frame arrives at computer B, it will be accepted and
frame expected will be set to a value of 1. All the subsequent frames received will be rejected
because B is now expecting frames with sequence number 1, not 0. Furthermore, since all the
duplicates will have ack = 1 and B is still waiting for an acknowledgement of 0, B will not go
and fetch a new packet from its network layer.
After every rejected duplicate comes in, B will send A a frame containing seq = 0 and ack
= 0. Eventually, one of these will arrive correctly at A, causing A to begin sending the next
packet. No combination of lost frames or premature timeouts can cause the protocol to deliver
duplicate packets to either network layer, to skip a packet, or to deadlock. The protocol is
correct.
Figure 31.9: (a) Normal case. (b) Abnormal case. The notation is (seq, ack, packet number).
An asterisk indicates where a network layer accepts a packet.
Go Back N
Bandwidth Delay Product(BDP) = Bandwidth(bits/sec) × One-way transit time
BDP
BD =
No. of frames
Max no. of frames to be sent before blocking = Max. window size = w = 2BD + 1.
Link Utilization ≤
95
w
2BD + 1
Chapter 31. Error & Flow control - Data Link Layer 31.3. Data Link Protocols
Figure 31.10: Pipelining and error recovery. Effect of an error when (a) receiver’s window size
is 1(Go Back n) and (b) receiver’s window size is large(Selective Repeat).
Selective Repeat
Please understand
seletive repeat
96
Chapter 31. Error & Flow control - Data Link Layer 31.3. Data Link Protocols
Figure 31.11: (a) Initial situation with a window of size 7. (b) After 7 frames have been sent
and received but not acknowledged. (c) Initial situation with a window size of 4. (d) After 4
frames have been sent and received but not acknowledged.
Window size ≤ Sequence number. [?], [?], [5]. What is the maximum window size? The
receiver must be able to distinguish a retransmission of an already received packet from the
original transmission of a new packet. Thus the maximum window size is:
1. 2n − 1 in the case of Go-Back-N. Here the receiver accepts only the next expected packet
and discards all out-of-order packets. In the example, with a 2-bit sequence number the
maximum window size is 3
2.
2n
in Selective Repeat. Since the receiver accepts out-of-order packets, two consecutive
2
windows should not overlap. Otherwise it is not able to distinguish duplicates from new
transmissions. Hence, in the example the maximum window size is 2
97
Chapter 32
Data Link Layer Switching
32.1
Bridges
Definition 43 - Bridges.
Bridges are used for connecting multiple LAN’s into a single logical LAN in an organization.
Bridges operate in the data link layer, so they examine the data link layer addresses to forward
frames. They can handle IP packets as well as other kinds of packets. Different kinds of cables
can also be attached to one bridge.
Definition 44 - VLAN(Virtual LAN).
Treat one physical LAN as multiple logical LANs.
Figure 32.1: a) Bridge connecting two multidrop LANs. (b) Bridges (and a hub) connecting
seven point-to-point stations.
32.1.1
Learning Bridges
The bridge must decide whether to forward or discard each frame, and, if the former, on which
port to output the frame. A simple way to implement this scheme is to have a big (hash) table
inside the bridge. The table can list each possible destination and which output port it belongs
on.
98
Chapter 32. Data Link Layer Switching
32.1. Bridges
When the bridges are first plugged in, all the hash tables are empty. None of the bridges know
where any of the destinations are, so they use a flooding algorithm: every incoming frame for
an unknown destination is output on all the ports to which the bridge is connected except the
one it arrived on. As time goes on, the bridges learn where destinations are. Once a destination
is known, frames destined for it are put only on the proper port; they are not flooded.
To handle dynamic topologies, whenever a hash table entry is made, the arrival time of the
frame is noted in the entry. Whenever a frame whose source is already in the table arrives, its
entry is updated with the current time. Thus, the time associated with every entry tells the
last time a frame from that machine was seen.
The routing procedure for an incoming frame depends on the port it arrives on (the source
port) and the address to which it is destined (the destination address).
1. If the port for the destination address is the same as the source port, discard the frame.
2. If the port for the destination address and the source port are different, forward the frame
on to the destination port.
3. If the destination port is unknown, use flooding and send the frame on all ports except
the source port.
Bridges only look at the MAC addresses to decide how to forward frames, it is possible to start
forwarding as soon as the destination header field has come in, before the rest of the frame
has arrived (provided the output line is available, of course). This design reduces the latency
of passing through the bridge, as well as the number of frames that the bridge must be able
to buffer. It is referred to as cut-through switching or wormhole routing and is usually
handled in hardware.
32.1.2
Spanning Trees
Figure 32.2: Bridges with two parallel links.
Bridges to communicate with each other and overlay the actual topology with a spanning tree
that reaches every bridge (to avoid looping).
To build the spanning tree, the bridges run a distributed algorithm. Each bridge periodically
broadcasts a configuration message out all of its ports to its neighbors and processes the messages it receives from other bridges, as described next. These messages are not forwarded, since
their purpose is to build the tree, which can then be used for forwarding.
To make the choice of root, they each include an identifier based on their MAC address in the
99
Chapter 32. Data Link Layer Switching
32.1. Bridges
configuration message, as well as the identifier of the bridge they believe to be the root. MAC
addresses are installed by the manufacturer and guaranteed to be unique worldwide, which
makes these identifiers convenient and unique. The bridges choose the bridge with the lowest
identifier to be the root.
To find these shortest paths, bridges include the distance from the root in their configuration
messages. Each bridge remembers the shortest path it finds to the root. The bridges then turn
off ports that are not part of the shortest path.
Figure 32.3: (a) Which device is in which layer. (b) Frames, packets, and headers.
100
Chapter 33
Transport Layer
33.1
Introduction
Figure 33.1: The primitives of Transport Layer.
Figure 33.2: The primitives of TCP socket.
101
Chapter 34
Internet Protocol - IP
34.1
IPv4
Figure 34.1: IPv4 Header
102
Chapter 35
Network Layer
1. Physical Address - MAC Address: System Address:LAN card address:Ethernet address.
Points to main memory.
2. Communication done with logical address - IP address. Types: Classful addressing,
subnetting, supernetting.
(a) Classful Addressing: 2 parts: net-id, hosts; 2 notations: binary: 00000011 00000011
00000011 00000011, octet: 255.255.255.255
(b) Unicasting: Transfer data from one system to another system. Supported by class
A,B,C.
(c) Multicasting: Transfers data from one systems to many systems. Suported by Class
D.
(d) Class E : Future Use. First 4 bits in net-ID: 1111. IP address range(240 - 255).
1. Part of CIDR (Classless Inerdomain Routing)
2. Class A: 1st bit of net ID should be 0. net-ID(8 bits): 27 −2 bits(no. of possible networks).
host-ID(24 bits): 224 −2(no. of possible hosts). IP address range(0 -126). 0.0.0.0 - DHCP,
127.x.y.z - Loopback.
3. Class B: 1st , 2nd bit of net ID should be 10. net-ID(16 bits): 214 bits(no. of possible
networks). host-ID(16 bits): 216 − 2(no. of possible hosts). IP address range(128 -191).
4. Class C: 1st , 2nd , 3rd bit of net ID should be 110. net-ID(24 bits): 221 bits(no. of possible
networks). host-ID(8 bits): 28 − 2(no. of possible hosts). IP address range(192 -223).
5. Class D: 1st , 2nd , 3rd , 4th bit of net ID should be 1110. net-ID( bits): 2 bits(no. of possible
networks). host-ID( bits): 2 − 2(no. of possible hosts). IP address range(224 - 239).
6. Class D & Class E cannot be divided into net-ID & host-ID because of multicasting.
7. Net masks for various classes:(net-ID all 0’s and host-Id all 1’s)
(a) Class A - 255.0.0.0
(b) Class B - 255.255.0.0
(c) Class C - 255.255.255.0
8. Calculation of net-ID:
(a) Identify class of IP address.
103
Check about net
mask
Chapter 35. Network Layer
35.1. Subnetting
(b) Calculate net mask for that class.
(c) Perform bitwise AND operation between IP address and net mask.
9. Range of private IP addresses:(for communication within LAN)
(a) Class A: 10.0.0.0 - 10.255.255.255 - 1n/w
(b) Class B: 172.16.0.0 - 172.31.255.255 - 16 n/w
(c) Class C: 192.168.0.0 - 192.168.255.255 - 255 n/w
10. NAT - Network Address Translator. Converts private IP to public IP when pkt going
outside the n/w & public IP to private IP if pkt coming in the n/w.
11. Destination Broadcast address
12. Limited Broadcast address
1. Service addressing system - Port address: 16 bits. also known as logical ports
2. Predefined ports like http, smtp etc., (0 - 1023).
3. Registered ports (1024 - 49151)
4. Dynamic Ports - (49152 - 65535)
5.
Learn about DHCP
35.1
Subnetting
1. Borrows bits from host-ID. Security is high.
2. Given subnet mask, we can calculate no. of subnets and no. of hosts in each subnet
3. Subnet-ID = IP Address AND subnet mask.
4. Example: Subnet mask of class B: 255.255.240.0. Default Mask for class B: 255.255.0.0.
Subnet bits are no. of bits having 1’s in the host bits of mask.
Subnet mask = |255.255
240 . |{z}
0
{z } . |{z}
Net-ID
subnet
host
No. of subnets = 24 − 2 = 14. no. of hosts in each subnet = 212 − 2 = 4094
5. Example: IP address: 197.111.121.199 & Subnet mask: 255.255.255.240. Calculate
subnet-ID.
197.111.121.199 & 255.255.255.240 = 197.111.121.192
197.111.121.192 = 11000101.01101111.01111001.11000000. no. of 1’s in host part = 4.
Total no .of subnets = 14. Total no. of hosts = 126.
(a) /28 means 28 1’s in the subnet mask.
(b) 1st subnet id: 197.111.121.16/28(in slash notaion of CIDR) - 11000101.01101111.01111001.00010000
(c) 2nd subnet id: 197.111.121.32/28 - 11000101.01101111.01111001.00100000
(d) 3rd subnet id: 197.111.121.48/28 - 11000101.01101111.01111001.00110000
(e) Last subnet id: 197.111.121.224/28 - 11000101.01101111.01111001.11100000
(f) Last host of subnet id: 197.111.121.238/28 - 11000101.01101111.01111001.11101110
104
Chapter 35. Network Layer
35.2
35.2. Classless Addressing
Classless Addressing
1. It consists of only blocks.
2. IP address given along with mask.
3. 1st address of the block should be divisible by no. of addresses in the block.
4. Addresses must be contiguous.
5. Every address in a block must be a power of 2.
6. Example: One of the addresses in a block is 167.199.170.82/27. find no. of addresses
and 1st & last address.
This block consists of No .of hosts = 25 = 32. No. of address in a block is determined by
subnet mask.
1st address 82 → 01010010. Replace the last 5 bits by 0’s. Therefore 1st address is
01000000. Last address is 01011111.
7. When all subnet bits are 0 → zero subnet.
8. When all subnet bits are 1 → all ones subnet.
105
Chapter 36
Physical Layer
36.1
Introduction
Definition 45 - Transmission time.
Time taken to place the data on the channel.
Transmission Time(TX ) =
Transmission Time(Tack ) =
Mesage size
Bandwidth
Acknowledgement size
Bandwidth
Definition 46 - Propagation Time.
Time taken by data to propagate to reach the destination.
Propagation Time(PX ) =
Distance
Velocity
Propagation Time(Pack ) =
Distance
Velocity
Total Time = TX + PX + P ack = TX + 2PX
Link Utilization of Sender =
Message size
TX
=
Total Time
Message size + Bandwidth*RTT
Round Trip Time(RTT) = 2 × PX
Definition 47 - Processing Time.
Time taken to generate the data.
1. At sender headers are added & at receiver headers are removed.
2. Physical address points to Data Link Layer - Bridge
3. Logical address points to Network Layer - Router
4. Port address points to Transport Layer - Gateway
106
Part XI
Calculus
107
Chapter 37
Continuity
Definition 48 - Continuity.
Let D ∈ R . Consider a function f : D → R and a point c ∈ D. We say that f is continuous at c if
(xn ) any sequence in D and xn → c =⇒ f (xn ) → f (c).
If f is not continuous at c, we say that f is discontinuous at c. In case f is continuous at
every c ∈ D, we say that f is continuous on D.
Definition 49 - Dirichlet Function.
f (x) =
1
0
if x is rational
if x is irrational
Lemma 8.1.
Let D ⊆ R, c ∈ D, and let f : D → R be a function that is continuous at c. If f (c) > 0,
then there is δ > 0 such that f (x) > 0 whenever x ∈ D and |x − c| < δ. Likewise, if f (c) < 0,
then there is δ > 0 such that f (x) < 0 whenever x ∈ D and |x − c| < δ.
Proposition 8.1.
Let D ⊆ R, c ∈ D, and let f, g : D → R be functions that are continuous at c. Then
1. f + g is continuous at c,
2. rf is continuous at c for any r ∈ R,
3. f g is continuous at c,
4. if f (c) = 0, then there is δ > 0 such that f (x) = 0 whenever x ∈ D and |x − c| < δ;
1
moreover the function : D ∩ (c − δ, c + δ) → R is continuous at c,
f
5. if there is δ > 0 such that f (x) ≥ 0 whenever x ∈ D and |x − c| < δ, then for any k ∈ N ,
1
the function f k : D ∩ (c − δ, c + δ) → R is continuous at c.
108
Chapter 38
Differentiation
Lemma 8.2.
Let D ⊆ R and c be an interior point of D. If f : D → R is differentiable at c and has a
local extremum at c, then f (c) = 0.
Proposition 8.2 - Rolle’s Theorem.
If f : [a, b] → R is continuous on [a, b] and differentiable on (a, b) and if f (a) = f (b), then
there is c ∈ (a, b) such that f (c) = 0.
Proposition 8.3 - Mean Value Theorem.
If a function f : [a, b] → R is continuous on [a, b] and differentiable on (a, b), then there is
c ∈ (a, b) such that
f (b) − f (a) = f 0 (c)(b − a).
109
Chapter 39
Integration
Proposition 8.4.
Let f : [a, b] → R be a bounded function. Then for any partition P of [a, b], we have
m(f )(b − a) ≤ L(P, f ) ≤ U (P, f ) ≤ M (f )(b − a).
where
L(P, f ) :=
n
X
mi (f )(xi − xi−1 )
i=0
U (P, f ) :=
n
X
Mi (f )(xi − xi−1 ).
i=0
L(P, f) = Lower Sum, U(P, f) = Upper Sum
Proposition 8.5 - Basic Inequality on Riemann’s Integral.
Suppose f : [a, b] → R is an integrable function and there are α, β ∈ R such that β ≤ f ≤ α.
Then
Z b
β(b − a) ≤
f (x)dx ≤ α(b − a).
a
. In particular, if |f | ≤ α, then
Z
b
f (x)dx ≤ α(b − a).
a
Proposition 8.6 - Domain Additivity of Riemann Integrals.
Let f : [a, b] → R be a bounded function and let c ∈ (a, b). Then f is integrable on [a, b]
if and only if f is integrable on [a, c] and on [c, b]. In this case,
Z b
Z c
Z b
f (x)dx =
f (x)dx +
f (x)dx
a
a
c
Proposition 8.7.
Let f : [a, b] → R be a function.
1. If f is monotonic, then it is integrable.
2. If f is continuous, then it is integrable.
Proposition 8.8.
Let f, g : [a, b] → R be integrable functions. Then
110
Chapter 39. Integration
1. f + g is integrable and
Rb
(f + g)(x)dx =
Rb
f (x)dx +
Rb
g(x)dx,
Rb
Rb
2. rf is integrable for any r âĹĹ R and a b a (rf )(x)dx = r a f (x)dx,
a
a
a
3. f g is integrable,
4. If there is δ > 0 such that |f (x)| ≥ δ and all x ∈ [a, b], then
1
is integrable,
f
1
k
5. If f (x) ≥ 0 for all x ∈ [a, b], then for any k ∈ N , the function f is integrable.
Proposition 8.9.
Let f, g : [a, b] → R be integrable.
Rb
Rb
1. If f ≤ g, then a f (x)dx ≤ a g(x)dx.
R
R
b
b
2. The function |f | is integrable and a f (x)dx ≤ a |f | (x)dx.
Proposition 8.10 - Fundamental Theorem of Calculus.
Let f : [a, b] → R be integrable.
1. If f has an antiderivative F , then
Z x
f (t)dt = F (x) − F (a) for all x ∈ [a, b]
a
.
2. Let F : [a, b] → R be defined by
Z
x
F (x) =
f (t)dt.
a
If f is continuous at c ∈ [a, b], then F is differentiable at c and
F 0 (c) = f (c).
In particular, if f is continuous on [a, b], then F is an antiderivative of f on [a, b].
Proposition 8.11 - Fundamental Theorem of Riemann Integration.
Let F : [a, b] → R be a function. Then F is differentiable and F 0 is continuous on [a, b] if
and only if there is a continuous function f : [a, b] → R such that
Z x
F (x) = F (a) +
f (t)dt for all x ∈ [a, b].
a
In this case, we have F (x) = f (x) for all x ∈ [a, b].
0
111
Chapter 40
Definite Integrals & Improper
Integrals
112
Part XII
Linear Algebra
113
Chapter 41
Determinants
41.1
Introduction
41.2
Properties
1. |At | = |A|
2. |A| = 0 if:
(a) It has two equal lines.
(b) All elements of a line are zero.
(c) The elements of a line are a linear combination of the others.
3. A triangular determinant is the product of the diagonal elements.
4. If a determinant switches two parallel lines its determinant changes sign.
5. If the elements of a line are added to the elements of another parallel line previously
multiplied by a real number, the value of the determinant is unchanged.
6. If a determinant is multiplied by a real number, any line can be multiplied by the above
mentioned number, but only one.
7. If all the elements of a line or column are formed by two addends, the above mentioned
determinant decomposes in the sum of two determinants.
8. |A.B| = |A| . |B|.
1
.
9. If A is invertible, then A−1 =
|A|
10. Suppose if 2 rows of a square matrix "A" are the same, then |A| = 0.
11. |cA| = cn |A| for an n × n matrix.
12. A−1 =
adj(A)
.
|A|
1
x1
2
13. Vandermode determinant: x1
..
.
n−1
x
1
1
x2
x22
..
.
xn−1
2
114
1
x3
x23
..
.
xn−1
3
···
···
···
..
.
1
xn
x2n
..
.
···
xn−1
n
Q
= 1≤i<j≤n (xj − xi )
Chapter 41. Determinants
41.3. Determinants & Eigenvalues
x1
x2 x3 · · ·
xn
xn
x1 x2 · · · xn−1
xn−1 xn x1 · · · xn−2 Qn
14. Circulant Matrix:
= j=1 x1 + x2 ωj + x3 ωj2 + . . . + xn ωjn−1
..
..
.. . .
..
.
.
.
.
.
x2
x3 x4 · · ·
x1
where ωj is an nth root of 1.
15. |A| = AT = |−A| = (1)n |A|. Hence det(A) = 0 when n is odd.
41.3
Determinants & Eigenvalues
1. |A − xI| = 0.
2. A symmetric n × n real matrix M is said to be positive definite if z T M z is positive for
every non-zero column vector z of n real numbers. Here z T denotes the transpose of z.
3. The negative definite, positive semi-definite, and negative semi-definite matrices are defined in the same way, except that the expression z T M z or z ∗ M z is required to be always
negative, non-negative, and non-positive, respectively.
4. Eigenvalues of Hermitian Matrices( A = AT ) are always real.
5. For any real non-singular matrix A, the product AT A is a positive definite matrix.
6. All eigenvalues of positive definite matrix are positive.
7. Every positive definite matrix is invertible and its inverse is also positive definite.
8. If M is positive definite and r > 0 is a real number, then rM is positive definite. If M
and N are positive definite, then the sum M + N and the products M N M and N M N
are also positive definite. If M N = N M , then M N is also positive definite.(M &N are
square matrices.)
9. Every principal submatrix of a positive definite matrix is positive definite.
10. The trace tr(A) is by definition the sum of the diagonal entries of A and also equals the
sum of the eigenvalues.
11. tr(A) = log(|(exp(A))|).,
41.4
Eigenvectors & Eigenvalues
1. Eigenvectors with Distinct Eigenvalues are Linearly Independent.
2. Singular Matrices have Zero Eigenvalues. ie, eigenvalue = 0.
3. Suppose A is a square matrix and λ is an eigenvalue of A. Then αλ is an eigenvalue of
αA.
4. Suppose A is a square matrix, λ is an eigenvalue of A, and s ≥ 0 is an integer. Then λs
is an eigenvalue of As .
5. Suppose A is a square matrix and λ is an eigenvalue of A. Let q(x) be a polynomial in
the variable x. Then q(λ) is an eigenvalue of the matrix q(A).
6. Suppose A is a square nonsingular matrix and λ is an eigenvalue of A. Then λ−1 is an
eigenvalue of the matrix A−1 .
115
Chapter 41. Determinants
41.4. Eigenvectors & Eigenvalues
7. Suppose A is a square matrix and λ is an eigenvalue of A. Then λ is an eigenvalue of the
matrix At .
8. Suppose A is a square matrix with real entries and x is an eigenvector of A for the
¯
eigenvalue λ. Then x
¯ is an eigenvector of A for the eigenvalue λ.
9. Hermitian Matrices have Real Eigenvalues, orthogonal eigenvectors.
10. An eigenvalue λ has algebraic multiplicity l > 0 if det(A − λI) = 0.
11. Characteristic Polynomial: det(A − λI) = 0.
12. An n × n symmetric matrix has n orthogonal eigenvectors( X T Y = 0) for distinct eigenvalues.
13. Symmetric matrices only have real eigenvalues.
14. Geometric multiplicity γT (λ) of an eigenvalue λ is the dimension of the eigenspace
associated to λ, i.e. number of linearly independent eigenvectors with that eigenvalue.
15. Let A be an arbitrary n × n matrix of complex numbers with eigenvalues λ1 , λ2 , ...λn .
(a) Every eigenvalue of a unitary matrix has absolute value |λ| = 1.
(b) If A is invertible, then the eigenvalues of A−1 are 1/λ1 , 1/λ2 , . . . , 1/λn .
(c) The eigenvalues of the k th power of A, i.e. the eigenvalues of Ak , for any positive
integer k, are λk1 , λk2 , . . . , λkn with same eigenvectors.
(d) The matrix A is invertible if and only if all the eigenvalues λi are nonzero.
(e) The trace of A, defined
Pn as the sum
Pnof its diagonal elements, is also the sum of all
eigenvalues: tr(A) = i=1 Aii = i=1 λi = λ1 + λ2 + · · · + λn .
Qn
(f) The determinant of A is the product of all eigenvalues: det(A) = i=1 λi = λ1 λ2 · · · λn .
(g) New Item
16. The eigenvalues of a diagonal or triangular matrix are its diagonal elements.
17. An n × n matrix is invertible if and only if it doesn’t have 0 as an eigenvalue.
18. Row reductions don’t preserve eigenvalues . However, similar matrices have the same
characteristic polynomial, so theyhave the same eigenvalues with the same multiplicities.
19. A complete set of eigenvectors for An×n is any set of n linearly independent eigenvectors
for A.
20. A n×n is diagonalizable if and only if A possesses a complete set ofeigenvectors. Moreover,P 1 AP =
diag(λ1 , λ2 , . . . , λn ) if and only if the columns of P constitute a complete set of eigenvectors and the λj ’s are the associated eigenvalues.
21. Cayley Hamilton Theorem: Every square matrix satisfiesits own characteristic equation p(λ) = 0.That is, p(A) = 0.
22. If no eigenvalue of A is repeated, then A is diagonalizable. Converse is not true.
116
Chapter 41. Determinants
41.5
41.5. Cramer’s rule
Cramer’s rule
A linear system of m equations with n unknowns x1 , x2 , . . . , xn .
a11 x1 + a12 x2 + . . . + a1n xn = b1
a21 x1 + a22 x2 + . . . + a2n xn = b2
..
..
.
..
.
.+
. + .. +
. = ..
am1 x1 + am2 x2 + . . . + amn xn = bm
Solution:
A1
Ai
An
x1 =
, . . . xi =
. . ., xn =
where
A
A
A
a11 a12
a21 a22
Ai = .
..
..
.
am1 am2
...
...
b1
b2
..
.
...
. . . bn
a1n
a2n
..
...
.
. . . amn
...
...
where bi ’s are present in ith column.
41.6
Rank of a Matrix
1. The rank of a matrix is the number of pivots when in row echelon form. A pivot is the
first non zero entry in a row.
2. Rank of diagonal matrix is the no. of non-zero elements in the principal diagonal of the
matrix.
3. Rank of A (m × n) matrix is rank(A) ≤ (m, n).
4. A square matrix A of order n is invertible if rank(A) = n.
5. Rank(A) + nullity(A) = no. of columns in A.
6. Row equivalent matrices have same rank.
41.7
System of Linear Equations
A linear system of m equations with n unknowns x1 , x2 , . . . , xn .
a11 x1 + a12 x2 + . . . + a1n xn = b1
a21 x1 + a22 x2 + . . . + a2n xn = b2
..
..
.
..
.
.+
. + .. +
. = ..
am1 x1 + am2 x2 + . . . + amn xn = bm
˜
is consistent
if and only
if A and A
a11 . . . a1n
a11
a21 . . . a2n
a21
A= .
.. A˜ = ..
..
.
...
.
am1
...
amn
am1
have the same rank.
. . . a1n | b1
. . . a2n | b2
..
.
...
.
| ..
...
amn
| bm
117
Chapter 41. Determinants
41.7. System of Linear Equations
1. Unique Solution: If and only if common rank of A & A˜ is same and is equal to n.
˜
2. No Solution: rank(A) 6= rank(A)
3. Infinitely many Solution: If and only if common rank of A & A˜ is less than n.
4. For homogenous systems(all bi ’s are 0), there exists non-trivial solution if rank(A) < n.
5. Let Ax = b be a consistent system of equations with n variables. Then number of free
variables is equal to n − rank(A).
118
Check this part for
m, n comaprison
condition for no,
infintely many solutions. Also for
m = n.
Part XIII
Set Theory & Algebra
119
Chapter 42
Sets
120
Chapter 43
Relations
Definition 50 - Cartesian Product.
The Cartesian product of two sets A and B (also called the product set, set direct product, or
cross product) is defined to be the set of all points (a, b) where a ∈ A and b ∈ B. It is denoted
by A × B. Cartesian Product is not commutaitve ie., A × B 6= B × A.
Definition 51 - Relation.
A relation is any subset of a Cartesian product. R ◦ S = (x, z)|(x, y) ∈ S, (y, z) ∈ R.R ◦ S 6=
¯
S ◦ R.R ◦ (S ◦ T ) = (R ◦ S) ◦ T.R−1 6= R ⇒ RisSymmetric.R−1 6= R
Definition 52 - Reflexive Closure.
The reflexive closure S of a relation R on a set X is given by
S = R ∪ {(x, x) : x ∈ X}
Definition 53 - Symmetric Closure.
The symmetric closure S of a relation R on a set X is given by
S = R ∪ {(x, y) : (y, x) ∈ R} .
Definition 54 - Transitive Closure.
The transitive closure of R is then given by the intersection of all transitive relations containing R. Warshall Alorithm is used to find transitive closure.
R+ is representation for transitive closure.
[
R+ =
Ri .
i∈{1,2,3,...}
where Ri is the ith power of R, defined inductively by R1 = R and, for i > 0, Ri+1 = R ◦ Ri
Definition 55 - Reachability Relation.
Reachability refers to the ability to get from one vertex to another within a graph. Floyd
Warshall Algorithm used to find it.
R∞ = R+ ∪ I
. contains self loops. MR◦S = MS MR where is binary multiplication.
121
Chapter 43. Relations
43.1. Properties
Definition 56 - Reachability Matrix.
"
a11
R = .
..
k
a12
..
.
...
...
a1n
..
.
#
where a1n indicates ∃ a path of length k from 1 to n.
Theorem 9.
If R(Relation) is symmetric, transitive, reflexive, equivalence then R−1 is also symmetric, transitive, reflexive, equivalence.
Definition 57 - Binary Relation.
A relation on set A to set B. R ⊆ A1 × A2 .
43.1
Properties
1. Reflexive Relation ∀x ∈ S, xRx.
2. Symmetric Relation ∀x, y ∈ S, xRy → yRx.
3. Transitive Relation ∀x, y, z ∈ S, (xRy ∧ yRz) → xRz.
4. Equivalence Relation All of reflexive, symmetric & transitive relation.
5. If R and S are equivalence relations, then R ∪ S is also equivalence relation, not true for
R ∪ S.
43.2
Other Properties Names
1. Asymmetry ¬∃x, y ∈ S, xRy ∧ yRx
2. AntiSymmetric ∀x, y ∈ S, xRy ∧ yRx → x = y.
3. Irreflexive ¬∃x ∈ S, xRx.
122
Chapter 44
Functions
123
Chapter 45
Group
124
Chapter 46
Lattices
125
Chapter 47
Partial Orders
Definition 58 - Weak Partial Order.
A relation R on a set A is a weak partial order if it is transitive, antisymmetric, and reflexive.
Definition 59 - Strong Partial Order.
The relation is said to be a strong partial order if it is transitive, antisymmetric, and irreflexive.
Definition 60 - Total Order.
A total order is a partial order in which every pair of distinct elements is comparable. Comparable elements A, B ⇐⇒ A ≤ B ∪ B ≤ A.
Theorem 10.
A poset has no directed cycles other than self-loops. Partially ordered set is a digraph without
cycles (DAG).
Definition 61.
Given a digraph G = (V, E), the transitive closure of G is the digraph G+ = (V, E + ) where
E + = u → v | there is a directed path of positive length from u to v in G.
Definition 62 - Lattices.
A lattice is a partially ordered set in which every two elements have a supremum (also called a
least upper bound or join) and an infimum (also called a greatest lower bound or meet).
An example is given by the natural numbers, partially ordered by divisibility, for which the
supremum is the least common multiple and the infimum is the greatest common divisor.
126
Part XIV
Combinatory
127
Chapter 48
Generating Functions
Definition 63 - Generating functions.
Generating Function for the sequence hg0 , g1 , g2 , g3 , . . .i is the power series:
G(x) = g0 + g1 x + g2 x2 + g3 x3 + . . .
128
Chapter 49
Recurrence Relations
Determinate Order Recurrence Relations an = k1 an−1 + k2 an − 2 + k3 where k1 , k2 , k3
are constants and the relation is of 2nd order. Determinate Order Recurrence Relations
an = k1 a n2 + k2 where k1 , k2 are constants. an = k1 a2n−1 + k2 an − 2 + k2 Non-Linear Order
an = k1 an−1 + k2 an − 2 + k2 Linear Order
Example: an − 5an−1 + 6an−2 = 0 an = f (n) = xn . No. of constants → Order of relation.
Solution: an = c1 2n +c2 3n . c1 , c2 can be obtained by inital conditions given like a0 = 1, a1 = 2.
When roots are same an = c1 xn1 + c2 nxn2 + c3 n2 xn3 + . . ..
n
an = a n + k1 where k1 is a constant. n = rs .
= rs−1 . ars = ars−1 + k1 . Let bs = ars . Solve
r
r
for bs and then replace it with an .
For particular solution a = ah + ap where ap = d1 ap1 where d1 is a constant.
129
Part XV
C Programs for Algorithms I [6]
130
Chapter 50
Sorting
#include <stdio.h>
// A recursive binary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle itself
if (arr[mid] == x) return mid;
// If element is smaller than mid, then it can only be present
// in left subarray
if (arr[mid] > x) return binarySearch(arr, l, mid-1, x);
}
}
// Else the element can only be present in right subarray
return binarySearch(arr, mid+1, r, x);
// We reach here when element is not present in array
return -1;
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
131
Chapter 50. Sorting
}
return 0;
: printf("Element is present at index %d", result);
Listing 1: Binary Search in C (Recursive)
132
Chapter 50. Sorting
#include <stdio.h>
// A iterative binary search function. It returns location of x in
// given array arr[l..r] if present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r)
{
int m = l + (r-l)/2;
if (arr[m] == x) return m;
// Check if x is present at mid
if (arr[m] < x) l = m + 1; // If x greater, ignore left half
}
else r = m - 1; // If x is smaller, ignore left half
}
return -1; // if we reach here, then element was not present
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n-1, x);
(result == -1)? printf("Element is not present in array")
: printf("Element is present at index %d", result);
return 0;
}
Listing 2: Binary Search in C (Iterative)
133
Chapter 50. Sorting
// C program for insertion sort
#include <stdio.h>
#include <math.h>
/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
}
}
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
// A utility function ot print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = {12, 11, 13, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
}
return 0;
134
Chapter 50. Sorting
Listing 3: Insertion Sort in C
135
Chapter 50. Sorting
// C program for implementation of Bubble sort
#include <stdio.h>
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n; i++)
for (j = 0; j < n-i-1; j++) //Last i elements are already in place
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr)/sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Listing 4: Bubble Sort in C
136
Chapter 50. Sorting
/* C program for merge sort */
#include<stdlib.h>
#include<stdio.h>
/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[] */
void merge(int arr[], int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
int L[n1], R[n2];
/* Copy data to temp arrays L[] and R[] */
for(i = 0; i < n1; i++)
L[i] = arr[l + i];
for(j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
137
Chapter 50. Sorting
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
/* l is for left index and r is right index of the sub-array
of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
int m = l+(r-l)/2; //Same as (l+r)/2, but avoids overflow for large l and h
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
/* UITLITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
/* Driver program to test above functions */
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
}
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
138
Chapter 50. Sorting
Listing 5: Merge Sort in C
139
Chapter 50. Sorting
/* A typical recursive implementation of quick sort */
#include<stdio.h>
// A utility function to swap two elements
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
/* This function takes last element as pivot, places the pivot element at its
correct position in sorted array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right of pivot */
int partition (int arr[], int l, int h)
{
int x = arr[h];
// pivot
int i = (l - 1); // Index of smaller element
}
for (int j = l; j <= h- 1; j++)
{
// If current element is smaller than or equal to pivot
if (arr[j] <= x)
{
i++;
// increment index of smaller element
swap(&arr[i], &arr[j]); // Swap current element with index
}
}
swap(&arr[i + 1], &arr[h]);
return (i + 1);
/* arr[] --> Array to be sorted, l --> Starting index, h --> Ending index */
void quickSort(int arr[], int l, int h)
{
if (l < h)
{
int p = partition(arr, l, h); /* Partitioning index */
quickSort(arr, l, p - 1);
quickSort(arr, p + 1, h);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{
int i;
140
Chapter 50. Sorting
}
for (i=0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
// Driver program to test above functions
int main()
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
Listing 6: Quick Sort in C
141
Chapter 50. Sorting
// An iterative implementation of quick sort
#include <stdio.h>
int n;
// A utility function to print contents of arr
void printArr( int arr[], int n )
{
int i;
for ( i = 0; i < n; ++i )
printf( "%d ", arr[i] );
printf("\n");
}
// A utility function to swap two elements
void swap ( int* a, int* b )
{
int t = *a;
*a = *b;
*b = t;
}
/* This function is same in both iterative and recursive*/
int partition (int arr[], int l, int h)
{
int x = arr[h];
int i = (l - 1);
//printf("Pivot: %d, i = %d, h = %d\n", x, i, h);
for (int j = l; j <= h- 1; j++)
{
if (arr[j] <= x)
{
i++;
swap (&arr[i], &arr[j]);
}
//printf("Partition: i = %d, j = %d\n",i,j);
printArr( arr, n);
}
swap (&arr[i + 1], &arr[h]);
return (i + 1);
}
/* A[] --> Array to be sorted, l --> Starting index, h
void quickSortIterative (int arr[], int l, int h)
{
// Create an auxiliary stack
int stack[ h - l + 1 ];
142
--> Ending index */
Chapter 50. Sorting
// initialize top of stack
int top = -1;
// push initial values of l and h to stack
stack[ ++top ] = l;
stack[ ++top ] = h;
// Keep popping from stack while is not empty
while ( top >= 0 )
{
// Pop h and l
h = stack[ top-- ];
l = stack[ top-- ];
// Set pivot element at its correct position in sorted array
int p = partition( arr, l, h );
//printf("After Partition:\n");
printArr( arr, n);
// If there are elements on left side of pivot, then push left
// side to stack
if ( p-1 > l )
{
stack[ ++top ] = l;
stack[ ++top ] = p - 1;
}
}
}
// If there are elements on right side of pivot, then push right
// side to stack
if ( p+1 < h )
{
stack[ ++top ] = p + 1;
stack[ ++top ] = h;
}
// Driver program to test above
int main()
{
int arr[] = {4, 3, 5, 2, 1,
n = sizeof( arr ) / sizeof(
quickSortIterative( arr, 0,
printf("\n");
printArr( arr, n );
return 0;
}
functions
3, 2, 3};
*arr );
n - 1 );
143
Chapter 50. Sorting
Listing 7: Quick Sort in C (Iterative)
144
Chapter 50. Sorting
// C implementation of Heap Sort
#include <stdio.h>
#include <stdlib.h>
// A heap has current size and array of elements
struct MaxHeap
{
int size;
int* array;
};
// A utility function to swap to integers
void swap(int* a, int* b) { int t = *a; *a = *b;
*b = t; }
// The main function to heapify a Max Heap. The function assumes that
// everything under given root (element at index idx) is already heapified
void maxHeapify(struct MaxHeap* maxHeap, int idx)
{
int largest = idx; // Initialize largest as root
int left = (idx << 1) + 1; // left = 2*idx + 1
int right = (idx + 1) << 1; // right = 2*idx + 2
// See if left child of root exists and is greater than root
if (left < maxHeap->size && maxHeap->array[left] > maxHeap->array[largest])
largest = left;
// See if right child of root exists and is greater than the largest so far
if (right < maxHeap->size && maxHeap->array[right] > maxHeap->array[largest])
largest = right;
}
// Change root, if needed
if (largest != idx)
{
swap(&maxHeap->array[largest], &maxHeap->array[idx]);
maxHeapify(maxHeap, largest);
}
// A utility function to create a max heap of given capacity
struct MaxHeap* createAndBuildHeap(int *array, int size)
{
int i;
struct MaxHeap* maxHeap = (struct MaxHeap*) malloc(sizeof(struct MaxHeap));
maxHeap->size = size;
// initialize size of heap
maxHeap->array = array; // Assign address of first element of array
// Start from bottommost and rightmost internal mode and heapify all
145
Chapter 50. Sorting
}
// internal modes in bottom up way
for (i = (maxHeap->size - 2) / 2; i >= 0; --i){
printf("\nHeapifying at index %d\n",i);
maxHeapify(maxHeap, i);
}
return maxHeap;
// The main function to sort an array of given size
void heapSort(int* array, int size)
{
// Build a heap from the input data.
struct MaxHeap* maxHeap = createAndBuildHeap(array, size);
// Repeat following steps while heap size is greater than 1. The last
// element in max heap will be the minimum element
while (maxHeap->size > 1)
{
// The largest item in Heap is stored at the root. Replace it with the
// last item of the heap followed by reducing the size of heap by 1.
swap(&maxHeap->array[0], &maxHeap->array[maxHeap->size - 1]);
--maxHeap->size; // Reduce heap size
}
}
// Finally, heapify the root of tree.
maxHeapify(maxHeap, 0);
// A utility function to print a given array of given size
void printArray(int* arr, int size)
{
int i;
for (i = 0; i < size; ++i)
printf("%d ", arr[i]);
}
/* Driver program to test above functions */
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7, 20, 1, 10};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, size);
heapSort(arr, size);
printf("\nSorted array is \n");
146
Chapter 50. Sorting
}
printArray(arr, size);
return 0;
Listing 8: Heap Sort in C
147
Chapter 50. Sorting
// C++ program to sort an array using bucket sort
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
// Function to sort arr[] of size n using bucket sort
void bucketSort(float arr[], int n)
{
// 1) Create n empty buckets
vector<float> b[n];
// 2) Put array elements in different buckets
for (int i=0; i<n; i++)
{
int bi = n*arr[i]; // Index in bucket
b[bi].push_back(arr[i]);
}
// 3) Sort individual buckets
for (int i=0; i<n; i++)
sort(b[i].begin(), b[i].end());
}
// 4) Concatenate all buckets into arr[]
int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i].size(); j++)
arr[index++] = b[i][j];
/* Driver program to test above funtion */
int main()
{
float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434};
int n = sizeof(arr)/sizeof(arr[0]);
bucketSort(arr, n);
}
cout << "Sorted array is \n";
for (int i=0; i<n; i++)
cout << arr[i] << " ";
return 0;
Listing 9: Bucket Sort in C++
148
Chapter 51
Spanning Trees
// Kruskal’s algortihm to find Minimum Spanning Tree of a given connected,
// undirected and weighted graph
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// a structure to represent a weighted edge in graph
struct Edge
{
int src, dest, weight;
};
// a structure to represent a connected, undirected and weighted graph
struct Graph
{
// V-> Number of vertices, E-> Number of edges
int V, E;
};
// graph is represented as an array of edges. Since the graph is
// undirected, the edge from src to dest is also edge from dest
// to src. Both are counted as 1 edge here.
struct Edge* edge;
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );
149
Chapter 51. Spanning Trees
}
return graph;
// A structure to represent a subset for union-find
struct subset
{
int parent;
int rank;
};
// A utility function to find set of an element i
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
// find root and make root as parent of i (path compression)
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
// A function that does union of two sets of x and y
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
int xroot = find(subsets, x);
int yroot = find(subsets, y);
// Attach smaller rank tree under root of high rank tree
// (Union by Rank)
if (subsets[xroot].rank < subsets[yroot].rank)
subsets[xroot].parent = yroot;
else if (subsets[xroot].rank > subsets[yroot].rank)
subsets[yroot].parent = xroot;
}
// If ranks are same, then make one as root and increment
// its rank by one
else
{
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
// Compare two edges according to their weights.
// Used in qsort() for sorting an array of edges
int myComp(const void* a, const void* b)
150
Chapter 51. Spanning Trees
{
}
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;
return a1->weight > b1->weight;
// The main function to construct MST using Kruskal’s algorithm
void KruskalMST(struct Graph* graph)
{
int V = graph->V;
struct Edge result[V]; // Tnis will store the resultant MST
int e = 0; // An index variable, used for result[]
int i = 0; // An index variable, used for sorted edges
// Step 1: Sort all the edges in non-decreasing order of their weight
// If we are not allowed to change the given graph, we can create a copy of
// array of edges
qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
// Allocate memory for creating V ssubsets
struct subset *subsets =
(struct subset*) malloc( V * sizeof(struct subset) );
// Create V subsets with single elements
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Number of edges to be taken is equal to V-1
while (e < V - 1)
{
// Step 2: Pick the smallest edge. And increment the index
// for next iteration
struct Edge next_edge = graph->edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
// If including this edge does’t cause cycle, include it
// in result and increment the index of result for next edge
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
// Else discard the next_edge
151
Chapter 51. Spanning Trees
}
// print the contents of result[] to display the built MST
printf("Following are the edges in the constructed MST\n");
for (i = 0; i < e; ++i)
printf("%d -- %d == %d\n", result[i].src, result[i].dest,
result[i].weight);
return;
}
// Driver program to test above functions
int main()
{
/* Let us create following weighted graph
10
0--------1
| \
|
6| 5\
|15
|
\ |
2--------3
4
*/
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
// add edge 0-1
graph->edge[0].src = 0;
graph->edge[0].dest = 1;
graph->edge[0].weight = 10;
// add edge 0-2
graph->edge[1].src = 0;
graph->edge[1].dest = 2;
graph->edge[1].weight = 6;
// add edge 0-3
graph->edge[2].src = 0;
graph->edge[2].dest = 3;
graph->edge[2].weight = 5;
// add edge 1-3
graph->edge[3].src = 1;
graph->edge[3].dest = 3;
graph->edge[3].weight = 15;
// add edge 2-3
graph->edge[4].src = 2;
152
Chapter 51. Spanning Trees
graph->edge[4].dest = 3;
graph->edge[4].weight = 4;
KruskalMST(graph);
}
return 0;
Listing 10: Kruskal MST in C
153
Chapter 52
Dynamic Programming
#include<stdio.h>
/* simple recursive program for Fibonacci numbers */
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
int main(){
printf("Fibonacci of 4 is %d", fib(4));
return 0;
}
Listing 11: Fibonacci Numbers in C
154
Chapter 52. Dynamic Programming
/* Memoized version for nth Fibonacci number */
#include<stdio.h>
#define NIL -1
#define MAX 100
int lookup[MAX];
/* Function to initialize NIL values in lookup table */
void _initialize()
{
int i;
for (i = 0; i < MAX; i++)
lookup[i] = NIL;
}
/* function for
int fib(int n)
{
if(lookup[n]
{
if ( n <= 1
lookup[n]
else
lookup[n]
}
}
nth Fibonacci number */
== NIL)
)
= n;
= fib(n-1) + fib(n-2);
return lookup[n];
int main ()
{
int n = 40;
_initialize();
printf("Fibonacci number is %d ", fib(n));
getchar();
retur
Listing 12: Fibonacci Numbers in C(Memoization)
155
Chapter 52. Dynamic Programming
/* tabulated version */
#include<stdio.h>
int fib(int n)
{
int f[n+1];
int i;
f[0] = 0; f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = f[i-1] + f[i-2];
}
return f[n];
int main ()
{
int n = 9;
printf("Fibonacci number is %d ", fib(n));
getchar();
return 0;
}
Listing 13: Fibonacci Numbers in C(Tabulation)
156
Chapter 52. Dynamic Programming
# include<stdio.h>
# include<stdlib.h>
/*This function divides a by greatest divisible
power of b*/
int maxDivide(int a, int b)
{
while (a%b == 0)
a = a/b;
return a;
}
/* Function to check
int isUgly(int no)
{
no = maxDivide(no,
no = maxDivide(no,
no = maxDivide(no,
}
if a number is ugly or not */
2);
3);
5);
return (no == 1)? 1 : 0;
/* Function to get the nth ugly number*/
int getNthUglyNo(int n)
{
int i = 1;
int count = 1;
/* ugly number count */
}
/*Check for all integers untill ugly count
becomes n*/
while (n > count)
{
i++;
if (isUgly(i))
count++;
}
return i;
/* Driver program to test above functions */
int main()
{
unsigned no = getNthUglyNo(150);
printf("150th ugly no. is %d ", no);
getchar();
return 0;
}
157
Chapter 52. Dynamic Programming
Listing 14: Ugly Numbers Numbers in C
158
Chapter 52. Dynamic Programming
# include<stdio.h>
# include<stdlib.h>
# define bool int
/* Function to find minimum of 3 numbers */
unsigned min(unsigned , unsigned , unsigned );
/* Function to get the nth ugly number*/
unsigned getNthUglyNo(unsigned n)
{
unsigned *ugly =
(unsigned *)(malloc (sizeof(unsigned)*n));
unsigned i2 = 0, i3 = 0, i5 = 0;
unsigned i;
unsigned next_multiple_of_2 = 2;
unsigned next_multiple_of_3 = 3;
unsigned next_multiple_of_5 = 5;
unsigned next_ugly_no = 1;
*(ugly+0) = 1;
}
for(i=1; i<n; i++)
{
next_ugly_no = min(next_multiple_of_2,
next_multiple_of_3,
next_multiple_of_5);
*(ugly+i) = next_ugly_no;
if(next_ugly_no == next_multiple_of_2)
{
i2 = i2+1;
next_multiple_of_2 = *(ugly+i2)*2;
}
if(next_ugly_no == next_multiple_of_3)
{
i3 = i3+1;
next_multiple_of_3 = *(ugly+i3)*3;
}
if(next_ugly_no == next_multiple_of_5)
{
i5 = i5+1;
next_multiple_of_5 = *(ugly+i5)*5;
}
} /*End of for loop (i=1; i<n; i++) */
return next_ugly_no;
/* Function to find minimum of 3 numbers */
unsigned min(unsigned a, unsigned b, unsigned c)
159
Chapter 52. Dynamic Programming
{
}
if(a <= b)
{
if(a <= c)
return a;
else
return c;
}
if(b <= c)
return b;
else
return c;
/* Driver program to test above functions */
int main()
{
unsigned no = getNthUglyNo(150);
printf("%dth ugly no. is %d ", 150, no);
getchar();
return 0;
}
Listing 15: Ugly Numbers in C(Dynamic Programming)
160
Chapter 52. Dynamic Programming
/* A Naive recursive implementation of LIS problem */
#include<stdio.h>
#include<stdlib.h>
/* To make use of recursive calls, this function must return two things:
1) Length of LIS ending with element arr[n-1]. We use max_ending_here
for this purpose
2) Overall maximum as the LIS may end with an element before arr[n-1]
max_ref is used this purpose.
The value of LIS of full array of size n is stored in *max_ref which is our final result
*/
int _lis( int arr[], int n, int *max_ref)
{
/* Base case */
if(n == 1)
return 1;
int res, max_ending_here = 1; // length of LIS ending with arr[n-1]
/* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If
arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs
to be updated, then update it */
for(int i = 1; i < n; i++)
{
res = _lis(arr, i, max_ref);
if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
max_ending_here = res + 1;
}
// Compare max_ending_here with the overall max. And update the
// overall max if needed
if (*max_ref < max_ending_here)
*max_ref = max_ending_here;
}
// Return length of LIS ending with arr[n-1]
return max_ending_here;
// The wrapper function for _lis()
int lis(int arr[], int n)
{
// The max variable holds the result
int max = 1;
// The function _lis() stores its result in max
_lis( arr, n, &max );
161
Chapter 52. Dynamic Programming
}
// returns max
return max;
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of LIS is %d\n", lis( arr, n ));
getchar();
return 0;
}
Listing 16: Longest Increasing Subsequence in C
162
Chapter 52. Dynamic Programming
/* Dynamic Programming implementation of LIS problem */
#include<stdio.h>
#include<stdlib.h>
/* lis() returns the length of the longest increasing subsequence in
arr[] of size n */
int lis( int arr[], int n )
{
int *lis, i, j, max = 0;
lis = (int*) malloc ( sizeof( int ) * n );
/* Initialize LIS values for all indexes */
for ( i = 0; i < n; i++ )
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
/* Pick maximum of all LIS values */
for ( i = 0; i < n; i++ )
if ( max < lis[i] )
max = lis[i];
/* Free memory to avoid memory leak */
free( lis );
}
return max;
/* Driver program to test above function */
int main()
{
int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int n = sizeof(arr)/sizeof(arr[0]);
printf("Length of LIS is %d\n", lis( arr, n ) );
}
getchar();
return 0;
Listing 17: Longest Increasing Subsequence in C(Dynamic Programming)
163
Chapter 52. Dynamic Programming
/* A Naive recursive implementation of LCS problem */
#include<stdio.h>
#include<stdlib.h>
int max(int a, int b);
/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
int lcs( char *X, char *Y, int m, int n )
{
if (m == 0 || n == 0)
return 0;
if (X[m-1] == Y[n-1])
return 1 + lcs(X, Y, m-1, n-1);
else
return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n));
}
/* Utility function to get max of 2 integers */
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Driver program to test above function */
int main()
{
char X[] = "AGGTAB";
char Y[] = "GXTXAYB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d\n", lcs( X, Y, m, n ) );
}
getchar();
return 0;
Listing 18: Longest Common Subsequence in C
164
Chapter 52. Dynamic Programming
Listing 19: Longest Common Subsequence in C(Dynamic Programming)
165
Chapter 52. Dynamic Programming
// Dynamic Programming implementation of edit distance
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
// Change these strings to test the program
#define STRING_X "SUNDAY"
#define STRING_Y "SATURDAY"
#define SENTINEL (-1)
#define EDIT_COST (1)
#define MIN(a, b) a>b?a:b
inline
int min(int a, int b) {
return a < b ? a : b;
}
// Returns Minimum among a, b, c
int Minimum(int a, int b, int c)
{
return MIN(MIN(a, b), c);
}
// Strings of size m and n are passed.
// Construct the Table for X[0...m, m+1], Y[0...n, n+1]
int EditDistanceDP(char X[], char Y[])
{
// Cost of alignment
int cost = 0;
int leftCell, topCell, cornerCell;
int m = strlen(X)+1;
int n = strlen(Y)+1;
// T[m][n]
int *T = (int *)malloc(m * n * sizeof(int));
// Initialize table
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
*(T + i * n + j) = SENTINEL;
// Set up base cases
// T[i][0] = i
for(int i = 0; i < m; i++)
*(T + i * n) = i;
166
Chapter 52. Dynamic Programming
// T[0][j] = j
for(int j = 0; j < n; j++)
*(T + j) = j;
// Build the T in top-down fashion
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
{
// T[i][j-1]
leftCell = *(T + i*n + j-1);
leftCell += EDIT_COST; // deletion
// T[i-1][j]
topCell = *(T + (i-1)*n + j);
topCell += EDIT_COST; // insertion
// Top-left (corner) cell
// T[i-1][j-1]
cornerCell = *(T + (i-1)*n + (j-1) );
// edit[(i-1), (j-1)] = 0 if X[i] == Y[j], 1 otherwise
cornerCell += (X[i-1] != Y[j-1]); // may be replace
}
}
}
// Minimum cost of current cell
// Fill in the next cell T[i][j]
*(T + (i)*n + (j)) = Minimum(leftCell, topCell, cornerCell);
// Cost is in the cell T[m][n]
cost = *(T + m*n - 1);
free(T);
return cost;
// Recursive implementation
int EditDistanceRecursion( char *X, char *Y, int m, int n )
{
// Base cases
if( m == 0 && n == 0 )
return 0;
if( m == 0 )
return n;
if( n == 0 )
167
Chapter 52. Dynamic Programming
return m;
// Recurse
int left = EditDistanceRecursion(X, Y, m-1, n) + 1;
int right = EditDistanceRecursion(X, Y, m, n-1) + 1;
int corner = EditDistanceRecursion(X, Y, m-1, n-1) + (X[m-1] != Y[n-1]);
}
return Minimum(left, right, corner);
int main()
{
char X[] = STRING_X; // vertical
char Y[] = STRING_Y; // horizontal
printf("Minimum edits required to convert %s into %s is %d\n",
X, Y, EditDistanceDP(X, Y) );
printf("Minimum edits required to convert %s into %s is %d by recursion\n",
X, Y, EditDistanceRecursion(X, Y, strlen(X), strlen(Y)));
}
return 0;
Listing 20: Edit Distance in C
168
Part XVI
C Programs for Testing
169
#include<stdio.h>
int main(){
if(sizeof(int) > -1){
printf("True");
}
else{
printf("False");
}
return 0;
}
Output:
Reason:
False
sizeof returns size_t which is unsigned int. When we compare int and unsigned int is converted
to unsigned and comparison takes place between two unsigned values. Thus any unsigned positive
int value will compare less with any negative signed value, if its MSB is 0.
#include <stdio.h>
int main(int argc, char const *argv[])
{
int x = 5;
if (5 == x)
{
printf("True\n");
}
else{
printf("False\n");
}
return 0;
}
Output:
Reason:
True
x == 5 and 5 == x both work.
170
#include <stdio.h>
int main()
{
float x = 1.1;
while( x == 1.1 )
{
printf("%f\n",x);
x=x-0.1;
}
return 0;
}
Output:
Reason:
No Output
1.1 is a double value. To have output replace 1.1 with 1.1f in line 6. 1.1 is default treated as
double.
171
#include <stdio.h>
int staticFn() {
static int x = 0;
x++;
return x;
}
int autoFn() {
auto int x = 0;
x++;
return x;
}
int registerFn() {
register int x = 0;
x++;
return x;
}
int main(void) {
int j;
for (j = 0; j <
printf("Value
}
for (j = 0; j <
printf("Value
}
for (j = 0; j <
printf("Value
}
return 0;
}
Output:
Reason:
5; j++) {
of autoFn(): %d\n", autoFn());
5; j++) {
of registerFn(): %d\n", registerFn());
5; j++) {
of staticFn(): %d\n", staticFn());
Value of auto(): 1 Value of auto(): 1 Value of auto(): 1 Value of auto(): 1 Value of auto(): 1 Value
of register(): 1 Value of register(): 1 Value of register(): 1 Value of register(): 1 Value of register():
1 Value of static(): 1 Value of static(): 2 Value of static(): 3 Value of static(): 4 Value of static():
5
sizeof returns size_t which is unsigned int. When we compare int and unsigned int is converted
to unsigned and comparison takes place between two unsigned values. Thus any unsigned positive
int value will compare less with any negative signed value, if its MSB is 0.
172
Bibliography
[1] Interpolation search. http://en.wikipedia.org/wiki/Interpolation_search.
[2] Jeffrey D Ullman. Introduction to automata theory, languages, and computation. Addison
Wesley Publishing Company, USA., ISBN, 10:020102988X, 1979.
[3] David A Patterson and John L Hennessy. Computer organization and design: the hardware/software interface. Newnes, 2013.
[4] Fundamentals of algorithms.
exh&src=73.
http://webmuseum.mi.fh-offenburg.de/index.php?view=
[5] Selective repeat go back n. http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/.
[6] Fundamentals
of
algorithms.
fundamentals-of-algorithms/.
http://www.geeksforgeeks.org/
173
Index
positive, 3
174
</div>
</div>
</div>
<!-- End Description Section -->
</main>
<!-- ========== END MAIN ========== -->
<div id="embedModal" class="js-login-window u-modal-window u-modal-window--embed">
<button class="btn btn-xs u-btn--icon u-btn-text-secondary u-modal-window__close" type="button"
onclick="Custombox.modal.close();">
<span class="fas fa-times"></span>
</button>
<form class="p-7">
<header class="text-center mb-7">
<h4 class="h4 mb-0">Embed!</h4>
<p>Computer </p>
</header>
<textarea class="form-control u-form__input" rows="5"></textarea>
</form>
</div>
<script>
function check_recatpcha(token) {
document.getElementById("download-form").submit();
grecaptcha.reset();
}
</script>
<script src='https://www.google.com/recaptcha/api.js'></script>
<!-- ========== FOOTER ========== -->
<footer class="bg-dark">
<div class="container space-2">
<div class="row justify-content-md-between">
<div class="col-6 col-md-3 col-lg-2 order-lg-3 mb-7 mb-lg-0">
<h3 class="h6 text-white mb-3">About</h3>
<!-- List Group -->
<div class="list-group list-group-flush list-group-transparent">
<a class="list-group-item list-group-item-action"
href="https://documento.mx/about">About us</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/terms">Terms and conditions</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/privacy">Privacy policy</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/sitemap">Sitemap</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/career">Career</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/contact">Contact us</a>
</div>
<!-- End List Group -->
</div>
<div class="col-6 col-md-3 col-lg-2 order-lg-4 mb-7 mb-lg-0">
<h3 class="h6 text-white mb-3">Help and support</h3>
<!-- List Group -->
<div class="list-group list-group-flush list-group-transparent">
<a class="list-group-item list-group-item-action"
href="https://documento.mx/help">Help</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/ticket">Submit ticket</a>
</div>
<!-- End List Group -->
</div>
<div class="col-6 col-md-3 col-lg-2 order-lg-5 mb-7 mb-lg-0">
<h3 class="h6 text-white mb-3">Account</h3>
<!-- List Group -->
<div class="list-group list-group-flush list-group-transparent">
<a class="list-group-item list-group-item-action"
href="https://documento.mx/profile">Profile</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/login">Login</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/register">Register</a>
<a class="list-group-item list-group-item-action"
href="https://documento.mx/forgot">Forgot password</a>
</div>
<!-- End List Group -->
</div>
<div class="col-6 col-md-3 col-lg-2 order-lg-6 mb-7 mb-lg-0">
<h3 class="h6 text-white mb-3">Social</h3>
<!-- List -->
<div class="list-group list-group-flush list-group-transparent">
<a class="list-group-item list-group-item-action" href="https://facebook.com/documento">
<span class="fab fa-facebook-f min-width-3 text-center mr-2"></span>
Facebook
</a>
<a class="list-group-item list-group-item-action" href="https://twitter.com/documento">
<span class="fab fa-twitter min-width-3 text-center mr-2"></span>
Twitter
</a>
</div>
<!-- End List -->
</div>
<div class="col-lg-4 order-lg-1 d-flex align-items-start flex-column">
<!-- Logo -->
<a class="d-inline-block mb-5" href="index.html" aria-label="Space">
<img src="https://documento.mx/assets/img/logo-white.png" alt="Logo"
style="width: 200px; max-width: 100%;">
</a>
<!-- End Logo -->
<!-- Language -->
<div class="btn-group d-block position-relative mb-4 mb-lg-auto">
<a id="footerLanguageInvoker"
class="btn-text-secondary d-flex align-items-center u-unfold--language-btn rounded py-2 px-3"
href="javascript:;" role="button"
aria-controls="footerLanguage"
aria-haspopup="true"
aria-expanded="false"
data-unfold-event="click"
data-unfold-target="#footerLanguage"
data-unfold-type="css-animation"
data-unfold-duration="300"
data-unfold-delay="300"
data-unfold-hide-on-scroll="false"
data-unfold-animation-in="slideInUp"
data-unfold-animation-out="fadeOut">
<span class="font-size-14">English</span>
<span class="fa fa-angle-down u-unfold__icon-pointer u-unfold--language-icon-pointer ml-4"></span>
</a>
<!-- Content -->
<div id="footerLanguage" class="u-unfold u-unfold--language bottom-0 left-0"
aria-labelledby="footerLanguageInvoker">
<div class="py-6 px-5">
<h4 class="h6 mb-4">Select your language</h4>
<div class="row">
<div class="col-6">
<!-- List of Languages -->
<div class="list-group list-group-borderless list-group-flush">
<a class="active d-flex align-items-center list-group-item list-group-item-action"
href="#">
<img class="max-width-3 mr-2"
src="../../assets/vendor/flag-icon-css/flags/4x3/us.svg"
alt="United States Flag">
English
</a>
<a class="d-flex align-items-center list-group-item list-group-item-action"
href="#">
<img class="max-width-3 mr-2"
src="../../assets/vendor/flag-icon-css/flags/4x3/fr.svg"
alt="France Flag">
Français
</a>
<a class="d-flex align-items-center list-group-item list-group-item-action"
href="#">
<img class="max-width-3 mr-2"
src="../../assets/vendor/flag-icon-css/flags/4x3/de.svg"
alt="Germany Flag">
Deutsch
</a>
<a class="d-flex align-items-center list-group-item list-group-item-action"
href="#">
<img class="max-width-3 mr-2"
src="../../assets/vendor/flag-icon-css/flags/4x3/pt.svg"
alt="Portugal Flag">
Português
</a>
</div>
<!-- End List of Languages -->
</div>
<div class="col-6">
<!-- List of Languages -->
<div class="list-group list-group-borderless list-group-flush">
<a class="d-flex align-items-center list-group-item list-group-item-action"
href="#">
<img class="max-width-3 mr-2"
src="../../assets/vendor/flag-icon-css/flags/4x3/es.svg"
alt="Spain Flag">
Español
</a>
<a class="d-flex align-items-center list-group-item list-group-item-action"
href="#">
<img class="max-width-3 mr-2"
src="../../assets/vendor/flag-icon-css/flags/4x3/it.svg"
alt="Italy Flag">
Italiano
</a>
<a class="d-flex align-items-center list-group-item list-group-item-action"
href="#">
<img class="max-width-3 mr-2"
src="../../assets/vendor/flag-icon-css/flags/4x3/ru.svg"
alt="Russian Flag">
Русский
</a>
<a class="d-flex align-items-center list-group-item list-group-item-action"
href="#">
<img class="max-width-3 mr-2"
src="../../assets/vendor/flag-icon-css/flags/4x3/tr.svg"
alt="Turkey Flag">
Türkçe
</a>
</div>
<!-- End List of Languages -->
</div>
</div>
</div>
<!-- Signup -->
<a class="u-unfold--language__link p-5" href="../pages/signup-simple.html">
<small class="d-block text-muted mb-1">More languages coming soon.</small>
<small class="d-block">Signup to get notified <span
class="fa fa-arrow-right u-unfold__icon-pointer"></span></small>
</a>
<!-- End Signup -->
</div>
<!-- End Content -->
</div>
<!-- End Language -->
<p class="small text-muted">Copyright © 2015-2024.</p>
</div>
</div>
</div>
</footer>
<!-- ========== END FOOTER ========== -->
<!-- Signup Modal Window -->
<div id="signupModal" class="js-signup-modal u-modal-window" style="width: 500px;">
<!-- Modal Close Button -->
<button class="btn btn-sm btn-icon btn-text-secondary u-modal-window__close" type="button"
onclick="Custombox.modal.close();">
<span class="fas fa-times"></span>
</button>
<!-- End Modal Close Button -->
<!-- Content -->
<div class="p-5">
<!-- Signin -->
<div id="signin" data-target-group="idForm">
<form method="post" action="https://documento.mx/login">
<!-- Title -->
<header class="text-center mb-5">
<h2 class="h4 mb-0">Please sign in</h2>
<p>Sign in to manage your account.</p>
</header>
<!-- End Title -->
<!-- Input -->
<div class="js-form-message mb-3">
<div class="js-focus-state input-group form">
<div class="input-group-prepend form__prepend">
<span class="input-group-text form__text">
<span class="fa fa-user form__text-inner"></span>
</span>
</div>
<input type="email" class="form-control form__input" name="email" required
placeholder="Email address"
aria-label="Email address"
data-msg="Please enter a valid email address"
data-error-class="u-has-error"
data-success-class="u-has-success">
</div>
</div>
<!-- End Input -->
<!-- Input -->
<div class="js-form-message mb-3">
<div class="js-focus-state input-group form">
<div class="input-group-prepend form__prepend">
<span class="input-group-text form__text">
<span class="fa fa-lock form__text-inner"></span>
</span>
</div>
<input type="password" class="form-control form__input" name="password" required
placeholder="Password"
aria-label="Password"
data-msg="Your password is invalid please try again"
data-error-class="u-has-error"
data-success-class="u-has-success">
</div>
</div>
<!-- End Input -->
<div class="row mb-3">
<div class="col-6">
<!-- Checkbox -->
<div class="custom-control custom-checkbox d-flex align-items-center text-muted">
<input type="checkbox" class="custom-control-input" id="rememberMeCheckbox">
<label class="custom-control-label" for="rememberMeCheckbox">
Remember me </label>
</div>
<!-- End Checkbox -->
</div>
<div class="col-6 text-right">
<a class="js-animation-link float-right" href="javascript:;"
data-target="#forgotPassword"
data-link-group="idForm"
data-animation-in="fadeIn">Forgot password</a>
</div>
</div>
<div class="mb-3">
<button type="submit" class="btn btn-block btn-primary">Login</button>
</div>
</form>
<div class="text-center mb-3">
<p class="text-muted">
Do not have an account? <a class="js-animation-link" href="javascript:;"
data-target="#signup"
data-link-group="idForm"
data-animation-in="fadeIn">Register </a>
</p>
</div>
<!-- Divider -->
<div class="text-center u-divider-wrapper my-3">
<span class="u-divider u-divider--xs u-divider--text">Or</span>
</div>
<!-- End Divider -->
<!-- Signin Social Buttons -->
<div class="row mx-gutters-2 mb-4">
<div class="col-sm-6 mb-2 mb-sm-0">
<a href="https://documento.mx/login/facebook" class="btn btn-block btn-facebook">
<span class="fab fa-facebook-f mr-2"></span>
Sign in with Facebook
</a>
</div>
<!-- <div class="col-sm-6">-->
<!-- <a href="--><!--" class="btn btn-block btn-google">-->
<!-- <span class="fab fa-google mr-2"></span>-->
<!-- --><!-- Google-->
<!-- </a>-->
<!-- </div>-->
</div>
<!-- End Signin Social Buttons -->
</div>
<!-- End Signin -->
<!-- Signup -->
<div id="signup" style="display: none; opacity: 0;" data-target-group="idForm">
<form method="post" action="https://documento.mx/register">
<!-- Title -->
<header class="text-center mb-5">
<h2 class="h4 mb-0">Please sign up</h2>
<p>Fill out the form to get started</p>
</header>
<!-- End Title -->
<!-- Input -->
<div class="js-form-message mb-3">
<div class="js-focus-state input-group form">
<div class="input-group-prepend form__prepend">
<span class="input-group-text form__text">
<span class="fa fa-user form__text-inner"></span>
</span>
</div>
<input type="email" class="form-control form__input" name="email" required
placeholder="Email address"
aria-label="Email address"
data-msg="Please enter a valid email address"
data-error-class="u-has-error"
data-success-class="u-has-success">
</div>
</div>
<!-- End Input -->
<!-- Input -->
<div class="js-form-message mb-3">
<div class="js-focus-state input-group form">
<div class="input-group-prepend form__prepend">
<span class="input-group-text form__text">
<span class="fa fa-lock form__text-inner"></span>
</span>
</div>
<input type="password" class="form-control form__input" name="password" required
placeholder="Password"
aria-label="Password"
data-msg="Your password is invalid please try again"
data-error-class="u-has-error"
data-success-class="u-has-success">
</div>
</div>
<!-- End Input -->
<!-- Input -->
<div class="js-form-message mb-3">
<div class="js-focus-state input-group form">
<div class="input-group-prepend form__prepend">
<span class="input-group-text form__text">
<span class="fa fa-key form__text-inner"></span>
</span>
</div>
<input type="password" class="form-control form__input" name="confirmPassword" required
placeholder="Confirm password"
aria-label="Confirm password"
data-msg="Password does not match with confirm password"
data-error-class="u-has-error"
data-success-class="u-has-success">
</div>
</div>
<!-- End Input -->
<div class="mb-3">
<button type="submit" class="btn btn-block btn-primary">Register</button>
</div>
</form>
<div class="text-center mb-3">
<p class="text-muted">
Have an account? <a class="js-animation-link" href="javascript:;"
data-target="#signin"
data-link-group="idForm"
data-animation-in="fadeIn">Login </a>
</p>
</div>
<!-- Divider -->
<div class="text-center u-divider-wrapper my-3">
<span class="u-divider u-divider--xs u-divider--text">Or</span>
</div>
<!-- End Divider -->
<!-- Signup Social Buttons -->
<div class="row mx-gutters-2 mb-4">
<div class="col-sm-6 mb-2 mb-sm-0">
<a href="https://documento.mx/login/facebook" class="btn btn-block btn-facebook">
<span class="fab fa-facebook-f mr-2"></span>
Sign in with Facebook
</a>
</div>
<!-- <div class="col-sm-6">-->
<!-- <a href="--><!--" class="btn btn-block btn-google">-->
<!-- <span class="fab fa-google mr-2"></span>-->
<!-- --><!-- Google-->
<!-- </a>-->
<!-- </div>-->
</div>
<!-- End Signup Social Buttons -->
</div>
<!-- End Signup -->
<!-- Forgot Password -->
<div id="forgotPassword" style="display: none; opacity: 0;" data-target-group="idForm">
<form method="post" action="https://documento.mx/forgot">
<!-- Title -->
<header class="text-center mb-5">
<h2 class="h4 mb-0">Recover account</h2>
<p>Enter your email address and an email with instructions will be sent to you</p>
</header>
<!-- End Title -->
<!-- Input -->
<div class="js-form-message mb-3">
<div class="js-focus-state input-group form">
<div class="input-group-prepend form__prepend">
<span class="input-group-text form__text">
<span class="fa fa-user form__text-inner"></span>
</span>
</div>
<input type="email" class="form-control form__input" name="email" required
placeholder="Email address"
aria-label="Email address"
data-msg="Please enter a valid email address"
data-error-class="u-has-error"
data-success-class="u-has-success">
</div>
</div>
<!-- End Input -->
<div class="mb-3">
<button type="submit" class="btn btn-block btn-primary">Recover</button>
</div>
</form>
<div class="text-center mb-3">
<p class="text-muted">
Have an account? <a class="js-animation-link" href="javascript:;"
data-target="#signin"
data-link-group="idForm"
data-animation-in="fadeIn">Login </a>
</p>
</div>
</div>
<!-- End Forgot Password -->
</form>
</div>
<!-- End Content -->
</div>
<!-- End Signup Modal Window -->
<!-- ========== END SECONDARY CONTENTS ========== -->
<!-- Go to Top -->
<a class="js-go-to u-go-to" href="#"
data-position='{"bottom": 15, "right": 15 }'
data-type="fixed"
data-offset-top="400"
data-compensation="#header"
data-show-effect="slideInUp"
data-hide-effect="slideOutDown">
<span class="fa fa-arrow-up u-go-to__inner"></span>
</a>
<!-- End Go to Top -->
<!-- JS Global Compulsory -->
<script src="https://documento.mx/assets/vendor/jquery/dist/jquery.min.js"></script>
<script src="https://documento.mx/assets/vendor/jquery-migrate/dist/jquery-migrate.min.js"></script>
<script src="https://documento.mx/assets/vendor/popper.js/dist/umd/popper.min.js"></script>
<script src="https://documento.mx/assets/vendor/bootstrap/bootstrap.min.js"></script>
<!-- JS Implementing Plugins -->
<script src="https://documento.mx/assets/vendor/hs-megamenu/src/hs.megamenu.js"></script>
<script src="https://documento.mx/assets/vendor/malihu-custom-scrollbar-plugin/jquery.mCustomScrollbar.concat.min.js"></script>
<script src="https://documento.mx/assets/vendor/jquery-validation/dist/jquery.validate.min.js"></script>
<script src="https://documento.mx/assets/vendor/fancybox/jquery.fancybox.min.js"></script>
<script src="https://documento.mx/assets/vendor/typed.js/lib/typed.min.js"></script>
<script src="https://documento.mx/assets/vendor/slick-carousel/slick/slick.js"></script>
<script src="https://documento.mx/assets/vendor/pdfobject/pdfobject.js"></script>
<script src="https://documento.mx/assets/vendor/custombox/dist/custombox.min.js"></script>
<script src="https://documento.mx/assets/vendor/appear.js/appear.js"></script>
<script src="https://documento.mx/assets/vendor/dzsparallaxer/dzsparallaxer.js"></script>
<script src="https://documento.mx/assets/vendor/cubeportfolio/js/jquery.cubeportfolio.min.js"></script>
<!-- JS Template -->
<script src="https://documento.mx/assets/js/hs.core.js"></script>
<script src="https://documento.mx/assets/js/helpers/hs.focus-state.js"></script>
<script src="https://documento.mx/assets/js/components/hs.header.js"></script>
<script src="https://documento.mx/assets/js/components/hs.unfold.js"></script>
<script src="https://documento.mx/assets/js/components/hs.malihu-scrollbar.js"></script>
<script src="https://documento.mx/assets/js/components/hs.validation.js"></script>
<script src="https://documento.mx/assets/js/components/hs.fancybox.js"></script>
<script src="https://documento.mx/assets/js/components/hs.slick-carousel.js"></script>
<script src="https://documento.mx/assets/js/components/hs.show-animation.js"></script>
<script src="https://documento.mx/assets/js/components/hs.sticky-block.js"></script>
<script src="https://documento.mx/assets/js/components/hs.scroll-nav.js"></script>
<script src="https://documento.mx/assets/js/components/hs.go-to.js"></script>
<script src="https://documento.mx/assets/js/components/hs.modal-window.js"></script>
<script src="https://documento.mx/assets/js/components/hs.cubeportfolio.js"></script>
<script src="https://documento.mx/assets/js/documento.js?v=2"></script>
<script>
// initialization of text animation (typing)
if (jQuery('.u-text-animation.u-text-animation--typing').length > 0) {
var typed = new Typed(".u-text-animation.u-text-animation--typing", {
strings: ["Documents.", "Magazines.", "Articles.", "And more."],
typeSpeed: 60,
loop: true,
backSpeed: 25,
backDelay: 1500
});
}
</script>
</body>
</html><script>jQuery("#show-more").click(function(){$(this).prev().css("max-height", "none")});</script>