CS- 6515-A: Intro to Grad Algorithms - CS-6515-A

Final grades

All grades have been published to Canvas. It displays your current letter grade.

I will export final letter grade directly from canvas, so please check the displayed letter grade.

CIOS

CIOS is currently at 72% (05/02, 3am ET). Since this is very close to the 75%, I added a partial 0.5 CIOS bonus, rather than completely dropping it.

You can still reach 75% threshold.

Exam 4

The exam has been released on gradescope.

Regrade requests are very short, until Saturday 1pm.

Hi everyone,

Scores for problem sets 9 and 10 have been released. These are the statistics:

Rubric and Regrade Requests

Your graders are human, and so they may have made errors. If you think your assignment was graded incorrectly against the rubric, then make a regrade request to the instructors on Gradescope. Regrades will be open for THREE days until April 25th at noon (04-25-2025 @ 12:00 PM ET). Please submit a regrade request before the deadline. Also, provide a brief explanation of the issue(s) and why you should receive points.

Some notes about regrade requests:

• Please read the rubric closely and refer to the solutions posted in the Resources section before submitting a regrade request. 
• Note that we reserve the right to regrade your entire submission if you submit a regrade request. It is possible, though very unlikely, to end up losing points after submitting a regrade request.
• Regrade requests without an explanation of the issue/why points should be returned will be dismissed. 
• Note that regrades requests are for when you think the grading did not match the rubric, or if you think that the answer in the rubric is incorrect. Please do not submit a regrade request if you were graded correctly but feel that the rubric is unfair.

Handwritten notes: https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m9ltp2bhaui4kz

Recording: https://mediaspace.gatech.edu/media/CS6515%20L25%20Global%20Min%20Cut/1_8irw5hf1

Further material:

• Lecture notes from CS7530 (Section 2 of the pdf)
• Chapter from Erickson's algorithm book: https://jeffe.cs.illinois.edu/teaching/algorithms/notes/08-mincut.pdf

https://gatech.smartevals.com/

The CIOS is online, please take a few minutes to fill it out.

There is the incentive listed in @486, but please fill out the CIOS even if you do not need the extra 1%. The feedback is important for future iterations of this course. Below are some examples how the course changed because of CIOS from previous semesters.

Not just the feedback on what to change but also what should be kept the same is helpful, since some changes are new and were tried for first time.

Changes implemented based on previous CIOS feedback:

• Programming assignments
  • Last semester we had only a single programming assignment. The feedback was positive so we added a bunch more this time.
  • (Were they helpful with learning the material or not? Should we have more or fewer?)
• Recording
  • We did not record 6515 in fall. Recordings were requested in last semester's CIOS.
  • (Since this is new, feedback is helpful. Did it help you learn the material?)
• Dropping problems rather than problem sets
  • This is now the 2nd semester we dropped problems. (In the past we dropped problem sets rather than individual problems, so it used to be more "all or nothing".) This was implemented based on CIOS feedback in spring'24 undergrad algorithms.

Handwritten notes:

https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m9iz5fv0qkq6su

Recording:

https://mediaspace.gatech.edu/media/CS6515%20L24%20One-Sided%20Error%2C%20Amplification%2C%20k-path/1_7yxb9osa

Further material:

Typed notes from CS7530

Scribe_Lec2.pdf

I've sent an email (subject "CS6515 Makeup Exam") to all students that are eligible for the makeup exam because of excused absence (sickness, conference travel, etc). 

Contact me ASAP via email (vdbrand@gatech.edu) if

• If you did not receive my email, even though you did provide us with the necessary documentation for the makeup exam. 
• If you did not yet provide documentation (doctor's note, conference program, etc) for a missed exam, please send it to us as soon as possible to be eligible for the makeup exam.

Handwritten notes: https://piazza.com/class_profile/get_resource/m3icaapxwwz1f5/m9f28luck7hyw

Recording: https://mediaspace.gatech.edu/media/CS6515%20L23%20Schwatz%20Zippel%20Lemma%20%20Matching/1_zjhjwbik

Further Material:

More information on this algorithm, including how to find the matching (rather than just testing if a perfect matching exits) from CS7530 randomized algorithms: CS_7530_Lecture_3_Scribing.pdf

This post is regarding the makeup exam on April 22nd, for those with excused absence during exam 1-3.

Exam rules

• 2 handwritten sheets (front and back) of notes is allowed. (Since this is cumulative, we allow an extra sheet)
• Other than that, no tools/material is allowed (no calculator, book, electronic devices, etc)
• The exam is on paper. So do bring a pen. Pencil is fine too.
• Exam is until 3:15. We design the exam to be taken within 1 hour, but you may have more time if everyone arrives on time (2:00) and we can start sooner than expected.

Topics

The exam covers the 4 major topics we have had for exam 1-3:

• Divide&Conquer
  • The focus will be more on analysis rather than design.
• Graph/Flow
  • BFS/DFS/Dijkstra/Prim; Reachability, Topological order, Shortest Path, Spanning Tree.
  • What is a max flow. What is a min cut. Residual graphs, augmenting flows. Some algorithms for it.
• Dynamic Programming
  • Design algorithms, construct recursions, argue complexity, etc
• Linear Programs
  • What is a linear program + their applications. Construct linear programs to solve problems
  • Simplex Algorithm (what are vertices, edges, which vertex is picked next)

The structure of the makeup exam is the same as usual:

• Q2/3/4 are larger questions, each is on one topic. Similar to what we had as Q2/3/4 on previous exams.
• Q1 is multiple choice or short answers.
  • Given that we have 4 topics to cover, likely the 1st page of Q1 will be mixed and the 2nd page of Q1 focuses more on one of the 4 topics not covered in Q2/3/4.

As practice, I'd look at our previous exams, since the questions will be similar. Here are previous exams without solutions:

Exam1.pdf

Exam2.pdf

Exam3.pdf

For solutions, see the resource tab.

For other practice questions, check the previous threads for exam 1-3:

@114

@276

@401