CSCI 670, Fall 2023
Advanced Analysis of Algorithms

Course descriptions and objectives

In Spring 2015, CS department has decided to make CSCI 670 a required class for all its Ph.D. students. While I personally never prefer to make any class that I teach a required class -- computer science has evolved so rapidly for me or maybe anyone to determine what each successful student should take -- this requirement has inspired me to modernize this class.

In the age of Big Data, efficient algorithms are now in higher demand more than ever before. While Big Data takes computing into the asymptotic world envisioned by our pioneers, it also challenges the classical notion of efficient algorithms: Algorithms that used to be considered efficient, according to polynomial-time characterization, may no longer be adequate for solving today's problems. It is not just desirable, but essential, that efficient algorithms should be scalable. In other words, their complexity should be nearly linear or sub-linear with respect to the problem size. Thus, scalability, not just polynomial-time computability, should be elevated as the central complexity notion for characterizing efficient computation.

This revision -- an evolving project -- has shifted the focus of this class towards "modern" algorithm design and analysis, both in techniques/methodologies and example problems. While the class materials cover mostly known and well-established results in the literature, I will also cover topics of potential research interests. I hope each student will be able to learn something to benefit his/her research.

Students in the class are expected to have a reasonable degree of mathematical sophistication, and to be familiar with the basic notions of algorithms and data structures, discrete mathematics, probability, and complexity theory. Specifically, the following will be assumed:

• Mathematical Proofs, in particular induction and contradiction.
• Asymptotic notation (Big-O, Omega, Theta), how to apply them.
• Basic data structures: arrays, linked lists, trees, balanced trees, heaps (priority queues), graphs.
• Basic graph algorithms: connected components, BFS, DFS.
• Other basic algorithms: binary search, sorting, median selection.
• Discrete mathematics: evaluating sums and simple recurrences.
• Basic complexity theory: Turing machines, computability, NP completeness, polynomial-time reduction.

This is a theory class. Students will be required and tested not just to design algorithms but also to rigorously characterize their performance. This is also a fast-paced class. If a student does not do the reading assignments and homeworks in a timely fashion, then they will experience limited benefit from the class.

Instructor

Professor Shang-Hua Teng
Office hours: MW: 12:00(noon)- 1:30 RTH 505 or by appointment;
Email : shanghua[@]usc.edu

TA

Miryam Mi-Ying Huang  
Office hours: Wednesday 14:00 - 15:00
Email: miying.huang@usc.edu

Textbook

• BOOK 1: Algorithm Design
                  Jon Kleinberg and Eva Tardos

• BOOK 2: Scalable Algorithms for Data and Network Analysis
                  Shang-Hua Teng

Lectures

10:00-11:50am Monday and Wednesday, in room WPH 102  

Grades

• 10 points - Class participation
• 60 points - 15 points each - four quizzes on homeworks (closed book & notes)
• 10 points - theoretical thinking projects I: mathematical formulation of a research project
• 20 points - theoretical thinking projects II: TCS development and exploration with ChatGPT

Homeworks

Integrity

Plagiarism and other anti-intellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University.