[SOLVED] CS data structure algorithm Lecture 13: Summary

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 U 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 hardestimo)
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. Dont waste time looking these up during the exam
Have a template ready to go, especially if you are using LaTeX. Dont 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