Welcome to COMP4121: Advanced Algorithms
Trimester 3, 2023
Lecturer: Aleks Ignjatovic (ignjat@cse.unsw.edu.au;
office: 504 in K-17)
Office
hours: by appointment, send me a Zoom
invite
Lectures:
Day |
Time |
Location |
Weeks |
Instructor |
Tue |
12:00 - 14:00 |
E19 Patricia O'Shane 104 (K-E19-104) |
1-10 |
Apro A
Ignjatovic |
Fri |
12:00 - 14:00 |
Law Theatre G04 (K-F8-G04) |
1-10 |
Apro A
Ignjatovic |
This course is a continuation
of our introductory algorithms courses
COMP3121/3821/9101/9801. We will cover some of the basic randomised algorithms
and data structures, such as randomised hashing, skip-lists, order statistics
and Karger's randomised Min Cut algorithm. We will then look at the Markov
chains and the Google PageRank algorithm, the Hidden Markov Models
and the Viterbi Algorithm, and then cover in quite a detail a variety of other
algorithms important to the present day practice, such as the recommender
systems as well as some of the algorithms used in Data Science. We will cover
parts of three books: our COMP3121/3821/9101/9801 textbook Algorithm Design by
Kleinberg and Tardosh, Networked Life by Mung
Chiang and Foundations of Data Science by
Blum, Hopcroft and Kannan. The first two books are available in the bookstore.
A preprint of the third book is available for free at https://www.cs.cornell.edu/jeh/book.pdf
The grade will be based on a
final (50%) and a major project (50%).
The learning outcomes are:
(1) understanding and mastering more advanced algorithm design techniques and
(2) familiarising with some of the most important present day algorithms, such
as those used in Data Science, which is, nowadays, one of the most important
fields of Computer Science, presently in high demand by industry employers.
Review
Material:
Linear
Programming refresher - slides Linear
Programming refresher - Lecture Notes
Suggestions for topics for the
Major Project
Practice Problems (updated 10/11/2021)
Solutions to Practice Problems (updated 10/11/2021)
Review summary (updated 10/11/2021)
Final exam 2023 will be posted here on Wednesday November 29, at 9:45am. You have 3 hours unless
you have an ELS provision in which case you will get extra time.
You should email me
back your solutions using your UNSW email at 1pm at ignjat@cse.unsw.edu.au.
DUE DATE TO
SUBMIT YOUR MAJOR PROJECT : November
24 at Midnight sharp. Please email me zipped your project report and associated
files such as implementations, test data etc.
MAJOR
PROJECT examples from past years (right click on the link and choose ‘Save
link As…’ to download the zip file)
Lecture Notes (subject to updates,
please make sure you download the version after the class when the material has
been covered)
Order statistics short
version
Karger's Min Cut algorithm
short version
- COMP3121
Lecture slides on MaxFlow/MinCut
for those who have not studied this
Universal
and perfect hashing
short version
Gaussian
Annulus, Random projection and Johnson – Lindenstrauss lemmas short version
-- please also read pages 12-26 in BHK (https://www.cs.cornell.edu/jeh/book.pdf)
Clustering
algorithms short
version
Google PageRank and Markov Chains (lecture notes with more details)
Google PageRank and Markov Chains SLIDES short
version
Security
application of the PageRank (a paper from the major project by former 4121
students)
Hidden
Markov Models and the Viterbi Algorithm
(lecture notes with more details)
Hidden
Markov Models and the Viterbi Algorithm slides short
version
Transmit
power control in cellular networks
short
version
Recommender
Systems short
version
Examples
for the flexi week short
version
A brief
sketch of the Singular Value Decomposition (SVD) short
version
A Mathematica depiction of a SVD
transformation
Low rank approximations of the Lena image
large
integer multiplication short
version
DFT, FFT and
convolution short
version
DFT, DCT and convolution (lecture notes
with more details)
A Mathematica implementation of DFT and DCT (Mathematica is free for UNSW students and
available at the UNSW IT website)
A Mathematica implementation of DFT and DCT (pdf)
A (slow) Mathematica implementation of JPEG
A Mathematica implementation of Gaussian
smoothing (Mathematica is free for
UNSW students and available at the UNSW IT website)
Introduction
to signal processing and MP3 sound compression short
version
Intro to signal processing (lecture notes
with more details)
Introduction
to signal processing summary and MP3 sound compression short
version
Visit https://au.prosple.com/graduate-employers/dolby-australia and
https://www.themuse.com/profiles/dolby/location/sydney-australia
I can get you in touch with them if you are interested.
OPTIONAL
MATERIAL NOT COVERED IN CLASS
Voting
and Customer Feedback Aggregation
short
version
Voting Algorithms (lecture notes with more details)
A Mathematica implementation of the adaptive voting
algorithm (Mathematica is free for
UNSW students and available at the UNSW IT website)
Iterative
Filtering (lecture notes with more details)
Recap
of Fourier series and integrals
short
version
Every term,
student feedback is requested in a survey using UNSW myExperience
online survey system where the feedback will be used to make improvements to
the course. Students are also encouraged to provide informal feedback during
the session, and to let course staff know of any problems as soon as they
arise. Other possible contacts including the School Grievance officer or one of
the student representatives. Suggestions will be listened to openly,
positively, constructively, and thankfully, and every reasonable effort will be
made to address them. Feedback from last offering indicated students were quite
happy with updated content which included algorithms for Data Science and
Machine Learning. Consequently, such material will be emphasised in the
subsequent deliveries of this course.
CRICOS
Provider 00098G.