Xi Li (李溪)

CS652/752 Advanced Algorithms and Applications

Course Overview

The study of algorithms will enable you to reason about the core computational structure underlying a problem and equip you with a rigorous set of techniques to solve such problems. The design and analysis of fundamental algorithms underpins numerous fields of importance ranging from data science, business intelligence, finance and cyber security to bioinformatics. Algorithms to be covered include dynamic programming, greedy technique, linear programming, network flow, sequence matching, search and alignment, randomized algorithms, page ranking, data compression, and quantum algorithms. Both time and space complexity of the algorithms will be analyzed. Formalization, mathematical proofs will play a key role in the class.

Course Objectives

Throughout this course, students will:

• Understand fundamental algorithms, their types, and typical applications.
• Analyze the efficiency of algorithms, focusing on time and space complexity.
• Implement algorithms using a programming language to solve practical problems.

Topics

• Mathematical Foundations: Such as common mathematical functions, analysis of algorithm efficiency, and growth rate functions.
• Divide and Conquer Strategies: Concepts such as merge sort, recursion trees, the Master Theorem, and the Maximum Subarray Problem.
• Sorting Algorithms: Detailed study of algorithms including quicksort, counting sort, radix sort, and heapsort.
• Selection Problems: Techniques for solving selection problems efficiently.
• Dynamic Programming: Introduction to dynamic programming principles and their applications.
• Greedy Algorithms: Exploration of greedy methods for problem-solving.
• Tree Data Structures: Study of advanced tree structures including van Emde Boas (vEB) trees, tree algorithms, and red-black trees.

Prerequisites

CS 303 [Min Grade: C] and (MA 125 [Min Grade: C] or MA 225 [Min Grade: C])

Textbook

Introduction to Algorithms (3rd Edition), Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Online

Grading Policy

• Assignments: 30%
• Midterm Exam 1: 20%
• Midterm Exam 2: 20%
• Final Exam: 20%
• Participation: 10%

Course Activities

Assignments: This course includes both coding and written assignments to enhance learning and practical application. You are expected to use Python for the 3 coding assignments. There will be 5 theory assignments throughout the semester. You are expected to complete all of them to help you learn the topics discussed in lectures.

Exams: The course will include 2 midterm exams and 1 final exam. 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. The exams will be conducted in a closed-book format and administered as quizzes on Canvas, using the Respondus LockDown Browser on your laptop.

Participation: Participation is assessed through in-class quizzes. Quizzes consist of multiple-choice questions accessible via Canvas on a phone or laptop.