Weitian Tong – Curriculum Vitae

Weitian Tong
Curriculum Vitae
CSC 311, Department of Computing Science
University of Alberta
Edmonton, AB, Canada, T6G 2E8
H +1 (780) 394 8742
B [email protected]
Í www.cs.ualberta.ca/ weitian
1989–present
"Chance favors only the prepared mind" - Louis Pasteur
Education
2011–present PhD student (transferred from Master program in January 2012), Department of
Computing Science, University of Alberta, Canada, GPA – 4.0/4.0.
Supervisor: Prof. Guohui Lin
Expected graduate date: Aug. 20, 2015
2010–2010 Research student, Applied Mathematics and Physics, Graduate School of Informatics,
Kyoto University, Japan.
2007–2010 Finance Minor, College of Economics, Zhejiang University, China, GPA – 3.92/4.0.
2006–2010 B.S., Department of Mathematics, Zhejiang University, China, GPA – 3.92/4.0.
Research Interests
Approximation Algorithms, Smoothed Analysis, Randomized Algorithms
Awards
2014 Alberta Innovates Graduate Student Scholarship
Alberta Innovates-Technology Futures
2014 Computing Science GPA Award
Department of Computing Science, University of Alberta
2013 PhD Early Achievement Award
Department of Computing Science, University of Alberta
2012 Graduate Student Teaching Award
Faculty of Graduate Studies and Research, University of Alberta
2010 Excellent Graduate of Zhejiang University
Ministry of Education of China
2009 The First Prize of National Teaching Bases Scholarship
Ministry of Education of China
2008 The First Prize of National Teaching Bases Scholarship
Ministry of Education of China
2008 National Scholarship
Ministry of Education of China
2007 The Second Prize of National Teaching Bases Scholarship
Ministry of Education of China
1/6
Professional Activities
2012-present { External reviewer for AAIM 2014, FAW 2014, COCOON 2013, COCOA 2013, COCOA
2012
{ PC member of COCOA 2012
{ Local organizing committee member of COCOA 2012
{ Reviewer for Journal of Combinatorial Optimization
Teaching Experience
2011-present Teaching Assistant for courses:
Formal Systems and Logic (CMPUT 272), Algorithms II (CMPUT 304)
Department of Computing Science, University of Alberta
Publications
Journal
1. Z. Chen, B. Fu, R. Goebel, G. Lin, W. Tong, J. Xu, B. Yang, Z. Zhao and B. Zhu.
On the Approximability of the Exemplar Adjacency Number Problem for Genomes with
Gene Repetitions. Theoretical Computer Science (TCS). Accepted on July 9, 2014.
2. W. Tong, R. Goebel, T. Liu and G. Lin. Approximation Algorithms for the Maximum
Multiple RNA Interaction Problem. Theoretical Computer Science (TCS). Accepted on
Apr. 12, 2014.
3. W. Tong, R. Goebel and G. Lin. Approximating the Minimum Independent Dominating
Set in Perturbed Graphs. Theoretical Computer Science (TCS). Accepted on Nov. 12,
2013.
4. L. Huang, W. Tong, R. Goebel, T. Liu and G. Lin. A 0.5358-Approximation for
Bandpass-2. Journal of Combinatorial Optimization (JOCO). Accepted on Aug. 27,
2013.
Conference
1. W. Tong and G. Lin. An Improved Approximation Algorithm for the Minimum Common
Integer Partition Problem. In Proceedings of the 25th International Symposium on
Algorithms and Computation (ISAAC 2014). Accepted on Aug. 28, 2014.
2. I. A. Kanj, G. Lin, T. Liu, W. Tong, G. Xia, J. Xu, B. Yang, F. Zhang, P. Zhang
and B. Zhu. Algorithms for Cut Problems on Trees. In Proceedings of the 8th Annual
International Conference on Combinatorial Optimization and Applications (COCOA
2014). Accepted on Aug. 19, 2014.
3. W. Tong, R. Goebel and G. Lin. On the Smoothed Heights of Trie and Patricia
Index Trees. In Proceedings of the 20th International Computing and Combinatorics
Conference (COCOON 2014). LNCS 8591: 94-103.
4. H. Jiang, G. Lin, W. Tong, B. Zhu and D. Zhu. Isomorphism and Similarity for
2-Generation Pedigrees. In Proceedings of the 10th International Symposium on Bioinformatics Research and Applications (ISBRA 2014). LNCS/LNBI 8492: 396-396.
5. M. Lu, T. Liu, G. Lin, W. Tong and K. Xu. Set Cover, Set Packing and Hitting Set for
Tree Convex and Tree-like Set systems. In Proceedings of the 10th Annual Conference
on Theory and Applications of Models of Computation (TAMC 2014). LNCS 8402:
248-258.
6. W. Tong, R. Goebel, T. Liu and G. Lin. Approximation Algorithms for the Maximum
Multiple RNA Interaction Problem. In Proceedings of the 7th Annual International
Conference on Combinatorial Optimization and Applications (COCOA 2013). LNCS
2/6
8287: 49-59.
7. W. Tong, R. Goebel and G. Lin. Approximating the Minimum Independent Dominating
Set in Perturbed Graphs. In Proceedings of the 19th Annual International Computing
and Combinatorics Conference (COCOON 2013). LNCS 7936: 257-267.
8. W. Tong, R. Goebel, W. Ding and G. Lin. An Improved Approximation Algorithm for
the Bandpass Problem. In Proceedings of the Joint Conference of the 6th International
Frontiers of Algorithmics Workshop and the 8th International Conference on Algorithmic
Aspects of Information and Management (FAW-AAIM 2012). LNCS 7285: 351-358.
Submitted
1. H. Zhang, W. Tong, Y. Xu and G. Lin. The Graphic Traveling Salesman Problem with
Online Edge Blockages. European Journal of Operational Research (EJOR). Submitted
on May 15, 2014.
2. W. Tong, Z.-Z. Chen, L. Wang, Y. Xu, J. Xu, R. Goebel and G. Lin. An Approximation
Algorithm for the Bandpass-2 Problem. CoRR abs/1307.7089 (2013).
Presentations and talks
1. W. Tong. On the Smoothed Heights of Trie and Patricia Index Trees. The 20th
International Computing and Combinatorics Conference (COCOON 2014). Aug. 04,
2014.
2. W. Tong. Approximation Algorithms for the Maximum Multiple RNA Interaction Problem. The 7th Annual International Conference on Combinatorial Optimization and
Applications (COCOA 2013). Dec. 13, 2013.
3. W. Tong (on behalf of Dr. Tim Wylie). Discretely Following a Curve. The 7th Annual
International Conference on Combinatorial Optimization and Applications (COCOA
2013). Dec. 12, 2013.
4. W. Tong. Approximating the Minimum Independent Dominating Set in Perturbed
Graphs. The 19th Annual International Computing and Combinatorics Conference
(COCOON 2013). June 21, 2013.
5. W. Tong. Approximability Smoothed Analysis. AI seminar talk in the Department of
Computing Science, University of Alberta. Jan. 18, 2013.
6. W. Tong. An invited lecture in the course CMPUT 606 Bioinformatics in the Department of Computing Science, University of Alberta. Nov. 30, 2012.
7. W. Tong (on behalf of Dr. Zhipeng Cai). Load-Balanced Virtual Backbone Construction for Wireless Sensor Networks. The 6th Annual International Conference on
Combinatorial Optimization and Applications (COCOA 2012). Aug. 6, 2012.
8. W. Tong. An Improved Approximation Algorithm for the Bandpass Problem. The
Joint Conference of the Sixth International Frontiers of Algorithmics Workshop and the
Eighth International Conference on Algorithmic Aspects of Information and Management
(FAW-AAIM 2012). May 16, 2012.
Computer skills
Matlab
LaTex
C
C++
Python
Asympotote
html
Hobbies
Photography
Sketching
Cooking
Running
3/6
References
{ Dr. Guohui Lin, Professor
[email protected]
Department of Computing Science
University of Alberta
{ Dr. Randy Goebel, Professor
[email protected]
Department of Computing Science
University of Alberta
{ Dr. Binhai Zhu, Professor
[email protected]
Computer Science Department
Montana State University
{ Dr. Tian Liu, Associate Professor
[email protected]
School of Electronic Engineering
and Computer Science
Peking University
4/6
Research Statements
Approximability Smoothed Analysis
How to evaluate the performance of an algorithm is a very important subject in computer science. In
classical analysis approaches, i.e. the worst-case and/or average-case analyses, performance of many
algorithms is not always well explained. On the one hand, there are algorithms that perform well in practice but have a poor worst-case performance. On the other hand, average-case analysis instances bear
little resemblance to real-world instances because this method usually assumes an ideal distribution for
the input instances. Therefore, developing rigorous mathematical theories to better explain the observed
performance of algorithms or heuristics is of great significance.
Smoothed analysis was introduced by Spielman and Teng in 2001 with the aim of providing a more realistic performance measure. In this model, inputs are generated in two steps: first, an adversary chooses
an arbitrary instance, and then this instance is slightly perturbed randomly. The smoothed performance
of an algorithm is defined to be the worst expected performance the adversary can achieve. It not only
mimics the real input instances, but the randomness included in the perturbation also rules out pathological worst-case instances, that are rarely observed in practice but dominate the worst-case analysis. Since
smoothed analysis was introduced, it has achieved a series of successes in running time analysis for many
of the most interesting algorithms, including the Simplex method for linear programs and the k-means
clustering algorithm in AI.
Nevertheless, only a few studies have used smoothed analysis to assess the quality of solutions returned by
a heuristics or an approximation algorithm, a.k.a. the performance guarantee. On the other hand, in real
world applications, many approximation algorithms perform very well in practice but have poor approximation ratios under the worst-case analysis, such as the GREEDY for the Shortest Common Superstring
problem. It is quite promising that the approximability smoothed analysis will become an emerging research area and attract attention from multiple types of researchers besides theoretical computer scientists.
Besides, analysing the approximation ratio of some approximation algorithms will inevitably investigate
the quality of the optimal solution, which can reveal essential properties of the problem itself. Thus,
the approximability smoothed analysis can help us to better understand the problem and to design more
efficient and/or more effective approximation algorithms.
In the last three years, I have investigated several NP-hard problems, such as the bandpass problem,
the RNA interaction problem, the non-breakpoint problem, and the minimum common integer partition
problem, and have designed a number of best approximation algorithms under the worst-case analysis
model to these problems. I have also examined several problems under the approximability analysis model.
Recently, we proved the efficiency of the Patricia index tree using smoothed analysis and also designed an
efficient algorithm for the classic NP-hard problem in graph theory— the minimum independent dominating set problem.
In my future research career, I will continue to explore the wonderland of algorithm design and analysis, particularly the approximability smoothed analysis. I will explore various analysis techniques for
different algorithms and problems, seek to formalize the approximability smoothed analysis, and initiate
smoothed analysis on certain numerical quantities within hard problems. In turn, based on the insights
gained from the analytical results, I should be able to design more efficient or more effective algorithms.
5/6
Teaching Statements
Teaching is an essential part of increasing human understanding, not only for the students but also for the
instructors. I have always enjoyed teaching because it forces me to organise my knowledge systematically,
and I believe that the best way to learn something is by preparing to teach it to someone else. By preparing
presentations, addressing students’ questions, writing up solutions for homework problems and grading
them, I have been induced to see new perspectives and insights in my discipline, which I otherwise might
have missed. This is one of the reasons I find teaching a fulfilling and essential part of my academic life.
Teaching Experience
My first teaching duty dated back to the beginning of my graduate study in the Department of Computing
Science at the University of Alberta. Since then, I have served as a teaching assistant mainly for two
courses: Formal Systems and Logic (CMPUT 272) and Algorithms II (CMPUT 304). After the first TA
experience for CMPUT 304 in Fall 2011, I received the Graduate Student Teaching Award from the faculty
of graduate studies and research at University of Alberta. I really have enjoyed and benefited from this
teaching experience; it not only has been enjoyable to share knowledge with students, but also has helped
me deepen my knowledge in these areas.
Teaching Philosophy
I have learned is that both placing myself into the students’ position and interacting well with students are
essential for education, particularly in theory-oriented courses. I think the best way for students to learn
something is to force or seduce them to rediscover it. The instructor’s role in this process is to guide the
student toward these discoveries. During my office hours, I tutored less-experienced students and helped
them to understand basic concepts and techniques. Through this experience, I learned the skill of guiding
the students to answer their own questions, by turning a hard question into a sequence of simpler ones
that they can answer. Whenever possible, I believe this technique should be used in the classroom.
Second, I believe that during the lecture, especially when presenting a step-by-step proof of a complicit
theorem, it is crucial to spend time to explain at a purely intuitive and informal level what the proof is
about, what the key insight that cracks open the solution is, and why we care about this theorem. Such
brief introductions often reflect some aspect of an idealized creative process that could potentially explain
how the original proof was discovered. This can help students to better understand the formal proof itself.
The third thing that I learned is from my advisor (Prof. Guohui Lin), who is also the instructor of
the courses for which I was a teaching assistant. A good instructor should always carefully plan for every lecture, and make strong efforts to anticipate the students’ mental process. Maintaining a constant
friendly dialogue with the students and developing an inviting environment is very helpful in encouraging
students to express their lack of comprehension rather than to hide it.
Finally, in addition to introducing new insights into teaching service and required classes, we need to
design new courses that bring the state-of-the-art materials to the classroom. In addition, we need to
build our research team to provide research-oriented students with an environment for creative thinking
and for potential collaboration. Of course, we need to advance our own research in order to make all this
possible.
Teaching Interest
My teaching interests concentrate on theoretical computer science, especially algorithm design, complexity,
computational analysis and logic and discrete math. For the next phase of my career as an assistance
professor, where teaching will take an even more prominent role in my daily life, I am anxious to learn
new teaching skills through training and mentoring by colleagues.
6/6

Download Report