THE UNIVERSITY OF NEW SOUTH WALES
Assignment Project Exam Help
1. INTRODUCTION
Raveen de Silva, WeChat: cstutorcs
office: K17 202
Course Admin: Anahita Namvar,
School of Computer Science and Engineering UNSW Sydney
Term 2, 2022
Table of Contents
Assignment Project Exam Help
2. Solving problems using algorithms
WeChat: cstutorcs
4. An example of the role of proofs 5. Puzzles
Required knowledge and skills
Assignment Project Exam Help
Understanding of fundamental data structures and algorithms Arrays, trees, heaps, sorting, searching, etc.
Written communication skills
WeChat: cstutorcs
No programming involved – see COMP4121 and COMP4128
Smarthinking for writing help
Prerequisite courses
Assignment Project Exam Help
Only prerequisite: COMP2521/9024 Desirable (but not officially required)
For undergrads:
MATH1081 Discrete Mathematics (proofs, graphs)
WeChat: cstutorcs
MATH1131/1141 (matrices, complex numbers,
For postgrads:
COMP9020 Foundations of Computer Science
Extended courses
Assignment Project Exam Help
The extended courses COMP3821/9801 run in T1 only
Differences in content and assessment
Marks will be adjusted in both courses so as not to
WeChat: cstutorcs
disadvantage the extended students
Assignment Project Exam Help
Lectures (weeks 1–10) Thursday 16:00 – 18:00
Friday 11:00 – 13:00
At least one revision lecture in week 6 (flexibility week)
Live streams and recordings on YouTube Slides on Moodle
WeChat: cstutorcs
Consultation (weeks 1–10) Tuesday 14:00 – 15:00
Friday 14:00 – 15:00
Join live on Zoom, recordings on YouTube Exam consultation TBA
Getting Help
Assignment Project Exam Help
Join the Ed forum!
No conventional tutorials or labs.
Help sessions
Every weekday from week 2 at 11am and 5pm, except
WeChat: cstutorcs
Thursday PM and Friday AM
Tutor-led discussion of tutorial problems Voluntary participation
Some face-to-face, others on Zoom (recorded)
Assessment
Assignments
Assignment Project Exam Help
Final Exam
8 MCQ, 4 extended response
Four assignments, released approx bi-weekly Each consists of 4 questions
Each weighted 15% of course mark
WeChat: cstutorcs
Weighted 40% of course mark
Forum participation
Up to 5 bonus marks
Recommended textbook
AsKsleingberng amnd Teardnos:tAlPgorrithom jDesicgnt Exam Help paperback edition available at UNSW Bookshop
excellent: very readable textbook (and very pleasant to read!);
not so good: as a reference manual for later use.
An alternative textbook
WeChat: cstutorcs
Cormen, Leiserson, Rivest and Stein: Introduction to Algorithms 3rd edition also available at UNSW Bookshop, 4th edition not yet
excellent: to be used later as a reference manual;
not so good: somewhat formalistic and written in a rather dry style.
Assignment Project Exam Help
Changes from last term:
tutor-led help sessions, recordings and F2F
assignment question format
WeChat: cstutorcs
Feedback is always welcome, e.g. myExperience survey
feedback post on Ed (can post anonymously) email
Table of Contents
Assignment Project Exam Help
2. Solving problems using algorithms
WeChat: cstutorcs
4. An example of the role of proofs 5. Puzzles
CS Help, Email: tutorcs@163.com
Introduction
What is this course about?
It is about designing algorithms for solving practical problems. Assignment Project Exam Help
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
hus, 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 wa’l-muqabala”.
Introduction
Assignment Project Exam Help
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;
WeChat: cstutorcs
the action of each step gives the same result whenever this step is executed for the same input.
Introduction
Why should you study algorithm design?
Assignment Project Exam Help
Can you find every algorithm you might need using Google?
To learn techniques which can be used to solve new, unfamiliar problems that arise in a rapidly changing field.
WeChat: cstutorcs
Course content:
a survey of algorithm design techniques
particular algorithms will be mostly used to illustrate design
techniques
emphasis on development of your algorithm design skills
Example: Two Thieves
Assignment Project Exam Help
Alice and Bob have robbed a warehouse and have to split a pile of
items without price tags on them. Design an algorithm to split the
pile so that each thief believes that they have got at least half the
WeChat: cstutorcs
Alice splits the pile in two parts, so that she believes that both parts are of equal value. Bob then chooses the part that he believes is no worse than the other.
Example: Two Thieves
AsWseiagre anssumingetnhattit’sPalwraoys jpoessciblettoEsplxit uap tmhe looHt inteo lp whatever fraction we like. With discrete items this is more
complicated than it might appear!
If there are n items, and Alice values the ith at vi dollars, can Alice
WeChat: cstutorcs
efficiently split the loot into two equal piles?
There is no known algorithm that is significantly more efficient than the brute force (try all choices, of which there are approx 2n).
Example: Three Thieves
Assignment Project Exam Help https://tutorcs.com
Alice, Bob and Carol 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 they have got at
least one third of the loot?
WeChat: cstutorcs
Example: Three Thieves
Assignment Project Exam Help
The problem is much harder with 3 thieves!
Let us try do the same trick as in the case of two thieves. Say
Alice splits the loot into three piles which she thinks are of equal value; then Bob and Carol each choose which pile they want to take.
WeChat: cstutorcs
If they choose different piles, they can each take the piles they have chosen and Alice gets the remaining pile; in this case clearly each thief thinks that they got at least one third of the loot.
Code Help, Add WeChat: cstutorcs
Example: Three Thieves
Assignment Project Exam Help
But what if Bob and Carol choose the same pile?
One might think that in this case, Alice can pick either of the
other two piles, after which the remaining two piles are put
together for Bob and Carol to split them as in the earlier
WeChat: cstutorcs
problem with only two thieves.
Unfortunately this does not work!
Example: Three Thieves
Assignment Project Exam Help
Suppose that Alice splits the loot into three piles X, Y, Z, and that Bob thinks that
X = 50%, Y = 40%, Z = 10% of the total value, while Carol thinks that
WeChat: cstutorcs
X = 50%, Y = 10%, Z = 40%.
Example: Three Thieves
Assignment Project Exam Help
Clearly both Bob and Carol choose pile X, so Alice can choose pile Y or Z.
However, if Alice picks pile Y , then Bob will object that (in his eyes) only 60% of the loot remains, so he is not guaranteed to get at least one-third of the total.
WeChat: cstutorcs
If instead Alice picks pile Z, then Carol will object for the same reason.
What would be a correct algorithm?
Example: Three Thieves
Assignment Project Exam Help
Alice makes a pile X which she believes is 1/3 of the whole loot.
Alice proceeds to ask Bob whether he agrees that X ≤ 1/3. https://tutorcs.com
If Bob says YES, then he would be happy to split the remainder of the loot (worth ≥ 2/3) with one other thief.
Alice then asks Carol whether she thinks that X ≤ 1/3. WeChat: cstutorcs
If Carol says NO, then Carol takes X, and Alice and Bob split the rest.
If Carol says YES, then Alice takes X , and Bob and Carol split the rest.
Example: Three Thieves
Algorithm (continued)
AssiWghnat mif Boeb snaystNOP? rThoenjAelicce vtaluEes pxile aX mat 1/3Hof tehelp total, but Bob believes it to be > 1/3.
Now we ask Bob to reduce the pile X until he believes it to be 1/3 of the total. Alice values the new pile as < 1/3, so she
https://tutorcs.com
is happy to split the remainder of the loot (worth > 2/3) with one other thief.
This is exactly the situation we had before, but with Alice and
WeChat: cstutorcs
Bob’s roles reversed!
Bob asks Carol whether she thinks that X ≤ 1/3.
If Carol says NO, then Carol takes X, and Alice and Bob split the rest.
If Carol says YES, then Bob takes X , and Alice and Carol split the rest.
Example: n Thieves
Assignment Project Exam Help
Try generalising this to n thieves. https://tutorcs.com
WeChat: cstutorcs
There is a nested recursion happening even with 3 thieves!
Table of Contents
Assignment Project Exam Help
2. Solving problems using algorithms
WeChat: cstutorcs
4. An example of the role of proofs 5. Puzzles
The role of proofs in algorithm design
Assignment Project Exam Help
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?
WeChat: cstutorcs
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!
Example: Merge-Sort
Assignment Project Exam Help
Merge-Sort(A,l,r) *sorting A[l..r]*
1. 2. 3. 4. 5.
ihf lt