SE 2004

ALGORTIHMS

Dr. Emine Elif Tülay

COURSE INFORMATION
• All Announcement: Syllabus, Lecture notes, etc. will be on https://dys.mu.edu.tr/

• Grading Policy: It will be precise later on

• Attendance Policy: You should attend at least 70% of classes to pass the course.

• Plagiarism and Cheating Policy: Zero-tolerance!

GETTING HELP
• Office hours:
– Thursday 11.00 – 12:30, at building
«Research And Application Centre For
Research Laboratories»,
– Or, email to schedule an appointment.

• You can always email me

– eliftulay@mu.edu.tr
SUGGESTED BOOKS

Pearson https://www.cs.princeton.edu/~wayne
/kleinberg-tardos/pearson/
SUGGESTED BOOKS

Addison - Wesley
https://aofa.cs.princeton.edu/home/
GOALS understand
algorithms and
design
introduce techniques to
the classic solve problems
algorithms

learn the
complexities
Compare of various
algorithms algorithms
SYLLABUS
Week (Lec ) Topic
Week 1 Introduction to Algorithm
Week 2 Algorithms Analysis
Week 3 Searching Algorithms
Week 4 Sorting Algorithms
Week 5 Brute Force Algorithms
Week 6 Divide-and-Conquer Algorithms
Week 7 Decrease-and-Conquer Algorithms This outline shows the
Week 8 Graph Algorithms 1 list of topics associated
with each class meeting.
Week 9 Graph Algorithms 2
Week 10 Dynamic programming However, it is tentative
Week 11 Greedy Technique and subject to change as
seen necessary and
Week 12 NP-Complete Problems appropriate during the
Week 13 Special interests semester.
Week 14 Wrap-Up
W H AT A R E A L G O R I T H M S
AND
WHY SHOULD YOU CARE?
QUESTIONS IN MINDS
• What are algorithms?

• Why is the study of algorithms worthwhile?

• What is the role of algorithms relative to other technologies used
in computers?
• Is the algorithm correct or efficient? How can we prove that it is?
WHAT ARE ALGORITHM?
• An algorithm is any well-defined computational procedure that
– takes some value, or set of values, as input and produces some value, or set
of values, as output.
– perform the task in a finite amount of time

The notion of the algorithm.

WHAT ARE ALGORITHM?
• An algorithm is thus an explicit, precise, unambiguous,
mechanically-executable sequence of computational steps that
transform the input into the output.

• We can also view an algorithm as a tool for solving a well-specified

computational problem.
WHY STUDY ALGORITHMS?
Their impact is broad and far-reaching.
Almost all technology companies and science fields use them!

KEVIN WAYNE -
ALGORITHMS
and DATA
STRUCTURES -
2021
 Artificial Intelligence
Data processing Algorithms are used to develop
Algorithms are used to process intelligent systems, such as ML
and analyze large amounts of algorithms, natural language
data, such as sorting and processing algorithms, and
searching algorithms. computer vision algorithms.

Example: Binary Search, Bubble Sort Example: SVM

Network communication Operating systems

Algorithms are used for efficient Algorithms are used in operating
communication and data transfer systems for tasks such as
in networks, such as routing process scheduling, memory
algorithms and error management, and disk
correction algorithms. management.

Example: Dijkstra's algorithm Example: Round Robin

 Algorithmics is more than a branch of
computer science. It is the core of
computer science, and, in all fairness, can be
said to be relevant to most of science,
business, and technology

~David Harel: Algorithmics: the Spirit of

Computing~
DUTY 1
• Find interesting and latest news about algorithms!

• Tell us next week

• Not will be graded, just for fun.

• Please take it seriously!

WHY STUDY ALGORITHMS?
To become a good programmer.

“ I will, in fact, claim that the difference between a bad

programmer and a good one is whether [they] consider
[their] code or [their] data structures more important.
Bad programmers worry about the code. Good
programmers worry about data structures and their
relationships. ”
~Linus Torvalds~
(architect of Linux and git)
WHY STUDY ALGORITHMS?
• Useful Can I do
better?
– As we get more and more data and problem sizes
get bigger and bigger, algorithms become more and
more important.

