# 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 Û 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