Welcome to COMP4121:
Advanced Algorithms - Session 2, 2018

Lecturer: Aleks Ignjatovic

Wed
10:00 - 11:30 Macauley Theatre (K-E15-1027) |

Fri 09:00 - 10:30 Mathews Theatre D (K-D23-304)

* *

In
this course we will continue our study of algorithm design
which we started in COMP3121. We will study in detail some of the most
important algorithms today, highlighting the techniques used in their design,
often shared by several algorithms presented, such as fixed points of linear
and non-linear mappings, matrix techniques, power method, as well as
representation of discrete and continuous data in various orthogonal bases. The
grade will be based on a midterm (50%) and a final (50%), or a Major project
(50%) and Final (50%) – the choice is yours. We will cover parts of *Networked Life *by Mung
Chiang, as well as some research papers. The book is available in the bookstore
and it is wonderfully written, like very few CS books. The learning outcomes
are: (1) understanding and mastering more advanced algorithm design techniques
and (2) familiarizing with some of the most important present day algorithms.

Class
recordings:

https://www.youtube.com/playlist?list=PLgA1KNw3ovCJenw1AayNOAlL-iDtsjJ1m (2018 latest recordings)

https://www.youtube.com/playlist?list=PL30_65ribyvotOeh0CXGIFu1VAS3lEXZi (2018)

https://www.youtube.com/playlist?list=PL30_65ribyvp1cbLJ9Ed4E8I6aRVNq5S2 (2017 – has a bit more on theory)

**DUE DATE TO SUBMIT YOUR MAJOR PROJECT IS 14 ^{TH} OF NOVEMBER
2018.**
Please keep in mind that I cannot give any extensions; I will barely have
enough time to mark them and the finals before the deadline to submit the
marks.

* *

*Lecture Notes ***(subject to revisions and updates!)**

*Review Material:*

_____________________________________________________________________________________________

*Topic 1: The PageRank,
Markov chains and the Perron Frobenius
theory; **COMP4121_Lecture_Notes_1.pdf*

Please read also Chapter 3 in the textbook and look at
the examples and exercises there, to fully understand the PageRank.

Two papers on computer security
based on major projects of two students for this class (Mohsen Rezvani and Verica Sekulic):

*Topic 2: More on Markov chains:
Hidden Markov Models and the Viterbi Algorithm; **COMP4121_Lecture_Notes_2.pdf*

*Topic 3: More fixed point
iterative algorithms: voting and ranking; **COMP4121_Lecture_Notes_3.pdf*

Papers on voting, all also
originating from this class:

Paper on voting 1 Paper on
voting 2 Paper
on voting 3 . .

You might want to implement the
voting algorithms from the above papers in your favorite language and play with
them; below is a Mathematica implementation

Mathematica
implementation of the voting algorithm

*Mathematica* software is free for UNSW students, and you can
download it at https://www.it.unsw.edu.au/students/software/index.html;
you need to be connected via UNSW VPN https://www.it.unsw.edu.au/students/software/index.html
to its UNSW license server or you can request a standalone version for your
home computer by first creating a Wolfram account at https://user.wolfram.com/portal/login.html.
Once you try it, you will always use it – you can verify your math homework of
any kind; *Mathematica*
“knows” an amazing amount of math, up to a PhD level, and it takes no time to
learn how to use it; it is 100% intuitive and a very high level programming
environment in which you often do not have to program at all but you only write
formulas in their usual form found in textbooks, using convenient palettes.

*Topic 4: More fixed point
iterative algorithms: Iterative Filtering (IF) algorithms: **COMP4121_Lecture_Notes_4.pdf*

IF paper 1 IF paper 2 (two papers by a former student who took
this class a couple of years ago)

Mathematica
Implementations of IF algorithms

*Topic 5: Recommender systems:
please read the corresponding chapter (How does Netflix recommend movies?”) in our textbook “Networked Life”*

*Topic 6: Linear Programming; **COMP4121_Lecture_Notes_6.pdf*

*Topic 7: Transmit power control
in cellular networks and error correction codes; **COMP4121_Lecture_Notes_7.pdf*

*Topic 8:
Fundamentals of signal processing I: why does JPEG use the Discrete Cosine
Transform rather than just the Discrete Fourier Transform? ** **COMP4121_Lecture_Notes_10.pdf*

** **Mathematica
Implementations of the DFT and DCT and data compression

*Topic 9:
Fundamentals of signal processing I: Orthogonal Systems **COMP4121_Lecture_Notes_9.pdf*

*Topic 10: Fundamentals of signal processing II: The Shannon Sampling
Theorem; **COMP4121_Lecture_Notes_11.pdf*

·
*Optional material:
Orthogonal systems**: ** **COMP4121_Lecture_Notes_9.pdf*

·
*An
``interesting application’’ of **``convolution''*

·
*A paper on
MP3: **MP3 paper 1*

·
*Another
paper on MP3: **MP3 paper 2*

*Topic 11: Local Search*

·
*Reading material:
** *** Local search chapter** Please read the whole chapter except 12.6
Classification via Local Search

*CRICOS Provider 00098G.*