COMP 5970/6970-003 Graph Algorithms Fall, 2022

Course Description

Graphs are perhaps the most general and versatile data model. This course covers ways to cast real problems as graph theory problems and solve them with algorithms dealing with paths, trees, cuts, partitions, clusters, optimized search, and much more.

Course Materials

• Lecture notes will be made available on Canvas. There is no textbook for this course. There should be one lecture note per week of classes except for the midterm and final week.

Prerequisites/Corequisites

Prerequisites: Introduction to Algorithms Suggested: Linear algebra

Other requirements, languages used

Languages: Python, bash scripting (basic knowledge of both is expected) Packages and software

used: networkx, graphviz, gephi

Course Objectives

Successful students:

1. Can cast real world problems into graph problems and identify the appropriate graph algorithm to solve them

2. Can implement these algorithms from scratch as well as use packages to run these algo- rithms on real world problems

3. Have multiple ways to inspect graph structures with a variety of graph visualization tools

Course Structure

Assignments

Assignments will be in the form of weekly homeworks (12 planned, but this may be reduced). The homeworks will have some short answer and some coding sections. The lowest 2 homework grades will be dropped.  I will try to be explicit about what packages are allowed and what functions are not allowed, but use common sense — if the point of the assignment is to implement algorithm x, you cannot use package.x().

Late Policy

Each student is allowed 5 late days.   No more than 3 late days may be used on any single homework. After that, I will count it toward your dropped homeworks up to the 2 allowed.

Grading

Your letter grade will follow the standard numerical scale – A: [90, 100], B:[80, 90), C: [70, 80), D: [60, 70), F: [0, 60)

1.  Exams (45%): Midterm: 20%, Final: 25%

2.  Homeworks 55% lowest 2 homeworks will be dropped.

The final exam will be given on the last day of the course and not on the day designated in the final exam schedule. Assignment and final grades may be scaled up but not down according to whether I think those with mastery of the material are receiving an A or not. Example exam questions might be something like ”What problem is Karger’s algorithm trying to solve:  be specific. ” and ”How does Karger’s algorithm go about solving this problem for unweighted graphs?” Good answers to these would be ”finding the minimum weight cut in a graph” or ”global min-cut (not min s-t cut)” and ”Karger’s algorithm picks random edges and contracts the nodes on either end into a new node.  It then deletes self edges and proceeds until there are only 2 nodes left.   The remaining edges between these two nodes represent a cut in the original graph that is probabilistically a small cut. It repeats this process many times and picks the smallest which is probabilistically the min-cut. ”

Course Policies

0.1   Attendance

Class attendance is required but lax. You may miss up to 8 days (the class meets 42 days including a midterm and final on the last day of class) with no repercussions.  Any more than 8 days

unexcused will result in a single letter grade reduction. Any additional absent days need to be official excused absences through the university.  Phones should be on silent and any audible ring or notification will result in public shaming.

0.2   Excused Absences

Students are granted excused absences from class for the following reasons: Illness of the student or serious illness of a member of the student’s immediate family, death of a member of the student’s immediate family, trips for student organizations sponsored by an academic unit, trips for University classes, trips for participation in intercollegiate athletic events, subpoena for a court appearance and religious holidays.  Students who wish to have an excused absence from this class for any other reason must contact the instructor in advance of the absence to request permission.  The instructor will weigh the merits of the request and render a decision.  When feasible, the student must notify the instructor prior to the occurrence of any excused absences, but in no case shall such notification occur more than one week after the absence. Appropriate documentation for all excused absences is required.

0.3   Make-Up Policy

Arrangements to make up missed major examination (e.g.  mid-term exams) due to properly authorized excused absences. Except in unusual circumstances, such as continued absence of the student or the advent of University holidays, a make-up exam will take place within two weeks from the time the student initiates arrangements for it.

0.4   ADA Policy

