Category Archives: Teaching Materials

Note for prospective students and postdoc researchers

  • For current UBC students (Ph.D., Master, Undergraduate): For exceptional cases, there could be research opportunities. But students should have a working knowledge of Python programming and Linux environment. I recommend interested students to take these online courses: Data Science, Machine Learning, Linux, SQL, and NoSQL. In case you want to contact me, please read my research group’s papers, then describe the specific research topics you want to pursue.
  • For non-UBC students (Ph.D. and Master’s program applicants): Thank you for your interest in working with me. Unfortunately, I don’t have the capacity to work with non-UBC students. For possible collaboration, you first need to go through the formal admission process for UBC and Sauder School of Business before I can consider you as a potential collaborator. You do not need to have a commitment from an advisor prior to admission. Please check the related information on the Ph.D. program and the M.Sc. program. Also, please note that admission decisions are collectively made by Sauder school, not by individual faculty members.
  • Regarding postdoc positions or visiting students: Thank you for your interest in working with me as a postdoc or a visiting student. Unfortunately, I don’t have the capacity to host more researchers at the moment. You can find UBC faculty who are taking visiting scholars at https://www.grad.ubc.ca/virs/hosts.
  • Regarding the Visiting Associate Program at Centre for Korean Research, Institute of Asian Research: https://ckr.iar.ubc.ca/ckr-visiting-scholar-program/

Lecture Notes: NP-Completeness: An Overview

Kim, Y. E. and Lee, G. M. (2003). NP-Completeness: An Overview. Lecture Notes, November 2003.

This paper presents an overview of NP-complete problems. The theory of NP-completeness is important not only in the theoretical aspect but also in reality. First, we will take a look at the formal definition and some examples of NP-complete problems. Then, we will see how to prove a problem is NP-complete and how to cope with NP-complete problems.