CS计算机代考程序代写 Excel algorithm Algorithms COMP3121/9101

Algorithms COMP3121/9101
Aleks Ignjatovi ́c, ignjat@cse.unsw.edu.au
office: 504 (CSE building)
Course Admin: Anahita Namvar, cs3121@cse.unsw.edu.au
School of Computer Science and Engineering University of New South Wales Sydney
1. INTRODUCTION
COMP3121/3821/9101/9801
1 / 21

Introduction
What is this course about?
It is about designing algorithms for solving practical problems.
COMP3121/3821/9101/9801 2 / 21

Introduction
What is this course about?
It is about designing algorithms for solving practical problems. What is an algorithm?
An algorithm is a collection of precisely defined steps that are executable using certain specified mechanical methods.
By “mechanical” we mean the methods that do not involve any creativity, intuition or even intelligence. Thus, algorithms are specified by detailed, easily repeatable “recipes”.
The word “algorithm” comes by corruption of the name of Muhammad ibn Musa al-Khwarizmi, a Persian scientist 780-850, who wrote an important book on algebra, “Al-kitab al-mukhtasar fi hisab al-gabr wal-muqabala”. You are encouraged to read about him in Wikipedia.
COMP3121/3821/9101/9801 2 / 21

Introduction
In this course we will deal only with sequential deterministic algorithms which means that:
they are given as sequences of steps, thus assuming that only one step can be executed at a time;
the action of each step gives the same result whenever this step is executed for the same input.
COMP3121/3821/9101/9801 3 / 21

Why should you study algorithms design?
Can you find every algorithm you might need using Google?
COMP3121/3821/9101/9801 4 / 21

Why should you study algorithms design?
Can you find every algorithm you might need using Google?
Our goal:
To learn techniques which can be used to solve new, unfamiliar problems that arise in a rapidly changing field.
Course content:
a survey of algorithm design techniques
COMP3121/3821/9101/9801
4 / 21

Textbooks
Textbook:
Kleinberg and Tardos: Algorithm Design
paperback edition available at the UNSW book store
COMP3121/3821/9101/9801 5 / 21

Textbooks
Textbook:
Kleinberg and Tardos: Algorithm Design
paperback edition available at the UNSW book store
excellent: very readable textbook (and very pleasant to read!); not so good: as a reference manual for later use.
An alternative textbook:
Cormen, Leiserson, Rivest and Stein: Introduction to Algorithms preferably the third edition, should also be available at the bookstore
COMP3121/3821/9101/9801 5 / 21

Examples of Algorithms
Problem:
Two thieves have robbed a warehouse and have to split a pile of items without price tags on them. Design an algorithm for doing this in a way that ensures that each thief believes that he has got at least one half of the loot.
The solution:
One of the two thieves splits the pile in two parts, so that he believes that both parts are of equal value. The other thief then chooses the part that he believes is no worse than the other.
The hard part: how can a thief split the pile into two equal parts? Remarkably, this turns out that, most likely, there is no more efficient algorithm than the brute force: we consider all partitions of the pile and see if there is one which results in two equal parts.
COMP3121/3821/9101/9801 6 / 21

Examples of Algorithms
Problem:
Three thieves have robbed a warehouse and have to split a pile of items without price tags on them. How do they do this in a way that ensures that each thief believes that he has got at least one third of the loot?
Remarkably, the problem with 3 thieves is much harder than the problem with 2 thieves!
Let us try do the same trick as in the case of two tieves. Say the first thief splits the loot into three piles which he thinks are of equal value; then the remaining two thieves choose which pile they want to take.
If they choose different piles, they can each take the piles they have chosen and the first thief gets the remaining pile; in this case clearly each thief thinks that he got at least one third of the loot.
COMP3121/3821/9101/9801 7 / 21

One might think that in this case the first thief can pick any of the two piles that the second and the third thief did not choose; the remaining two piles are put together and the two remaining thieves split them as in Problem 1 with only two thieves. Unfortunately this does not work:
after the first thief splits the loot into three piles A, B, C, it might happen, for example, that the second thief thinks that
A = 50%, B = 40%, C = 10%
of the total value, while the third thief thinks that
A = 50%, B = 10%, C = 40%.
Thus, if the first thief picks pile B, then the second thief will object that the first thief is getting 40% while he will likely get only 60%/2 = 30%.
COMP3121/3821/9101/9801
8 / 21

