Transcript CE221_week_1_Chapter1_Introduction

CS 201
Data Structures & Algorithms
Chapter 1 Introduction
Text: Read Weiss, §1.1 – 1.3
Izmir University of Economics
1
Course Policy
• Syllabus
• Grading
• Labs always in C++ (and/or C)
programming language
• Each assignment starts and ends in the same
Lab session. Late assignments will not be
accepted.
• Study hard!
Izmir University of Economics
2
Introduction
• See that how a program performs for
reasonably large input is just as important as
its performance on moderate amounts of
input
• Summarize basic mathematical background
needed
• Review recursion
Izmir University of Economics
3
Motivating Examples: Selection
• Selection problem: you have a group of N numbers and
would like to determine the kth largest.
• I: read them into an array. Sort them in a decreasing order.
Return the kth element.
• II: read the first k elements into the array. Sort them in
decreasing order. Next read the remaining elements one by
one. If the new element read is smaller than the last, ignore
it otherwise place in the correct spot in the array bumping
one element out of the array.
• A simulation with a random file of 10 million elements and
k = 5,000,000 shows that each requires several days of
computer processing.
Izmir University of Economics
4
Motivating Examples: Word Puzzles
• Solving a popular word puzzle: Input consists of a two
dimensional array of letters and a list of words. The
objective is to find the words laying horizontally, vertically
or diagonally in either direction.
• I: for each word in the word list, check (row, column,
orientation)
• II: for each ordered quadruple (row, column, orientation,
number of characters), test whether the word is in the word
list.
• {this, two, fat, that}
Izmir University of Economics
5
Math Review - Exponents
•
•
•
•
XAXB = XA+B
XA/XB = XA-B
(XA)B = XAB
XN+XN = 2XN !=X2N
Izmir University of Economics
6
Math Review – Logarithms I
• In computer science, all logarithms are to the base 2 unless
specified otherwise.
• Definition 1.1. XA = B if logXB=A
• Theorem 1.1. logAB = logCB/logCA
where A, B, C > 0, A != 1
• Proof: Let X=logCB, Y=logCA, Z=logAB
CX=B, CY=A, AZ=B by Definition 1.1.
B=CX=(CY)Z.Therefore, X=YZ
• Theorem 1.2. log AB = logA + logB where A, B > 0
• Proof: X=logA, Y=logB, and Z=logAB,
2X=A, 2Y=B, and 2Z=AB, 2X2Y=AB=2Z.
Therefore, X+Y=Z
Izmir University of Economics
7
Math Review – Logarithms II
•
•
•
•
log A/B = logA – logB
log(AB)=BlogA
logX < X for all X > 0
log1 = 0, log2 = 1, log1024 = 10
Izmir University of Economics
8
Math Review – Series I
• Geometric Series
N i
 2  2 N 1 1
i 0
N i A N 1 1
A 
A1
i 0
N i
1
A 
1 A
i 0
• If 0 < A < 1, then
and as N
tends to , the sum approaches
1/(1-A)
• S=1+A+A2+A3+A4...
• AS=A+A2+A3+A4+A5...
• S-AS= 1 which implies S=1/(1-A)
Izmir University of Economics
9
Math Review – Series II
i
i1i / 2  ?
1 2 3 4
S   2  3  4  ...
2 2 2 2
2 3 4
2S  1  2  3  ...
2 2 2
1 1 1
2S  S  S  1  2  3  ...  2
2 2 2
• Arithmetic Series
N N ( N 1) N 2

(Gauss Method )
i 
2
2
i 1
S  1
2
3
... N
S  N  N 1 N  2 ... 1
 _______________________________
2S  N 1 N 1 N 1 ... N 1
S  N ( N 1) / 2
Izmir University of Economics
Example :
k
k
k
 3i 1   3i  1
i 1
i 1 i 1
k
k
3  i  1
i 1 i 1
3k (k 1) / 2 k
k (3k 1) / 2
10
Math Review – Series III
N 2
i  S
i 1
N 3
N 3 N
3
3 3
 i (i 1)   i   (i 1)  N
i 1
i 1 i 1
N 3 3 2
N 2
 i (i 3i 3i 1)   3i 3i 1
