The University of Sydney Page 1 COMP9007 Algorithms Week 12: Recap and Exam Review Dr. André van Renssen School of Computer Science The University of Sydney Page 2 Quick announcements Fill out online Unit of Study Survey – https://student-surveys.sydney.edu.au/students/ – Use the free text to help us make this better for next years students – “Pay it forward” The University of Sydney Page 3 Week 12 Tutorial There won’t be a tutorial sheet this week, but you can use this last tutorial to ask questions about any material covered during the semester The University of Sydney Page 4 Week 12 Quiz Quiz 10 will be about the final. Unlike previous quizzes you will be able to attempt it multiple times. It’s available until the start of the exam. The University of Sydney Page 5 Looking back We covered a lot of ground! The University of Sydney Page 6 Core concept 1: Abstraction layers Abstract Data Type Data Structure Computer code Problem definition Algorithm Computer code The University of Sydney Page 7 Core concept 2: Algorithm analysis A principled framework for evaluating algorithms: – measuring performance of resource use – proving correctness These should inform your design and implementation choices The University of Sydney Page 8 Learning outcomes 1. Demonstrate knowledge of fundamental algorithms for several problems, including graphs, greedy algorithms, divide-and- conquer, dynamic programming, and network flow 2. Collaborate in lectures/tutorials and exchange of ideas to solve algorithmic problems 3. Understand and analyze given algorithms as well as ability to design algorithmic solutions for given problems 4. Practice your writing presentation skills The University of Sydney Page 9 What is examinable? Everything from the lectures, the tutorials, the quizzes, the assignments. Exceptions to this rule: – when explicitly labeled as non-examinable In general though, if it happened during this unit, you are expected to know about it! Focus on the things we put most emphasis on, as seen in tutorials and assignments The University of Sydney Page 10 Final Exam Structure 2 hours writing plus 10 minutes reading 5 questions worth in total 60 points Worth 60% of overall COMP9007 grade Final exam has a 40% barrier The University of Sydney Page 11 Do’s and Don’ts Open book exam: – Can refer to slides, tutorial solutions, assignment solutions, books used in the unit – Making a 2-page summary is highly recommended – Can’t use the internet to look things up – Never copy text verbatim from anywhere, including the slides (few points and potential academic dishonesty) – If you refer to anything from the permitted material, write in your own words Type your answers and submit it as an assignment in Canvas Handwritten/scanned answers will not be accepted. Start your submission with your student ID – Don’t include your name The University of Sydney Page 12 Problem 1 10 points Tracing algorithms/data structures on a given example Easy problem. Make sure you nail it! The University of Sydney Page 13 Problem 2 10 points Analysis of given algorithms Easy problem. Make sure you nail it! The University of Sydney Page 14 Problem 3 15 points Design or modify an ADT Medium difficulty problem. Remember to: – Describe your approach – Prove correctness – Analyze complexity The University of Sydney Page 15 Problem 4 15 points Design an algorithm for a “completely new” problem Medium/Hard problem. Remember to: – Describe your algorithm – Prove correctness – Analyze complexity The University of Sydney Page 16 Problem 5 10 points Design an algorithm for a “completely new” problem Hard problem. Remember to: – Describe your algorithm – Prove correctness – Analyze complexity The University of Sydney Page 17 Problem 3, 4 & 5 Check if you’re supposed to use a specific technique: – “design a greedy algorithm” – “design a dynamic programming algorithm” Let the running time requirement guide you: – If we ask O(1) time, this limits your options considerably – If we ask O(n) time, you can’t sort the input The University of Sydney Page 18 Exam technique Read all questions to see which ones you can answer quickly Plan how you will allocate time (wisely) Start with easy problems and move to harder ones Write clearly and efficiently – Start with outline/bullet points, then expand if you have time – No need for fancy style or overly formal Figures take a lot of time to draw – Describing in text is faster (a graph is a bunch of vertices and edges) – No scanned drawings allowed The University of Sydney Page 19 Pragmatic Advice – Practice submitting a file in Canvas! – Be alone in your room to avoid distractions – Let housemates know when your exam is to avoid distractions – Bring water – Have clothing in layers – Start your submission with your student ID (can prepare file in advance) – Do not write your name on the exam (marking is anonymous) – Breathe – Relax Good Luck!!!
欢迎咨询51作业君
