ADVANCE ALGORITHM TOPICS
Nguyễn An Khương
Trần Tuấn Anh
Lê Hồng Trang
1. Lecturers
Nguyen An Khuong, Ph.D Tran Tuan Anh, Ph.D Le Hong Trang, Prof
nakhuong@[Link] trtanh@[Link] lhtrang@[Link]
• Originating & the need for algorithms to solve a real
problem.
• Absolute (Complete) or relative algorithms are less
important than effectiveness in a specific environment.
2. Introduction • Understanding the strengths and weaknesses of the
Expectation most straightforward algorithm is still more effective
than arbitrarily using the most powerful one.
• Any algorithm depends on how the data is organized.
Think about how to store and organize before doing the
algorithm.
• Logical coordination always shows efficiency in
algorithm organization.
• If you want to become an in-depth researcher, learn the
most basic things, and understand the best.
2. Introduction 1. Suggest some practical problems encountered - some
possible approaches in practice that teachers encounter.
Approach to the 2. Provides some overviews of algorithms related to these issues
lesson/course 3. Provides some “interesting” basic/modern algorithm topics
requiring good techniques.
4. Propose exercises and assign them to students. The exercises
are often highly applicable and require students to do
practical research.
3. Resources 1. There are many resources that talk about basic/classical algorithms
effectively:
[Link]
[Link]
[Link]
[Link]
2. This lesson does not have a specific textbook, mainly discussing slide
content and other related documents. However, there are some basic
documents that are quite good
• Advanced-Algorithms-and-Data-Structures, Marcello La Rocca
• ADVANCED ALGORITHMS , Anupam Gupta
3. Programming languages
Python, Matlab…
4. Syllabus
overview
HCMUT
4. Syllabus
overview List of Topics:
• Hasing
Columbia University • Sketching/Streaming
• Nearest Neighbor Search
• Graph Algorithms
• Spectral Graph Algorithms
• Optimization: linear programming, gradient descent, IPM
• Multiplicative Weights Update, online algorithms
• Large-scale computation models
4. Syllabus
overview
Advanced algorithm topics chosen from:
The University of • Dynamic Programming,
• Linear Programming,
Adelaide • Matching,
• Max Flow / Min Cut,
• P and NP,
• Approximation Algorithms,
• Randomized Algorithms,
• Computational Geometry.
4. Syllabus
• Week #1: Spanning Trees
overview • Week #2: Shortest-Path Trees
• Week #3: Shortest-Path Trees (Finish), Matchings
Carnegie Mellon
• Week #4: Matchings (Contd), Measure Concentration (Start)
University • Week #5: Measure Concentration (Contd)
• Week #6: Experts (and Submodularity)
• Week #7: Online Learning (Experts) and First-Order Convex Optimization
• Week #8: Convex Optimization (Contd.)
• Week #9: Approximation and Online Algorithms
• Week #10 & 11: Listener's Choice
Week #1: logistics, course topics, word RAM, predecessor, van Emde Boas, y-fast tries.
Week #2: fusion trees, word-level parallelism, most significant set bit in constant time
4. Syllabus Week #3: hashing: load balancing, k-wise independence, chaining, linear probing
Week #4: symmetrization, hashing: linear probing (5-wise indep.), bloom filters, cuckoo hashing, bloomier
filters
overview Week #5: hashing: cuckoo hashing analysis, power of two choices
Week #6: amortized analysis, binomial heaps, Fibonacci heaps.
Week #7: online algorithms, competitive analysis, move-to-front, paging
Week #8: randomized paging, packing/covering linear programs, weak duality, approximate complementary
Havard University slackness, primal/dual online algorithms
Week #9: approximation algorithms via dual fitting (wrap-up), LP integrality gaps, definitions of
PTAS/FPTAS/FPRAS, PTAS for knapsack
Week #10: FPTAS (knapsack), FPRAS (DNF counting), semidefinite programming, Goemans-Williamson
MAXCUT algorithm
Week #11: topic modeling, nonnegative matrix factorization
Week #12: approximate nearest neighbor, locality sensitive hashing
Week #13: linear programming: standard form, vertices, bases, simplex
Week #14: simplex wrap-up, strong duality, complementary slackness, ellipsoid, intro to interior point
Week #15: path-following interior point, first order methods (gradient descent).
Week #16: second order methods (Newton's method), path-following interior point wrap-up
Week #17: learning from experts, multiplicative weights
Week #18: linear programming via multiplicative weights, flows, augmenting paths
Week #19: scaling for max flow, blocking flow
Week #20: preferred path decomposition, link-cut trees
Week #21: heavy-light decomposition, O(log2n) amortized analysis of link-cut trees, min cost max flow,
min cost circulation, shortest augmenting paths
Week #22: more efficient exponential-time algorithms: exponential divide-and-conquer (TSP), pruned brute
force (3-SAT), Schöning's algorithm (3-SAT), inclusion-exclusion (k-colorability)
Week #23: zeta transform, Möbius inversion, streaming algorithms, necessity of randomization and
approximation, distinct elements
• Bit Tricks: Word-level Parallelism. Transdichotomous Model. o(n \log n) Integer Sorting.
4. Syllabus •
•
String Algorithms: Rabin-Karp Fingerprinting Algorithm. Suffix Trees.
Maximum Flows: Augmenting Paths and Push-Relabel Methods. Minimum Cost Flows.
Bipartite Matching.
overview • Linear Programming: Formulation of Problems as Linear Programs. Duality. Simplex, Interior
Point, and Ellipsoid Algorithms.
• Online Algorithms: Ski Rental. River Search Problem. Paging. The k-Server Problem. List
MIT •
Ordering and Move-to-Front.
Approximation Algorithms: One Way of Coping with NP-Hardness. Greedy Approximation
Algorithms. Dynamic Programming and Weakly Polynomial-Time Algorithms. Linear
Programming Relaxations. Randomized Rounding. Vertex Cover, Wiring, and TSP.
• Fixed-Parameter Algorithms: Another Way of Coping with NP-Hardness. Parameterized
Complexity. Kernelization. Vertex Cover. Connections to Approximation.
• Parallel Algorithms: PRAM. Pointer Jumping and Parallel Prefix. Tree Contraction. Divide and
Conquer. Randomized Symmetry Breaking. Maximal Independent Set.
• External-Memory Algorithms: Accounting for the Cost of Accessing Data from Slow
Memory. Sorting. B-trees. Buffer Trees. Cache-oblivious Algorithms for Matrix
Multiplication and Binary Search.
• Computational Geometry: Convex Hull. Line-segment Intersection. Sweep Lines. Voronoi
Diagrams. Range Trees. Seidel’s Low-dimensional LP Algorithm.
• Streaming Algorithms: Sketching. Distinct and Frequent Elements.
4. Syllabus
overview
Module 1: Flows in Networks
Coursera
Module 2: Linear Programming
Module 3: NP-complete Problems
Module 4: Coping NP-completeness
Module 5: Streaming Algorithms (Optional)
5. Content
Section Exe Week Content Lecturer
1 9 Connected Component Analysis in image processing Trần Tuấn Anh
2 20% 10 Address classification Trần Tuấn Anh
3 11 Trie & Dynamic programming Trần Tuấn Anh
4 12 Trie & Dynamic programming Trần Tuấn Anh
Attend every class and ask yourselves
why you are here? What is your goal?
Keep in your mind that we will not teach a topic twice.
You must review everything you have studied in class.
Read the textbooks carefully and solve the exercises
therein as much as possible ...
5. Requirements
Teamwork and coding skill
Respect each other
Q&A