i 1
i 1
N 3 3S 3N ( N 1) / 2 N
S ( N 3 3N ( N 1) / 2 N ) / 3
S  N ( N 2 3( N 1) / 21) / 3
S  N (2 N 2 3( N 1)  2) / 6
S  N (2 N 2 3N 1) / 6
S  N ( N 1)(2 N 1) / 6
 N3 /3
N k N k 1
when k  1
i 
k 1
i 1
N th
Harmonic Series
N1
H   log N
when k 1
N
e
i
i 1
The error in the
approximation tends to
Euler’s constant
 = 0.57721566
General Algebraic Manipulations
N
 f ( N )  Nf ( N )
i 1
n 1
N
N
0
 f (i)   f (i)   f (i)
i n
i 1
i 1
0
Izmir University of Economics
11
Math Review – Modular Arithmetic
• A  B (mod N) means
A is congruent to B modulo N,
If N divides A-B
(remainders are the same)
• Example:81  61  1 (mod 10)
• if A  B (mod N), then
• A + C  B + C (mod N) and
• AD  BD (mod N)
Izmir University of Economics
12
The P Word – Proof by Induction
• There are various ways of proving statements in
data structures analysis
• Proof by Induction: It has two standart parts: The
first step is proving a base case. Establishing that
a theorem is true for some small (usually
degenerate) value(s). This step is almost always
trivial.
• Next, an inductive hypothesis is assumed.
Generally this means that the theorem is assumed
to be true for all cases up to some limit k.Using the
assumption, the theorem is then shown to be true
for the next value, typically k+1.
Izmir University of Economics
13
The P Word – Induction Example I
• Example: Prove that Fibonacci Numbers F0=1, F1=1, and
Fi=Fi-1+Fi-2 for i > 1, satisfy Fi < (5/3)i for i ≥ 1.
• Proof: Verify that the theorem is true for the trivial cases
(base cases): F1=1 < (5/3)1 and, F2 = 2 < (5/3)2. These
prove the basis. We now assume that the theorem is true
for i = 1, 2, ..., k; this is the inductive hypothesis. To prove
the theorem, we need to prove Fk+1<(5/3)k+1.
F
F  F
k 1 k k 1
F (5 / 3) k  (5 / 3) k 1
k 1
F (3 / 5)(5 / 3) k 1 (3 / 5) 2 (5 / 3) k 1
k 1
F (3 / 59 / 25)(5 / 3) k 1
k 1
F (24 / 25)(5 / 3) k 1
k 1
F (5 / 3) k 1
k 1
Izmir University of Economics
14
The P Word – Induction Example II
• Example: If N ≥ 1 then iN1i 2  N (N 1)(2N 1) / 6
• Proof: For the base case, the theorem is true when N = 1.
For the inductive hypothesis, assume the theorem is true
for 1 ≤ k ≤ N. Let’s try to prove that it is true for N + 1
N 1 2 N 2
 i   i  ( N 1) 2
i 1
i 1
N 1 2 N ( N 1)(2 N 1)
 ( N 1) 2 by
 i 
6
i 1
Inductive
Hypothesis
 N (2 N 1)

( N 1)
 ( N 1)
6


2N 2 7 N 6
( N 1)
6
( N 1)( N  2)(2 N 3)

