Assignment 5 — Greedy Algorithms

CSC 349: Design and Analysis of Algorithms 
Assignment 5 — Greedy Algorithms

Credit: This is a lab by Christopher Siu.
A greedy algorithm is one that assumes it can repeatedly make locally optimal choices, never having to
backtrack, always arriving at a globally optimal solution. The greedy approach can be applied to a wide
variety of problems, including those that involve graphs.
Deliverables:
GitHub Classroom: https://classroom.github.com/a/WfTVjKB2
Required Files: compile.sh, run.sh
Optional Files: *.py, *.java, *.clj, *.kt, *.js, *.sh
Part 1: k-Cores
A k-core is a maximal connected subgraph within which every vertex has degree at least k. They have
applications in graph-based problems as a computationally inexpensive way of approximating the most densely
connected regions of a graph. For example, consider the following undirected graph:
v0
v1
v2
v3
v4
v5
v6
k = 2
k = 1
All seven vertices in this graph can be found within a 1-core, since they all have a degree of at least 1.
However, the 2-core contains only vertices v0, v1, and v2. Note that although the graph contains a vertex of
degree 3 (as well as one of degree 5), there is no 3-core — there is no subgraph within which every vertex has
degree 3. Vertex v2 has degree 3, but its neighbor v0, for example, only has degree 2. This means that v0
cannot be in a 3-core, and without v0, v2’s degree falls below 3.
Perhaps more importantly, from the perspective of a greedy approach, note that the k-cores form a nesting
hierarchy of vertices: any vertices in the i-core must necessarily also be in the (i − 1)-core, but there can be
vertices in the (i − 1)-core that are not in the i-core.
In your programming language of choice per Assignment 1, implement a greedy algorithm to compute the
k-cores of a graph. Think carefully about what metric your algorithm will be greedy over1 and what data
structures it will use to keep track of that information. You should be able to produce all of the k-cores of a
graph in linear O(|V | + |E|) time2
.
Each input graph will be provided as an edge list: each edge in the graph will be represented by a commaseparated pair of vertex identifiers, indicating an edge between the first vertex and the second.
You may assume that vertex identifiers are contiguous natural numbers — they begin at 0, and there will be
no “gaps” in the identifiers used. You may also assume that the graph will be simple and will not contain
any isolated vertices3
.
1Consider pruning: removing vertices and edges that cannot possibly be part of some solution.
2Formatting and printing the cores will naturally require more time.
3Since there are no isolated vertices, there are no meaningful 0-cores; they will always be identical to the 1-cores.
1 of 3
CSC 349: Design and Analysis of Algorithms
Fall 2019
Assignment 5 — Greedy Algorithms
Due: Friday, November 1st
For example, the above graph could be represented as:
0, 1
0, 2
1, 2
1, 4
1, 5
1, 6
2, 3
Your program must accept as a command line argument the name of a file containing an edge list as described
above, then print to stdout the k-cores according to the following format:
· Every non-empty k-core must be printed, starting with k = 1.
· For each value of k, all vertices in such k-core(s) must appear on a single comma-separated line.
· Each line’s vertices must be sorted in ascending order. Note that vertex identifiers are integers, not
strings. The lines themselves must be sorted in ascending order by k.
For example:
>$ ./compile.sh
>$ ./run.sh in1.txt
Vertices in 1-cores:
0, 1, 2, 3, 4, 5, 6
Vertices in 2-cores:
0, 1, 2
Your program will be tested using diff, so its printed output must match exactly.
Part 2: Submission
The following items must be demonstrated in lab on the day of the deadline:
· Pseudocode for an efficient greedy algorithm to find the k-cores of an undirected graph.
· A brief description of the locally optimal choices your algorithm greedily makes, together with a brief
justification of why it is safe to assume that those choices will lead to a globally optimal4
solution.
The following files are required and must be pushed to your GitHub Classroom repository by 8pm on the due
date:
· compile.sh — A Bash script to compile your submission (even if it does nothing), as specified.
· run.sh — A Bash script to run your submission, as specified.
The following files are optional:
· *.py, *.java, *.clj, *.kt, *.js, *.sh — The Python, Java, Clojure, Kotlin, Node.js, or Bash source
code files of a working program to find k-cores, as specified.
Any files other than these will be ignored.
4
In this problem, the optimized quantity is the size of the k-cores: for correctness, they must be maximal.
2 of 3
CSC 349: Design and Analysis of Algorithms
Fall 2019
Assignment 5 — Greedy Algorithms
Due: Friday, November 1st
Additionally:
· On the date before the due date, the grader will be run after 8pm and provides feedback containing
only what your program scores. Only submissions made before 8pm are guaranteed to receive feedback.
What your program scores on the official run (the due date) is the final score.
· Late submissions made within 24 hours of the deadline receive a .7 multiplier. If you decide to make a
late submission, please notify me by sending an email to vnguy143@calpoly.eduwith both the subject
and the body in the format: ”CSC349,late,asgn<i>”, i being the assignment number.
3 of 3