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:

 

Probability refresher 

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 2020

FINAL EXAM 2020 SOLUTIONS

FINAL EXAM 2021

FINAL EXAM 2021 SOLUTIONS

FINAL EXAM 2023

 

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)

Introduction 

preliminaries                                         short version        

 Order statistics                                         short version                             

   

 Skip lists                                                   short version

 

Database access                                       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 

 

racoons and possums   

 

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

 

 A paper on MP3

 

 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.