Advanced Data Structures and Algorithms

Back to main page

Syllabus

The syllabus for the course can be found here. Most (but not all) of that information is summarized here.

Lectures and Attendance Policy

Lectures will be held in-person in the classroom listed on the University Registrar. Lectures will be recorded for the convenience of those who cannot intend or prefer not to for any reason.

The class schedule depends on the day of the week. On Mondays and Wednesdays, we will have a traditional lecture in which material is presented to you by the instructor. On Fridays, we will do one of three things: Take an in-person quiz (2 total), work together on a homework assignment (6 total), or cancel class.

Class attendance is mandatory. Every lecture, I will have a computer program randomly select 20 names from the roster. If your name is chosen and you are not present on class for any reason, then your participation score will drop by 2 percentage points (you will lose 2 of the 12 percent participation grade). I have a good reason for instituting this policy, which will be justified to you in person during the first class period.

Our classroom is a no technology zone (except for the projector used for the slides) during traditional lectures (Mondays and Wednesdays). The purpose of this policy is to ensure students are present and paying attention to the lecture consistently. If you use technology during lecture, then I will consider you absent and deduct from your participation score. I will also justify this policy to you verbally during the first class period. On Fridays, you will use your laptops to work on homework assignments collaboratively with others.

Textbook

We’ll post readings from the following two sources (one is a textbook, the other a curated website of algorithms concepts). We urge you to read them or get that info from another source.

Introduction to Algorithms by Cormen, et. al., 3rd edition. Referred to as “CLRS”. UVA Library has a digital version of CLRS available online for free * CP-Algorithms. A curated website of algorithm ideas for competitive programming (https://cp-algorithms.com)

Topics

The course covers the following topics:

• Fenwick Trees: An advanced array that allows for fast range queries
• Segment Trees: An advanced tree that allows for fast range queries and updates
• Linear Programming: A general advanced approach to solving many optimization problems
• Computational Geometry: Some basic algorithms involving space, shapes, intersections, etc.
• Van Emde Boas Trees: A neat optimization on search trees that are very fast
• Approximation Algorithms: Approaches for when you can’t find the optimal solution fast

Homeworks

There will be six programming challenges that we will give for homework. Each assignment should be done individually, but high-level discussion is allowed. Each assignment will consist of a problem statement and sample input/output. Gradescope will be available for submissions and assignments will be autograded. The general flow for homework assignements is:

• Friday before due date: The assignment will be released in lecture. We will discuss it briefly and everybody will work on it during class. I will walk around and help everyone get intuition on how to approach the problem and some of the tricks that needs to be overcome. During this class period you may collaborate with your neighbors and peers.
• Following Wednesday: The assignment is due on gradescope by midnight.
• Monday after that: Everybody gets an automatic extension to the following Monday evening. This is NOT intended to be used unless you absolutely need it. NO extensions will be given beyond this for ANY REASON.

Quizzes

There will be two quizzes given throughout the term. Please reference the course schedule for details on the dates and content of each quiz. Each quiz will be short and is meant to quickly test your basic understanding of the concepts from class. These will be held in-person, in-class, on specific Fridays throughout the term. The schedule can be referenced to see which Friday class periods have quizzes scheduled.

Final Project

There is NO final exam for this class. Instead, there is a final project. Each student will join a group of other students (3-4 per group) and be given an algorithm to study on their own. The group will need to do the following for their algorithm:

• Learn it: Study and understand the algorithm you were assigned / chosen.
• Apply it: Design a homework assignment that requires some application of the algorithm you studied.
• Solve it: Write the solution to your homework assignment, along with test cases that test the solution.
• Teach it: Create a slide-deck that teaches this algorithm to the class and present it to everybody in lecture.

More details on this project will be provided once it is available.

Grading

This course will use a standard weighted-average grading system. The grade breakdown is shown below:

• Homework (40 percent): There will be six programming challenges which account in total for 30 percent of the final grade.
• Quizzes (30 percent): There will be two in-class quizzes which account for 30 percent of the final grade.
• Attendance (12 percent): Attendance and participation are required in this course. Every lecture, a random subset of students will be chosen by a computer program for attendance. If your name is chosen and you are not present, you will lose 2 of these 12 percentage points.
• Final Project (18 percent): There will be a final project in which groups of students study, implement, prepare, and present one advanced algorithm of their choosing. Details will be available on the course website.