• Fun
– Algorithms is still a young area, and there are still
many mysteries, and many problems for which we
still do not know the best algorithms Algorithm designer
HOW MANY SHORTEST PATH
ALGORİTHMS ARE THERE?
1. Shortest Path Algorithm using Depth-First Search(DFS
2. Breadth-First Search (BFS) for Shortest Path Algorithm
3. Multi-Source BFS for Shortest Path Algorithm
4. Dijkstra’s Algorithm for Shortest Path Algorithm
5. Bellman-Ford algorithm for Shortest Path Algorithm
6. TopoLogical Sort
7. Floyd-Warshall algorithm for Shortest Path Algorithm
8. A* Search Algorithm for Shortest Path Algorithm
9. Johnson’s Algorithm for Shortest Path Algorithm
WHY STUDY ALGORITHMS?
Job Interviews

• High-technology companies tend to ask

questions about algorithms and data
structures during job interviews.

• Please see “Applications” exercises in

Chapter 1 of the Goodrich Tamassia
textbook that was taken from reports of
actual job interview questions.
– https://canvas.projekti.info/ebooks/Algorithm%20D
esign%20and%20Applications%5BA4%5D.pdf
PROBLEMS VS ALGORITHMS VS PROGRAMS
For each problem, there may be many different algorithms.

For each algorithm, there may be many different implementations (programs).

WHICH ALGORITHM IS BEST…
• …a given application depends on
– the number of input,
– the architecture of the computer,
– the kind of storage devices to be used: main memory, disks, or even
tapes
– So on…

We should analyze the algorithm to decide whether it is efficient.

Suppose computers were infinitely fast and computer
memory was free.

Would you have any reason to analyze algorithms?

YES!

You would still like to demonstrate that your

solution method terminates and does so with
the correct outputs for every input instance
 Of course, computers may be fast, but they are not
infinitely fast and memory may be inexpensive, but it
is not free.

Computing time is therefore a bounded resource, and so is

space in memory.

You should use these resources wisely, and algorithms that are
efficient in terms of time or space will help you do so.
 Algorithm
design and
analysis
process

FUNDAMENTALS
OF ALGORITHMIC
PROBLEM
SOLVING
A COMMON PROBLEM
• Sorting is a fundamental operation in computer science.

We have a large
number of good
.
sorting algorithms
ALGORITHM DESIGN TECHNIQUES
How do you sort a cart of books in
increasing order of the volume number?
(i.e. volume 1, volume 2, volume 3....)?
Bad algorithm: compare all books, put the
smallest volume in the beginning, and
repeat. (Brute Force)

Clever algorithm: divide the cart into two,

sort the first half, sort the second half, and
merge them. (Divide and conquer)
 So, which design
technique does this
algorithm use?

Brute Force using

single loop

! https://www.enjoyalgorithms.com/blog/find-the-minimum-and-maximum-value-in-an-array
A PROBLEM YOU ALL KNOW HOW TO SOLVE:
INTEGER MULTIPLICATION

12
x 34
A PROBLEM YOU ALL KNOW HOW TO SOLVE:
INTEGER MULTIPLICATION

1234567895931413
x 4563823520395533
A PROBLEM YOU ALL KNOW HOW TO SOLVE:
INTEGER MULTIPLICATION
n

1233925720752752384623764283568364918374523856298
x 4562323582342395285623467235019130750135350013753

???
How would you solve this problem?
How long would it take you?
About 𝑛𝑛2 one-digit operations
At most 𝑛𝑛2 multiplications,
and then at most 𝑛𝑛2 additions (for carries)
and then I have to add n different 2n-digit numbers…

And I take 1 second to multiply two one-digit numbers and .6 seconds to add, so…
Slide from Huma Ayub
Let the two given numbers be 'a' and 'b'
1) Initialize result 'res' as 0.
2) Do following while 'b' is greater than 0
a) If 'b' is odd, add 'a' to 'res'
b) Double 'a' and halve 'b'
3) Return 'res'.
Slide from Huma Ayub
WHICH ALGORITHM IS BETTER?
All the algorithms are correct, but which is
the best?
• Measure the running time (number of operations
needed).
• Measure the amount of memory used.
• Note that the running time of the algorithms
increase as the size of the input increases.

Slide from Huma Ayub

HARD PROBLEMS
• There are some problems, however, for which no efficient solution is
known, which are known as NP-complete (nondeterministic polynomial-
time complete).
– Travelling Salesman algorithms
• We can find the “shortest
tour” but not the “best tour”.
DESIGN AND ANALYSIS OF
ALGORITHMS
• Analysis: predict the cost of an algorithm in terms of
resources and performance

• Design: design algorithms that minimize the cost

Remember that a correct algorithm is not one
that works most of the time, but one that
works correctly for all input.
ONLINE ALGORITHMS MATERIALS
• Introductory Algorithms course at the University of Cambridge by Frank
Stajano
– https://www.youtube.com/watch?v=m7npVV-
H8lI&list=PLbyW0t9gkXg0NtX6IYCwQjxDD8yvcS1pX&index=2

• Pros and Cons of the Algorithm Age

– https://www.pewresearch.org/internet/2017/02/08/code-dependent-pros-and-cons-of-the-algorithm-
age/