Lecture 13: Summary
The University of Sydney
Page 1
Please remember to fill in the unit of study evaluation
– COMP3027: https://student- surveys.sydney.edu.au/students/complete/form.cfm?key=uss22 1795
– COMP3927: https://student- surveys.sydney.edu.au/students/complete/form.cfm?key=uss22 1804
What was good? What was bad?
– Tutor and tutorials
– Were the extra resources, e.g. exemplars, useful?
– Assignments, feedback
The University of Sydney
Page 2
Aims of this unit
This unit provides an introduction to the design and analysis of algorithms. We will learn about
– (i) how to reason about algorithms rigorously: Is it correct? Is it fast? Can we do better?
– (ii) how to develop algorithmic solutions to computational problems Assumes:
– basic knowledge of data structures (stacks, queues, binary trees) and programming at level of COMP2123
– discrete math (graphs, big O notation, proof techniques) at level of MATH1004/MATH1064
The University of Sydney Page 3
University of Sydney
X
How to design algorithms
Step 1: Understand problem
Step 4: Better understanding of problem
Step 2: Start with simple alg. Step 5: Improved alg.
Step 3: Does it work? Is it fast?
No Yes
The University of Sydney
Page 4
Problem
Algorithm
Analysis
DONE!
Main Themes
– Induction:
– Proof technique
– Algorithm design method: Greedy, Divide-and-conquer and DP
– Reduction:
– Algorithm design: Reduction to flows
– Hardness: Reduction from NP-complete problems
The University of Sydney
Page 5
Overview – Greedy Algorithms
– Greedy algorithms
– Greedy technique
– Standard correctness proof: exchange argument
– Applications: Scheduling, MST, Dijkstra (incl. properties)
job ir+1 finishes before Jr+1
Greedy: OPT:
i1
i1
ir
ir+1
J1
J2
Jr
Jr+1
…
…
The University of Sydney
Page 6
Why not replace job Jr+1 with job ir+1?
Overview – Divide and Conquer
– Divide-and-Conquer algorithms
– –
– –
General technique: divide, solve and combine
Recursion: How to state and solve a recursion (unrolling, Master method)
Standard correctness proof: Induction
Applications: Mergesort, Inversions, Closest Pairs of Points
A
L
G
O
R
I
T
H
M
S
divide
O(1)
A
L
G
O
R
I
T
H
M
S
sort
2T(n/2)
A
G
L
O
R
H
I
M
S
T
merge
O(n)
A
G
H
I
L
M
O
R
S
T
The University of Sydney
Þ T(n) = O(n) + 2T(n/2) = O(n log n) Page 7
Overview – Dynamic programming
– Dynamic programming
– General technique: Subproblems and recurrence
• Define subproblems
• Define recurrence linking subproblems
– Correctness proof: Induction
– Applications: Knapsack, weighted scheduling, RNA, Bellman-Ford,…
i
match bj-5 and bj
j
The University of Sydney
Page 8
Overview – Flow Networks
– Flow networks
– Properties of flow network: max flow, min cut, integer lemma,…
– General technique: reduce to a flow network
– Correctness proof: Solution for X Û Solution for FN
– Applications: matching, edge-disjoint paths, circulation,…
295
10
15 15
sources 5 3 8 6 10 tsink
4
10
capacity
The University of Sydney
Page 9
15
46
10
15 4 30 7
Overview – NP-completeness
– Complexity
– Polynomial-time reductions
• Gadget reductions
– Classes: P, NP, NP-complete, NP-hard
– How to prove that a problem belongs to P/NP/NP-complete – Understand the NP-complete problems in lectures.
Algorithm for X
Instance of Y
f(I)
Yes for f(I) No for f(I)
Transforms instance of X to instance of Y
Algorithm for Y
Instance of X
I
Yes for I
No for I
The University of Sydney
Step 1
Step 2 Page 10
Overview – Coping with hardness
– Coping with hardness
– Understand the basic concepts:
• Exponential time algorithms • Restricted instances
• Approximation algorithms
The University of Sydney
Page 11
Exam
Time: 10 minutes reading time 2 hours
Number of problems: 4 (ordered from easiest to hardest…imo)
2 short-answer questions assessing surface-level knowledge and ability to analyse
correctness and running time of a given algorithm
2 design questions: greedy, divide-and-conquer, dynamic programming, flows, NP- completeness, reductions
Single Canvas site Final_Exam for: COMP3027_COMP3927.
See Practice Final on Ed. No solutions provided. Discuss your solutions on Ed.
The University of Sydney Page 12
Exam Conditions
Open-book: You are only allowed to refer to your own notes, and course materials hosted on Canvas/Ed such as lecture slides, tutorial sheets. You are not allowed to refer to any other materials.
You must do exam on your own. No communication with anyone else. Submissions must be type-written using LaTeX or word-processing software.
Hand-written solutions not accepted. Exceptions allowed for illustrations. Submit only your answers. Do not copy the questions.
Any breaches in academic integrity may result in the University mandating ProctorU in the future.
The University of Sydney Page 13
Exam Tips
Practice on problems under exam conditions
Memorise key definitions, proof techniques, and make your own cheat-sheet. Don’t waste time looking these up during the exam
Have a template ready to go, especially if you are using LaTeX. Don’t waste time with LaTeX compilation errors during the exam.
Resist the temptation to write a perfect solution on the first go. Have something written for all the questions and then return to edit.
Caution: Do not share cheat-sheets and templates.
The University of Sydney Page 14
More algorithms?
– COMP3530:DiscreteOptimization(2021S2) Lecturer: Julian Mestre
– COMP5045:ComputationalGeometry(2021S1) Lecturer: Joachim Gudmundsson
– Otheropportunities:
– SSP, summer projects
Please get in touch with us for more information The University of Sydney
Page 15
Please remember to fill in the unit of study evaluation
– COMP3027:https://student- surveys.sydney.edu.au/students/complete/form.cfm?key=uss221795
– COMP3927:https://student- surveys.sydney.edu.au/students/complete/form.cfm?key=uss221804
What was good? What was bad?
– Tutorandtutorials
– Weretheextraresources,e.g.exemplars,useful?
– Assignments,feedback
Thanks for taking the class! Good luck on the exam!
The University of Sydney
Page 16