Transcript Lecture PPT - IIIT

Problems to algorithms to
programs
Naveen Garg, IIT Delhi
Efficiency
• How would you check if 𝑛 is prime?
• Try to divide it by numbers 1,2,3,4, … , 𝑛 − 1 . If any of these
succeed then 𝑛 is not a prime.
• Can we do something better, which requires less divisions?
• Any number more than 𝑛/2 would not divide 𝑛 and so we could stop
at 𝑛/2.
• Even better?
• Claim: If 𝑛 is not a prime then it has a factor less than 𝑛.
• Proof: if 𝑛 is composite it has at least 2 factors. Both factors cannot be
larger than 𝑛 as their product would exceed 𝑛.
• Hence we need only 𝑛 divisions !!
Coding Theory
• Suppose I have to send a message, S.
• The communication channel might flip some bits of my message so
that the received message, say R, is different from S.
• Is there some way to recover the original message or at least to know
that the message has been corrupted.
• By adding additional bits to the original message we can achieve error
detection and/or correction.
• Efficient codes are those which can provide the necessary guarantees
(can detect/correct if upto x bits are in error) by using very few
additional bits.
King, wine and poison.
• A French king was fond of wine. He had a cellar stocked with
the finest wines and would often invite other nobles to taste
them.
• He had arranged one such wine tasting party. On the day
before the party he found out that an assassin had added a
deadly poison to one of the 1024 bottles.
• Even one drop of wine from the poisoned bottle is enough to
kill a person. But the poison’s effect happens after 12 hrs.
• The king has some slaves who he can “use” to identify the
poisoned bottle. He needs to do this before the party.
• What is the minimum no. of slaves he needs?
Using binary representations
B0
B1
B2
B3
B4
B5
B6
B7
S0
0
1
0
1
0
1
0
S1
0
0
1
1
0
0
S2
0
0
0
0
1
S3
0
0
0
0
S4
0
0
0
S5
0
0
S6
0
S7
.
.
.
B1020 B1021
B1022
B1023
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
1
1
1
1
S8
0
0
0
0
0
0
0
0
1
1
1
1
S9
0
0
0
0
0
0
0
0
1
1
1
1
If (Si,Bj) is 1 then Slave i gets a drop of wine from Bottle j.
If B7 is poisoned then only slaves S0, S1, S2 die.
Hamming Codes
• These are very efficient one bit-error correction codes.
• If the message is m bits long then we add roughly log 2 𝑚 check (or
parity) bits.
• Each check bit, ensures that a certain subset of bits have even parity.
• Subsets are cleverly chosen so that one can work backwards: knowing
which check bits are “violated” helps identify the bit in error.
Hamming codes (illustration)
m1
m2
m3
m4
c1
c2
m1
c3
m2
m3
m4
1
0
1
0
1
0
1
0
1
1
0
0
1
1
0
0
0
1
1
1
1
• c1 is chosen so that 𝑐1 ⊕ 𝑚1 ⊕ 𝑚2 ⊕ 𝑚4 = 0
• c2 is chosen so that 𝑐2 ⊕ 𝑚1 ⊕ 𝑚3 ⊕ 𝑚4 = 0
• c3 is chosen so that 𝑐3 ⊕ 𝑚2 ⊕ 𝑚3 ⊕ 𝑚4 = 0
Hamming codes (illustration)
1
c1
0
c2
m1
0
1
1
c3
1
m2
m3
m4
1
0
1
1
1
0
1
1
1
1
0
1
0
Sent Message
0
1
1
0
0
1
1
Hamming codes (illustration)
Sent Message
0
1
1
0
0
1
1
Recd Message
0
1
1
0
1
1
1
c1
C2
m1
c3
m2
m3
m4
X0
1
1
0
1
1
1
0
1
1
0
1
1
1
0
1
1
X0
1
1
1
Violated check bits form the code (c3,c2,c1) 101 which identifies the
position of the error (bit 5)
Computing Capital Gains Tax
• Suppose you have bought & sold HDFC stock.
• If a stock is held for more than 12 months, the CG is classified as
Long-term-capital-gain (LTCG) and no tax is applicable.
• Else it is a short-term-capital-gain (STCG) and 30% tax is applicable.
(200,0)
+100,10
+150,15
Jan ‘12
Mar ‘12
(100,+5)
(100,+10)
+200,20
-200,20
-100,20
-150, 25
Jan ‘13
Apr ‘13
(50,+5)
(50,0)
(150,+5)
The FIFO rule
+100,10
+150,15
Jan ‘12
Mar ‘12
(100,+5)
(100,+10)
+200,20
-200,20
-100,20
-150, 25
Jan ‘13
Apr ‘13
(50,+5)
(50,0)
(150,+5)
• The law says that the gains have to be computed by the FIFO rule.
• The shares that are bought first are also the first to be sold.
• In this example, the FIFO rule implies all gains are STCG and the tax
liability is 0.3(100*10+100*5+50*5+150*5)=750
Computing CG using FIFO
• The input file contains, for
each transaction, its date,
nature (sell/buy), price and
no of shares.
• Each Buy transaction is added
to a Queue.
• When we encounter a Sell we
match it to the Buy
transaction at the front of the
queue (x).
• CG is updated only if it is a
short term gain.
If t.type = Buy then Q.enqueue(t)
If t.type = Sell then {
while t.shares > 0 do {
If (x.shares > t.shares) then {
CG += t.shares*(t.price - x.price)
x.shares -= t.shares
t.shares = 0
}
else {
CG += x.shares*(t.price-x.price)
t.shares -= x.shares
x = Q.dequeue()
}
}
}
An example from Physics:
Computing current in a resistive circuit.
• You are given a network of resistors and a voltage source.
• The voltage is applied across two points in this circuit.
• The problem is to determine the current in a specific resistor.
• We will use Kirchoff’s laws to formulate this as a system of linear
equations.
• These linear equations can then be solved using Gaussian elimination.
A resistive circuit
• Kirchoff’s law: the total current arriving at a junction equals the
current leaving it.
• Ohm’s law: When a voltage V is applied across a resistance R the
current through it equals V/R.
Finding the EMI (Equated Monthly
Instalment) of your loan
• You borrow a certain amount of money, 𝑃 (Prinicipal), from ICICI at an
interest rate 𝑟 for a duration 𝑑 months.
• ICICI tells you that you have to pay 𝐸 per month and that there
computation is monthly reducing balance.
• How do you know this is correct?
Finding EMI: Illustration
• Suppose P = 10,00,000, r = 12%, d= 240 and E= 20,000
• In month 1: interest = 1% of 10,00,000 = 10,000. The remaining EMI
amount (20,000-10,000 =) 10,000 goes into reducing the principal.
• So principal after month 1 is 9,90,000.
• So principal after month 2 is
9,90,000 – (20,000 – 1% of 9,90,000) = 9,79,9,00
Exercises
1. You are given an 𝑚-bit message. Assume this is at locations 0 to
𝑚 − 1 in an array 𝑀. Write a program to compute the Hamming
code corresponding to this message in an array 𝑆.
2. You are given an 𝑛 × 𝑛 system of linear equations (𝑛 equations in
𝑛 variables). Write a program to solve this system using Gaussian
elimination (the method discussed in class).
Computing Hamming code
// array 𝑀[1. . 𝑛] contains the original message and 𝑆[1. . 𝑘] will contain the sent message
offset =2;
for i = 1 to n do {
if (i + offset == 2^offset) then offset++
S[i + offset] = M[i]
}
k = n + offset
// value of offset is no. of check bits
// the 𝑖 𝑡ℎ bit of number 𝑗 can be computed as (𝑗 𝑚𝑜𝑑 2𝑖−1 )𝑚𝑜𝑑 2
for i = 1 to offset do // computing the 𝑖 𝑡ℎ check bit at position 𝑆 2𝑖−1
for j = 1 to k do
if
𝑗 𝑚𝑜𝑑 2𝑖−1 𝑚𝑜𝑑 2 == 1 then 𝑆 2𝑖−1 = 𝑆 2𝑖−1 ⨁S[j]
Solving system of linear equations
// A[0..n-1,0..n] contains the 𝑛 × 𝑛 matrix A and the 𝑛 × 1 vector 𝑏 of the system 𝐴𝑥 = 𝑏
for j = 0 to n-1 do //zeroing out the entries of the 𝑗𝑡ℎ column below the diagonal.
for i = j+1 to n-1 do // zeroing the entry 𝐴[𝑖, 𝑗] and updating row 𝑖.
𝑚=−
𝐴 𝑖,𝑗
𝐴 𝑗,𝑗
//the factor by which we will multiply the 𝑗𝑡ℎ row
for k = j to n do
𝐴 𝑖, 𝑘 = 𝐴 𝑖, 𝑘 + 𝑚 ∗ 𝐴[𝑗, 𝑘]
// computing the solution vector 𝑥 0. . 𝑛 − 1
for i=n-1 down to 0 do
t=0
for j = i+1 to n-1 do 𝑡 += 𝑥[𝑗] ∗ 𝐴[𝑖, 𝑗]
𝑥[𝑖] = (𝐴[𝑖, 𝑛] − 𝑡)/𝐴[𝑖, 𝑖]