Theory and Applications of Graphs, Fall 2020

Course Information

Theory and Applications of Graphs: Social Networks, Search Engines, and Gene Interactions (EN 500.111)

Instructor: Melanie Kirsche (mkirsche @ jhu.edu)

Office Hours: Tuesdays 10:30 AM to 11:30 AM (EST) or by appointment - see Piazza for Zoom link

Course Meeting Times:

Section	Day	Time
09	Tuesday	8:30-9:45 AM (EST)
20	Wednesday	8:30-9:45 AM (EST)

Course Description

Graphs are a mathematical structure used to represent relationships between objects, and they can be found throughout the sciences as well as in the computer and phone applications people use every day. From modeling friendships in social networks, to giving the best directions on a map, to assembling genomes, there is a never-ending range of applications for graphs and the algorithms used to process them. In this course we will explore some of the real-world applications of graphs which drive the need for efficient algorithms.

Grading

This course is graded on a satisfactory/unsatisfactory basis. Grades will be based on two factors:

• Regular attendance and participation in the course (at most one absence will be permitted except in the case of extraordinary circumstances)
• A group presentation about a chosen application of graphs on the final day of class - details to follow

Course Resources

• Piazza Discussion Board

Course Outline

Slides will be posted here prior to each lecture, and required readings for each class will be posted no later than the end of the day of the previous class.

Course Session	Dates	Subject	Link to Slides	Required Reading or Viewing
Week 1	9/8, 9/9	Introductions, Definitions, and Terminology	Lecture 1	Welcome Survey
Week 2	9/15, 9/16	Path-Finding Algorithms	Lecture 2	Khan Academy's Introduction to Algorithms: I'm only assigning the video and articles in the Intro to Algorithms section, but feel free to read the sections on graph representation and breadth-first search as well if you want more of a preview of what we'll be going over in class Introduction to Big-O Notation for Algorithm Analysis: A blog post on algorithm analysis CS Dojo's Intro to Big O Notation: A longer, optional video which gives a more programming-focused look at Big-O notation and runtime analysis
Week 3	9/22, 9/23	Path-Finding in Maps and Navigation Software	Lecture 3	Introduction to A-Star Search: An introduction to the A-Star algorithm, which also includes a brief review of Dijkstra's algorithm A-Star Heuristics: A follow-up to the other reading which talks about some of the heuristics that could be used to make A-Star work faster in different situations
Week 4	9/29, 9/30	Social Network Graphs from Friendship to Disease Transmission	Lecture 4	None
Week 5	10/6, 10/7	Knowledge Graphs in Databases and Search Engines	Lecture 5	A graph-structured dataset for Wikipedia research: A paper describing a graph representation of Wikipedia - don't worry too much about the technical specifications, but try to understand the bigger picture of how their graph is structured Xefer: A visualization of Wikipedia hyperlinks leading from philosophy to any set of random or user-selected pages - try it out by entering some article names or by hitting the Random button a few times
Week 6	10/13, 10/14	Graphs in Computational Biology: Genome Assembly and Gene Interactions	Lecture 6	Why are de Bruijn graphs useful for genome assembly?: A paper describing the application of different types of graphs to genome assembly. Note that the figures, although they are referenced throughout the test, are at the end of the document.
Week 7	10/27, 10/28	Graphs to study genomic variation	Lecture 7	None
Week 8	11/3, 11/4	Dynamic Programming and Decision Trees	Lecture 8	Optional: Understanding Random Forests: A brief introduction to how random forests work
Week 9	11/10, 11/11	Graphs in Computer Vision and Image Processing	Lecture 9	None
Week 10	11/17, 11/18	Student Presentations		None, but don't forget to send me your slides by midnight the night before!