Introduction and Background Advanced Algorithms & Data Structures
Introduction and background
Introduction and Background Advanced Algorithms & Data Structures
COMP4500/7500
Aug 4, 2020
1/12
Introduction and background
Overview of this week
Overview of the material.
Administration: assessment, consultation, etc. Recap of algorithm analysis and asymptotic notation. Mathematical background.
2/12
Introduction and background
Course Aims
Expand your abilities to analyse,
critique, design, and implement
advanced data structures and algorithms.
3/12
Introduction and background
Assumed background
The prerequisite course is COMP3506/7505.
We will be assuming that you have: programming experience:
including basic data structures and recursive procedures;
familiarity with a programming language:
we will be using java for assignment tasks
mathematical background:
familiarity with proofs by mathematical induction; and knowledge of calculus, including differentiation, limits, L’Hôpital’s rule, and summations.
4/12
Introduction and background
Motivation
Practical basis for creating more efficient algorithms. Theoretical basis for justifying your choice of algorithms. Improve your problem-solving skills.
A prerequisite for looking for a job at Google, Oracle, etc
5/12
Introduction and background
Current areas research
Four areas currently under competitive research and development:
Distributed/parallel algorithms (multi-core architectures) Neural networks/pattern recognition
Bioinformatics Quantum computing
6/12
Introduction and background
Course outline
Topics
1
Asymptotic notation
Basic concepts of analysis
Graph algorithms
Complex data structure; multiple representations
Dynamic programming
Vast speed up by using arrays; also elegant
Greedy algorithms
Straightforward and efficient for certain types of problems
Amortised analysis
Advanced analysis technique for data types
Complexity classes
Broad theoretical concepts about computation
Randomised algorithms
A class of algorithms that avoid some inefficiencies
2
3
4
5
6
7
7/12
Introduction and background
Course outline by week
1
4/8/2020: Background and asymptotic notation.
11/8/2020: Solving recurrences; divide-&-conquer algorithms.
18/8/2020: Graph algorithms 1.
25/8/2020: Graph algorithms 2.
1/9/2020: Graph algorithms 3
8/9/2020: Graph algorithms 3 cont. and Dynamic programming 1.
Assignment 1 Published
15/9/2020: Dynamic Programming 2. Midterm Exam
22/9/2020: Midterm Feedback, and Assignment 1 consultation
29/9/2020: Mid-semester break, Assignment 2 Published
6/10/2020: Greedy algorithms. Asst 1 due Monday 4pm.
13/10/2020: Amortised analysis.
20/10/2020: Complexity classes.
27/10/2020: Randomised algorithms. Asst 2 due Monday 4pm.
3/11/2020: Revision.
2
3
4
5
6
7
8
9
10
11
12
13
8/12
Introduction and background
Assessment
The course profile has more detail and takes precedence. COMP4500 and COMP7500 differ in requirements.
1
Mid-semester exam
Worth 10%
lecture 2 (+ adjacent tutorial hour) of week 7.
Assignment 1.
Worth 20%
Due 4pm Monday 16th Sep.
Assignment 2.
Worth 20%
Due 4pm Monday 14th Oct.
Final exam.
Worth 50%
Exam period.
2
3
4
9/12
Introduction and background
Other administration
Course textbook: Cormen et al. (CLRS) Revision exercises (tutorials) from week 2.
You can use the COMP4500/7500 Piazza forum to discuss course material.
Lecturer consultation – Email
Slides: I’ve used slides from previous years, which are a combination of slides from earlier lecturers of the course and the MIT open coursework system.
10/12
Introduction and background
Overview of this week
1
Recap of algorithm analysis Asymptotic notation Mathematical background
2
3
11/12
Introduction and background
Recap
Design and analyse efficient algorithms
Analysis: bounded below (Ω), bounded above(O), and bounded tightly (Θ).
Constant terms can be disregarded (for large enough inputs)
Summations useful for analysing total cost of an algorithm
12/12