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)

 

Midterm Practice Questions 

 

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.

 

Final Practice Questions 

 

 

Lecture Notes  (subject to revisions and updates!)

Review Material:

Probability refresher 

Linear Programming refresher 

_____________________________________________________________________________________________

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): 

           paper 1       paper 2

 

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

Homework #1

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.