Advanced algorithm and complexity - L2H (S2)

Course Description:

Welcome to Advanced Algorithms & Complexity II! This course builds on foundational knowledge of algorithms and computational complexity, diving deeper into advanced techniques for designing, analyzing, and proving the correctness of algorithms. You will explore key topics such as recursion, data structures, algorithm complexity, and formal proofs of algorithmic correctness. By the end of this course, you will have a strong understanding of how to tackle complex computational problems and evaluate the efficiency of your solutions.

This course is designed for students who already have a basic understanding of algorithms and programming and are ready to tackle more challenging concepts. Through a combination of theoretical lessons, practical exercises, and problem-solving, you will develop the skills needed to design and analyze sophisticated algorithms.

Course Objectives:

By the end of this course, you will be able to:

  1. Design and implement advanced algorithms using functions, procedures, and recursion.

  2. Analyze and compare the complexity of algorithms using Big-O, Big-Ω, and Big-Θ notations.

  3. Work with advanced data structures such as records, files, and custom structures.

  4. Prove the correctness of algorithms using formal methods.

  5. Apply advanced algorithmic techniques to solve real-world problems.

  6. Understand the trade-offs between time and space complexity in algorithm design.

Course Outline:

  1. Functions and Procedures

    • Modular programming with functions and procedures

    • Parameter passing techniques (by value, by reference)

    • Scope and lifetime of variables

  2. Recursion

    • Principles of recursion

    • Recursive vs. iterative solutions

    • Examples of recursive algorithms (e.g., factorial, Fibonacci, Tower of Hanoi)

    • Tail recursion and optimization

  3. Records and Files

    • Working with structured data using records

    • File handling: reading from and writing to files

    • Applications of records and files in algorithm design

  4. Algorithm Complexity

    • Time and space complexity analysis

    • Big-O, Big-Ω, and Big-Θ notations

    • Complexity classes (P, NP, NP-hard, NP-complete)

    • Case studies of algorithm complexity

  5. Algorithm Proofs

    • Techniques for proving algorithm correctness

    • Loop invariants and mathematical induction

    • Examples of formal proofs for sorting, searching, and graph algorithms

  6. Advanced Algorithmic Techniques (Suggested Enhancement)

    • Divide and conquer algorithms (e.g., Merge Sort, Quick Sort)

    • Dynamic programming (e.g., Knapsack problem, Longest Common Subsequence)

    • Greedy algorithms (e.g., Dijkstra's algorithm, Huffman coding)

    • Graph algorithms (e.g., DFS, BFS, shortest path algorithms)

  7. Case Studies and Applications (Suggested Enhancement)

    • Real-world applications of advanced algorithms

    • Algorithm optimization for large-scale data

    • Ethical considerations in algorithm design

Level: L2