COMP3121/3821/9101/9801 9 / 21

Algorithm:
T1 makes a pile P1 which he believes is 1/3 of the whole loot; T1 proceeds to ask T2 if T2 agrees that P1 ≤ 1/3;
If T2 says YES, then T1 asks T3 if T3 agrees that P1 ≤ 1/3;
If T3 says YES, then T1 takes P1;
T2 and T3 split the rest as in Problem 1.
Else if T3 says NO, then T3 takes P1;
T1 and T2 split the rest as in Problem 1.
Else if T2 says NO, then T2 reduces the size of P1 to P2 < P1 such that T2 thinks P2 = 1/3; T2 then proceeds to ask T3 if he agrees that P2 ≤ 1/3; If T3 says YES then T2 takes P2; T1 and T3 split the rest as in Problem 1. Else if T3 says NO then T3 takes P2; T1 and T2 split the rest as in Problem 1. COMP3121/3821/9101/9801 9 / 21 Algorithm: T1 makes a pile P1 which he believes is 1/3 of the whole loot; T1 proceeds to ask T2 if T2 agrees that P1 ≤ 1/3; If T2 says YES, then T1 asks T3 if T3 agrees that P1 ≤ 1/3; If T3 says YES, then T1 takes P1; T2 and T3 split the rest as in Problem 1. Else if T3 says NO, then T3 takes P1; T1 and T2 split the rest as in Problem 1. Else if T2 says NO, then T2 reduces the size of P1 to P2 < P1 such that T2 thinks P2 = 1/3; T2 then proceeds to ask T3 if he agrees that P2 ≤ 1/3; If T3 says YES then T2 takes P2; T1 and T3 split the rest as in Problem 1. Else if T3 says NO then T3 takes P2; T1 and T2 split the rest as in Problem 1. Homework: Try generalising this to n thieves! (a bit harder than with three thieves!) COMP3121/3821/9101/9801 9 / 21 Algorithm: T1 makes a pile P1 which he believes is 1/3 of the whole loot; T1 proceeds to ask T2 if T2 agrees that P1 ≤ 1/3; If T2 says YES, then T1 asks T3 if T3 agrees that P1 ≤ 1/3; If T3 says YES, then T1 takes P1; T2 and T3 split the rest as in Problem 1. Else if T3 says NO, then T3 takes P1; T1 and T2 split the rest as in Problem 1. Else if T2 says NO, then T2 reduces the size of P1 to P2 < P1 such that T2 thinks P2 = 1/3; T2 then proceeds to ask T3 if he agrees that P2 ≤ 1/3; If T3 says YES then T2 takes P2; T1 and T3 split the rest as in Problem 1. Else if T3 says NO then T3 takes P2; T1 and T2 split the rest as in Problem 1. Homework: Try generalising this to n thieves! (a bit harder than with three thieves!) Hint: there is a nested recursion happening even with 3 thieves! COMP3121/3821/9101/9801 9 / 21 The role of proofs in algorithm design COMP3121/3821/9101/9801 10 / 21 The role of proofs in algorithm design When do we need to give a mathematical proof that an algorithm we have just designed terminates and returns a solution to the problem at hand? COMP3121/3821/9101/9801 10 / 21 The role of proofs in algorithm design When do we need to give a mathematical proof that an algorithm we have just designed terminates and returns a solution to the problem at hand? When this is not obvious by inspecting the algorithm using common sense! COMP3121/3821/9101/9801 10 / 21 The role of proofs in algorithm design When do we need to give a mathematical proof that an algorithm we have just designed terminates and returns a solution to the problem at hand? When this is not obvious by inspecting the algorithm using common sense! Mathematical proofs are NOT academic embellishments; we use them to justify things which are not obvious to common sense! COMP3121/3821/9101/9801 10 / 21 Example: MergeSort Merge-Sort(A,p,r) 1 ifp

Related Posts