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.
https://www.youtube.com/playlist?list=PLgA1KNw3ovCJenw1AayNOAlL-iDtsjJ1m (2018 latest recordings)
https://www.youtube.com/playlist?list=PL30_65ribyvp1cbLJ9Ed4E8I6aRVNq5S2 (2017 – has a bit more on theory)
DUE DATE TO SUBMIT YOUR MAJOR PROJECT IS 14TH 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!)
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:
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 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
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
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.