Students who need accommodations are asked to electronically submit their approved accommo- dations through AU Access and to make an individual appointment with the instructor during the first week of classes — or as soon as possible if accommodations are needed immediately. If you have not established accommodations through the Office of Accessibility, but need accom- modations, make an appointment with the Office of Accessibility, 1228 Haley Center, 844-2096 (V/TT).

0.5   Academic Honesty

All portions of the Auburn University Student Academic Honesty code (Title XII) found in the Student Policy eHandbook at http://www.auburn.edu/student info/student policies/ will ap- ply to this class. All academic honesty violations or alleged violations of the SGA Code of Laws will be reported to the Office of the Provost, which will then refer the case to the Academic Honesty Committee.

Schedule and weekly learning goals

The schedule is tentative and subject to change. The learning goals below should be viewed as the key concepts you should grasp after each week, and also as a study guide before each exam,

and at the end of the semester.  Each exam will test on the material that was taught up until 1 week prior to the exam.

Week 01, 08/15 - 08/19:   Introduction to graphs

• Nodes, edges, weights, directed edges, node degree

• Adjacency matrix, adjacency list, edge list

• DAGs, trees, bipartite, non-negative weighted, planar, hypergraphs

• Connected components, cliques, strongly connected components, paths, cuts, matchings

• Depth and breadth first search

Week 02, 08/22 - 08/26:   Connected components and spanning trees

• Union-find / disjoint set

• Path compression

• Minimum spanning tree

• Kruskal’s algorithm

• Prim-Jarnik algorithm

• Homework 1 due Friday

Week 03, 08/29 - 09/02:   DAGs

• Scheduling, Causal structures: bayesian networks, Geneology, Version control history, Ci- tation graphs

• Cycle detection

• Topological sort

• Strongly connected components

• Homework 2 due Friday

Week 04, 09/05 - 09/09:   Shortest Paths

• Dijkstra’s algorithm

• Bellman-ford

• Hamiltonian and Eularian paths

• Homework 3 due Friday

Week 05, 09/12 - 09/16:   All shortest Paths

• Floyd-warshall algorithm

• Johnson’s algorithm

• Homework 4 due Friday

Week 06, 09/19 - 09/23:   Optimized search

• A* search

• Branch and bound

• Homework 5 due Friday

Week 07, 09/26 - 09/30:   Matchings

• Fair assignments – medical residency placement, personal research example – polyploid phasing

• Maximizing productivity through task assignment

• Bipartite stable matching aka the stable marriage problem - Gale-Shapeley algorithm

• General stable matching aka the stable room mate problem - Irving’s algorithm

• Bipartite assignment problem - The Hungarian method

• General assignment problem - Blossom algorithm

• Homework 6 due Friday

Week 08, 10/03 - 10/07:   Midterm

• Midterm

• Fall break!

Week 09, 10/10 - 10/14:   Max flow-min cut

• Max flow-min cut duality

• Electrical grid throughput, personal research example – multiple sequence alignment

• Ford-fulkerson algorithm

• Edmonds-Karp algorithm

• Karger’s algorithm

Week 10, 10/17 - 10/21:   Graph clustering

• Spectral clustering

• Markov clustering

• Louvain method

• Homework 7 due Friday

Week 11, 10/24 - 10/28:   Graph visualization

• Graphviz

• Gephi

•  dot format

• Homework 8 due Friday

Week 12, 10/31 - 11/04:   K nearest neighbors

• Construction of sparse graph from euclidean or other multi-dimensional data

• Data reduction / dimensionality reduction

• Classification

• Ball-tree construction

• kd tree construction

• Homework 9 due Friday

Week 13, 11/07 - 11/11:   Vertex cover

• Integer linear programming

• Approximation algorithm

• Homework 10 due Friday

Week 14, 11/14 - 11/18:   Graph Coloring

• On planar graphs

• Determining if a graph is planar

• On non-planar graphs

• Homework 11 due Friday

Thanksgiving, 11/21 - 11/25: