slaytı sınava hazırlanan öğrencinin tüm konuları anlayacak şekilde detaylıca özetle, her bir terim konu hakkında buna uygun bilgiler vererek anlaşılmasında yardımcı ol:

What is an algorithm?
• A well-defined computational procedure that takes some values as 
input, and produces some values as output
• A step-by-step instruction for solving a computational problem
• Enough details so that a competent computer scientist can 
implement without questions
↳mathematical entity
↳ independent from a programming language
Why study design and analysis of algorithms?
• Programming is a complex task
• structural complexity
• large data sets and complex data structures
• complex computational problems that requires efficient algorithms
• There are standard ways to approaching algorithm design (patterns)
• High-level tools for run-time analysis
• This course: how to design good algorithms and how to analyze their 
efficiency
Good algorithm?
Many issues other than performance
Correctness Modularity Easy maintainance
Robustness Simplicity Extensibility
…
Our main focus in this course:
1. Correctness
2. Efficiency: amount of computational resources, such as running 
time and space
Time Efficiency
• A function of input size (and input structure)
• Worst-case: 
T(n) = maximum running time of algorithm among all inputs of size n. 
• Average-case: 
T(n) = expected time of algorithm over all inputs of size n. 
Need assumption of statistical distribution of inputs. 
I
fcn4"* Tln)
Tcn,
m )
Algorithm Write-up Components
1. Description: concise and unambiguous description of the algorithm in plain 
English/Turkish
2. Pseudocode: try to follow our textbook’s conventions
3. Proof of Correctness:
• Termination
• Functional correctness: e.g. using proof by induction, proof by contradiction, invariants..
• Optimality (for optimization problems)
4. Efficiency Analysis (mostly time)
L • insertEnd (X)
insert ✗ at the endof L
↳ CLRS
= ↳ e.g.
bubblesort
invent: after
T
ith iteration,
last i elements
are in place .
Model of Computation: RAM Model
• An abstraction of a standard generic single processor machine
• Infinitely large random access memory
• Instructions are executed sequentially
• Basic Operations take a small constant time to run
• Arithmetic
• Comparison
• Assignment
• Array indexing
• Function call/return
• Ignore memory hierarchy, locality of reference (in reality cached items 
for example are faster to access than the ones stored in memory)
-no parallelism
A [0]
Sorting Problem
Input: a sequence of n numbers〈a1, a2, ..., an〉
Output: a reordering (permutation) of the input sequence 
〈a'1, a'2, ..., a'n 〉such that a'1 ≤ a'2 ≤ ... ≤ a' -
=n.
→ tiondecreasingordv
increasing
1 j n
Insertion Sort
Sorted
key=A[j]
j=2 to
nq
a E-¥÷÷÷
A
nE㱺 -
finally '
.
£
1 j n
Insertion Sort
Sorted
key=A[j]
i
→ →
7*40%1-41845
0=8
worst-case : j
-1 shifts
when inserting
A[j]
InsertionSort(A, n){
for j=2 to n {
key = A[j]
i = j-1
while i > 0 and A[i] > key{
A[i+1] = A[i]
i = i-1
}
A[i+1]=key
}
} 
AG. .n] -
region .
?µ """"
YAG] inbtneso.ie,
→terminate if Acitky
OR I =D
-1=951 -
A- [0+2]=8 ¥¥-
Insertion Sort Example
I
qÉ
¥¥s-
,¥¥r
Insertion Sort Example .
j=6
taxes
Insertion Sort - Analysis
• Parameterize the running time by the size of the input: n
• Short sequences are faster to sort than long ones
• What else does the running time depends?
• E.g. an already sorted sequence is easier to sort
• Generally, we seek upper bounds on the running time, because 
everybody likes a guarantee. 
L
Ñ§%IH
is for inyzg.gl#d
easier to characterize
the worst case
instance
InsertionSort(A, n){
for (j=2 to n) {
key = A[j]
i = j-1
while(i > 0 and A[i] > key){
A[i+1] = A[i]
i = i-1
}
A[i+1]=key
}
} 
Assume each execution of the i-th line takes ci time
#iÉhns totalling
j=2 J⇐n
→
n -1+1 =n CIN
→ n - I Czcn -1 )
→ n -
I ↳ Cn -
1)
Éi
It
'
÷
:
Legs,
/ ↳ Eg,
,
j=2
j.tt
↳ Écj -1 Écj -1 ) )
↳ j=z 5=2
n -1 G- Cn -
1)
TG) = q n t Cz Cn -
1) + Cs Cn -
1)+
4 ↳
É+8 + sin-4
Ten>
= ÉE÷n2 +
ÉEzn
j
=2
zcj -
t
) = 1 +2 + - - -
Cn -
1) =
(n→÷
1-G) =
☒①-
+ 13/11-1 ☒
* omit lower order terms
# ignore constants
↳machine dependent ?⃝,p+o+ic growth rate : D-(n2)
we are interested in growth of function
for sufficiently large n . K2 dominates
n
Review: Summations (3.2 of CLRS)
Basic Rules:
(1) ∑!"#
$ "#! = c ∑!"#
$ #!
(2) ∑!"#
$ (#! + &!) = ∑!"#
$ #! + ∑!"#
$ &!
(3) ∑!"%
$ #! = ∑!"#
$ #! − ∑!"#
%&# #!
16.9.2021
Solving a summation means reducing it
to a closed formula .
€-az + ay -1 - - -+an
constant
n I
% - Zai
i =L
---
-
TT
Important Summations
• Constant series
!
!"#
$
1 = max(( − * + 1, 0)
• Arithmetic series
!
!"%
&
/ = 1 + 2 + ⋯ + 2 =
2 2 + 1
2 ∈ Θ 2'
• Geometric series: For " ≠ 1, n ≥ 0
!
!"(
&
5! = 1 + 5 + 5' … + 5& =
5&)% − 1
5 − 1 ∈ 7
Θ 1 , 0 < 5 < 1
Θ 5&
, 5 > 1
19
militias ,
-
-
-
i.
I
,+,. . -
+ i
if 04<1 Éci=y1=€ @ (1)
i=o
Important Summations
• Quadratic series
!
!"%
&
/' = 1' + 2' + ⋯ + 2' =
22* + 32' + 2
6 ∈ Θ 2*
• Linear-geometric series
For " ≠ 1, n ≥ 0
!
!"%
&
/5! = 5 + 25' + ⋯ + 25& =
2 − 1 5&)% − 25& + 5
5 − 1 ' ∈ Θ 25&
20
-
f)
= ^G+1Y2n#
-
ii. - -
E
Important Summations
• Harmonic series
<& = !
!"%
&
1
/
= 1 +
1
2 +
1
3 + ⋯ +
1
2
= ln 2 + ? 1 = ?(ln 2)
21
-
a
,
in -
loser
Approximation with Integrals
• Integration and summation are closely related
• Let f(x) be any monotonically increasing function 
@
(
&
A B CB ≤ !
!"%
&
A(/) ≤ @
%
&)%
A B CB
22
f-G)
¢-0
fistful + - - -
+ f" H"
?q¥¥É¥É¥f "
fÉ 9
Analyzing Programs with Loops
for i=1 to n {
…constant-time statement(s)
for j=1 to n {
…constant-time statement(s)
}
}
Loosetomds [ie f Inna = n -
n'⇐ off)
i =L
i =L
→ CI
I -
→ Cz
1 full execution of inner loop : can
1 iteration of the outer loop : Cy + Can
1 full execution of the outer loop :
①
É(gean) = Éci Zani +
=L I =L
i =L = can + ncczn) C- D-Cny
for k=1 to n {
for i=1 to n {
…constant-time statement(s)
for j=1 to n {
…constant-time statement(s)
}
}
}
¥=n. En-
=P
K =L
i =L
for i=1 to n {
for j=1 to 2*i {
k=j
while k >= 0 {
…constant-time statement(s)
k = k-1
}
} ÷
}
¥E ]
If ) : running time of 1 full executor of the innermost loop
K : j,j -2,
- - - - -
-
0
IGT = É1 = j-11
1<=0
MC:) = ÉICj) = Éj-12)
j=L j
=L
= + €1 = 2iGz+
zi
j
=L
Mci) =
272+3i
1-Cn) =
¥2M Ci) = 2^-1212+3 :)
i -1
= 2^-22+3 É,
i
f-I
= 4n3+15nJ € 0-63)
for (i=o to n1)
Fl)
for Cj = 1 to 2:)
- - -
constant time statements
Ici) = 2
"
n - I
1-Cn) = 2- Ici) =
£12:
i =D
i =0
=
1-12+22-1 - - -
+2^-2
=
2I÷ c- 0 (2)
Previous Greater Element Problem
• A list of numeric values *%, *', … , *&
• For each *!, find the index of the rightmost element of the sequence 
*%, *', … , *!+% whose value is strictly greater than *!, or 
if no such element exists return 0 (Instead, we will define *( = ∞)
• P! = max Q|0 ≤ Q < / and *, > *!
Example: 4, 3,11,9,5,6,8,12,7,10
27
→
-
£1 2 3 45 67 8 g to ← I
Pi : 0 1034440 8 8 ← output
Example: 4, 3,11,9,5,6,8,12,7,10
so
C- -
-
- -
-
- .
← - - -
← -
← -
← -
-
⇐ - -
← -
⇐-
⇐ ,
,
11 9← } 6 8 12
z
10
4 3
90 91 92 93 94 9g 96 97 98 99 910
pi= 0 1 ° 3 4 4 4 0 8 8
✗returns p[1- -
n]
BM-YY.fi?-nos+iay(aCs..n3) {
for (i=1 to n ) { ✗ process
aCi]
→
previous laser does:*
j= i-1
WII(jI and a[j]])
j
- -
Keep searching
p[i] =
I
9, az a ]
94
3
return P (8,10 ,
12 ,
16 )
] worst-case
%.-
e- - -
iii.it
90 8 10 12 16
Worst-case Analysis
• Dominated by the time spent in the inner loop
• / 0 = ∑!"#
$ ∑'"(
!&# 1
• = 1 + 2 + ⋯ 0 − 1 + 0
• = ∑!"#
$ 4
• =
$($*#)
,
• ∈ Θ(0,)
30
Worst-case invroop runs from j=i -1 down to 0
ÉI = i
5=0
☐inner loop i
-
Can we do better?
(4,3/1119,5/6/8,12,
7,10 >
i : L 2 3 4 56 7 8 9 10
←
YES
→ start processing from the end of the sequence
→ use a stack
acid i
process
10 : push d y
process
7 : 7410 ,push 7/9
8 12
1971 process
12 : 12>7, pop
7
p[9] = 8
in 101
i a[i] keepP°PPi§ 12 > 10,
pop
10
till coming
across alarge one
, p[10] = 8
or empty stack
Can we do better?
push 12
¥•__@-__-hO%B←p•ss g- 8<12 -
push 8
¥ § process
6- 6<8 push 6
process
5- 5<6 push 5
I 12
p-975 / pops
p[51=4
976 , pop
6
p[63=4
9 > 8 ,
pop
8
p[73=4
Can we do better?
9<12
,push 9
p-tf-ff-B-f-ss.gg , pop
9
p[4) =3
II
3 11 11<12 , push 11
¢ $
process 3- 3<11 /
push 3
&
process 4- 4>3,pop
3
p[2]=1
9
4<11 -push 4
Can we do better?
process
to - to > 4 , pop 4
pct] = 0
to > 11, pop
11
Bf@@@f@@ p[3] = °
✗ > 12,
pop
12
p [8] =D
rightmostlongerversion 2 ( a [1. -n ] ) {
stack S = now stackC)
S•p);
✗ push index of last element .
/
for (i = n - 1 down 1- 1) {
✗processing
aCi]
each,kvnnt(index)while ( ! S . istmptyc ) &&
pushed into S
a [i] > a [
5.top (D)
-i=] ¥-7
""
⇐
p[J] = "
y
while ( ! 5. isEmpty (3) { ✗ Leftover ones
~ ¢ in stack
j
= 5. pop C) d -
each element is
p[j]=o popped fromS
3 exactly once .
Herd rightmostlager -
version 2 .
* Total #of times the w#loops iterate :
I
↳ each element is popped from S
exactly once .
Rwniyt.me#O-Cn) for n pushes,
n pops .
tightbomd
e. g.
n= 5900° NI
= 50,000
1secvs.14h.ws