CSci 493 Syllabus        FAQ


7-leaf nni treespace nni by MP




CSci 493: Algorithms for Tree Distributions
Department of Computer Science
Hunter College, City University of New York
Fall 2022




TL;DR: Hands-on algorithms seminar with coding, design, group work, and presentations.

Questions? See the FAQ's.


Calendar:

The following sources are abbreviated below:

 Week: Topics: Techniques: Assignments: Reading:
#1: Wednesday,
31 August		 Syllabus & Class Policies; Overview;
Tree Similarity & Newick Notation 		Representing Trees in Newick Notation;
Using Github		 CW 1: Counting Trees Treespace (first 2 pages);
Newick Tree Format (Heckendorn);
Getting Started with Github
#2: Wednesday,
7 September		 Equality for Leaf-Labeled Trees; Counting Trees;
Balance Indices, Vector Representation of Trees
 Recap: Tree Abstract Data Type;
Classes in Python;
BioPython & ETE3 		CW 2: Balance Indices Python DS: Chapter 2 (classes);
Python DS: Chapter 7 (trees);
Tree Balance;
BioPython;
Environment for Tree Exploration (ETE)
#3: Wednesday,
14 September		 Vector-Based Tree Metrics: Robinson-Foulds Distance & Day's Algorithm, Branch Length Distance, Rooted Triples Distance, Cophenetic/KC Distance Recap: Hashing, Recursion on Trees CW 3: Hashing Trees Robinson, Foulds, 1981;
Day, 1985;
Sand et al., 2013 (triples)
#4: Wednesday,
21 September		 More on Vector-Based Tree Metrics;
Edit Moves on Trees: Nearest Neighbor Interchange (NNI);
Treespaces 		Recap: Big-Oh Notation;
Recurrence Relations		 PS 1: Tree Warm-ups;
CW 4: Poly-time Metrics		 Allen & Steel, 2001;
Treespace (discrete treespaces)
#5: Wednesday,
28 September		 Semester Project Lists;
Continuous Treespace;

Guest Speaker: Melanie Hopkins, AMNH 		Recap: Recurrence Relations CW 5: Continuous Treespace Treespace (continuous treespaces) ;
Billera, Holmes, Vogtmann, 2001 (BHV);
Amenta, et al., 2007
4-5 October CUNY: No Class
#6: Wednesday,
12 October		 Geodesics in Continuous Treespace Network Flows PS 2: Trees as Vectors;
CW 6: Geodesics		 Billera, Holmes, Vogtmann, 2001 (BHV);
Owen & Provan, 2011;
Network Flow (Quanta)
#7: Wednesday,
19 October		 Other Approaches to Geodesics;
Subtrees & Forests;
Maximum Agreement Subtrees (MASTs)

Guest Speaker: Sean Cleary, CCNY 		Dynamic Programming CW 7: MASTs Steel & Warnow, 1993
#8: Wednesday,
26 October		 More on Edit Moves on Trees: Subtree Prune & Regraph (SPR), and Tree Bisection & Reconnection (TBR);
Maximum Agreement Forests & Distances

Guest Speaker: Kristina Wicke, NJIT 		Fixed Parameter Tractability;
Kernelization		 CW 8: MAFs;
PS 3: Agreement Forests
 Allen & Steel, 2001
#9: Wednesday,
2 November		 More on Agreement Forests;
Approximating SPR & TBR Distances		 Approximation Algorithms
 CW 9: Approximations Allen & Steel, 2001;
Bonet et al., 2006
#10: Wednesday,
9 November		 Diameter of Treespaces;
Searching Treespaces; Neighborhoods in NNI-Treespace		 Graph Searches: Breadth First Search; CW 10: MAFs & Diameter Treespace (discrete treespaces);
Python DS: Section 8.9 (BFS)
#11: Wednesday,
16 November		 Tanglegrams Dynamic Programming;
CW 11: Projects Check-ins Venkatachalam et al., 2010
#12: Wednesday,
23 November		 Consensus & Summary Methods Uniform Hashing;
Randomness in Algorithms		 CW 12: Project Check-ins Bryant, 2003;
Amenta et al., 2003
#13: Wednesday,
30 November		 Scoring Trees CW 13: Parsimony
#14: Wednesday,
7 December		 Final Project Presentations
AMNH Tour		 CW 14: Turtles in ToL

(This file was last modified on 23 December 2022.)