Xi Li (李溪)

CS652/752 Advanced Algorithms and Applications

Course Overview

This course provides an in-depth study of fundamental algorithms and data structures, focusing on their design, analysis, and application in solving real-world problems. Students will explore key algorithmic paradigms, such as divide and conquer, dynamic programming, and greedy algorithms, while also learning techniques for analyzing algorithm correctness and efficiency using mathematical induction and asymptotic notation. The course aims to equip students with the skills needed to develop efficient and scalable solutions to computational problems, laying a strong foundation for advanced studies in computer science.

Course Objectives

Throughout this course, students will:

• Understand Core Algorithmic Concepts.
• Design and implement well-structured algorithms for diverse computational problems.
• Assess efficiency and correctness of the designed algorithm.

Topics

• Algorithm Analysis
  • Algorithm Correctness
  • Asymptotic Analysis
• Advanced Algorithm Design
  • Divide and Conquer
  • Dynamic Programming
  • Greedy Algorithms
  • Graph Algorithms
• Network Flow
  • Max Flow and Min Cut
  • Ford–Fulkerson and Preflow–Push Algorithms
  • Matching Problems
• NP-Completeness
  • Complexity Classes: P, NP, NP-hard, and NP-complete
  • Classic NP-complete Problems: SAT/3-SAT and Vertex Cover

Grading Policy

• Assignments (30%): This course includes both written assignments and coding assignments designed to strengthen algorithmic thinking, rigorous analysis, and practical application.
• Exams (60%): The course will include 2 midterm exams (15% each) and 1 final exam (30%). The midterm exams are periodic assessments that focus only on the material covered since the previous exam. The final exam is comprehensive, covering all topics discussed throughout the semester. All exams will be closed book, and they will be conducted in the form of in-person paper-based exam.
• Participation (10%): Class participation is assessed primarily through in-class attendance, which will be tracked using a sign-in sheet. Students are expected to attend class regularly and participate actively.