6
Izmir University of Economics
15
Proof by Counterexample
• Proof by Counterexample: Best way for
proving that a statement is false.
• Example: The statement Fk ≤ k2 is false.
The easiest way to prove this is to compute
F11 = 144 > 112 = 121
Izmir University of Economics
16
Proof by Contradiction
• It proceeds by assuming that the theorem is false and
showing that this assumption implies that some known
property is false, and hence the original assumption is
erroneous.
• Example: Prove that there is an infinite number of primes.
• Proof: Assume the theorem is false, so that there is some
largest prime Pk. Let P1, P2, ..., Pk be all the primes in
order and consider N = P1P2...Pk + 1. Clearly, N > Pk, so by
assumption N can not be prime.
However, none of P1, P2, ..., Pk divides N exactly, because
remainders are all 1. This is a contradiction: numbers are
either prime or a product of primes. Hence the original
assumption is false implying that the theorem is true.
Izmir University of Economics
17
A Brief Introduction to Recursion
• A function that is defined in terms of itself is called
recursive. Not all mathematically recursive functions are
correctly or efficiently implemented by recursion.
• Example: f (x)2 f (x1) x2 for all integers x ≥ 0 with f(0)=0
#include <stdio.h>
• If F is called with a value of
4, then 2*F(3)+4*4 will be
int F( int X ) {
required to be computed. Thus
if( X == 0 ) /* base case */
a call is made to find F(3).
return 0;
• F(4)=2*F(3)+4*4
else
return 2 * F( X - 1 ) + X * X; • F(3)=2*F(2)+3*3
}
• F(2)=2*F(1)+2*2
• F(1)=2*F(0)+1*1
main( )
{
• F(0)=0 base case. Recursive
printf( "F(4) = %d\n", F( 4 ) );
calls until a base case. F(-1)=?
return 0;
• Automatic Bookkeeping
}
Izmir University of Economics
18
Recursion - Bad
• Bad(0)=0, Bad(N)=Bad(N/3 + 1) + N – 1
• To compute Bad(1), the computer will repeatedly make
calls to Bad(1). Eventually, it will run out of space
#include <stdio.h>
int Bad( unsigned int N ) {
if( N == 0 )
return 0;
else
return Bad( N / 3 + 1 ) + N - 1;
}
main( )
{
printf( "Bad is infinite recursion\n" );
return 0;
}
Izmir University of Economics
19
Fundamental Rules of Recursion - I
• 1) Base cases: You must always have some
base cases, which can be solved without
recursion.
• 2) Making progress: For the cases to be
solved recursively, the recursive call must
always be to a case that makes progress
toward a base case.
Izmir University of Economics
20
Recursion - Induction
• PrintOut(N) prints out positive integers. PrintDigit(Ch)
take a single digit number as character and output it to the terminal
#include <stdio.h>
#define PrintDigit( Ch ) ( putchar( ( Ch ) + '0' ) )
/* Print nonnegative N */
void PrintOut( unsigned int N ) {
if( N >= 10 )
Theorem: Recursive number-printing
PrintOut( N / 10 );
algorithm is correct for N ≥ 0.
PrintDigit( N % 10 );
Proof (by induction): If N has one digit, then it
}
main( )
{
PrintOut( 1369 );
putchar( '\n' );
return 0;
}
is correct. Assume it works for all numbers of k
or fewer digits. A number of k+1 digits is
expressed by its first k digits followed by its
least significant digit. N   N / 10  N (mod 10)
By the inductive hypothesis, first part is printed
correctly and then the last digit is appended.
Izmir University of Economics
21
Fundamental Rules of Recursion - II
• 3) Design rule: Assume that all the
recursive calls work. This rule is important.
It relieves you of the burden of thinking
about the details of bookkeeping.
• 4) Compound interest rule: Never duplicate
work by solving the same instance of a
problem in separate calls.
• Hidden bookkeeping costs are mostly
justifiable. However; It should never be
used as a substitute for a simple loop.
Izmir University of Economics
22
C Style
Kth Fibonacci Numbers
F0 0, F1 1, and , Fi Fi 1  Fi  2
For  i  1
n0 1
n1 1
n2 n1  n0  1 1  1  1  3
n3 n2  n1  1  3  1  1  5
n4 n3  n2  1 5  3  1  9
n5 n4  n3  1  9  5  1  15
n6 n5  n4  1 15  9  1  25
n7 n6  n5  1 25  15  1  41
n8 n7  n6  1 41  25  1  67
kth Fibonacci Numbers
Binary recursion
int BinaryFib(k) {
// Input: An integer k
// Output: The kth Fibonacci number
if (k <= 1) then
return k ;
else
return BinaryFib(k-1)+BinaryFib(k-2);
}
Recursion
Calculate factorial (n!) of a positive integer:
n! = n(n-1)(n-2)...(n-n-1), 0! = 1! = 1
0! 1, n !  n((n  1)!)
(n  0)
int factorial(int n) {
if (n <= 1)
return 1;
else
return (n * factorial(n-1));
}
Homework Assignments
• 1.5, 1.7, 1.8.a, 1.8.b, 1.8.c, 1.9, and 1.12.
• You are requested to study and solve the
exercises. Note that these are for you to
practice only. You are not to deliver the
results to me.
Izmir University of Economics
27