CSE-350 Data Structures (Spring 2024; As CSE-410)

This course expands on CSE 250 by introducing techniques for data organization that account for the memory hierarchy and the need for concurrent access. Topics include IO Complexity, On-Disk Tree- and Hash- based structures, Write-optimized data structures (e.g., LSM Indexes and Beta-Epsilon Trees), Serialization/Data Layout, Caching, Secondary Indexes, Concurrent Data Structures, and Versioned Data Structures.

3 credit hours


When: M/W/F 2:00 PM - 2:50 PM
Where: Baldy 206

Course Staff

Instructor: Oliver Kennedy
Office Hours: Weds 12:00-1:50
Web: https://odin.cse.buffalo.edu

You should never hesitate to come ask questions in office hours, whether it be a simple/fundamental question, something more advanced that you are interested in, or simply to chat about the material/department/life in general. Remember that you are always welcome with any level of question and should not be shy to ask. Please report any issues/concerns with office hours ASAP so we can address problems early in the semester.

If you need to email course staff, please include [CSE 350] at the beginning of the subject line so your email is not missed. Email omitting this tag from the subject or from non-UB accounts will be ignored.

Important Dates

March 4, In Class [ review | annotated | rubric ]
Oliver Traveling, No Class
March 8
Spring Break, No Class
March 18-22
Resign Deadline
April 16
Final Exam
May 10, 3:30-6:30 (tentative) [ review | rubric ]

Deadlines (expected)

Course Resources

Online Resources

Topics Covered

Introduction [ notes ]
Course logistics and high level overview.
Rust Basics [ notes ]
How Rust differs from Java, and how to work with the borrow checker.
Background: Data Structures and SQL [ notes ]
A review of 250, collection data models, and SQL.
Data Serialization [ notes | cdf-index ]
An overview of how structured/collection data is represented in memory (and on disk).
The RAM and EM models [ notes ]
A review of the memory hierarchy, formalizing the external memory model, and an overview of techniques for managing data in external memory, including sorting as an example.
B+ Trees [ notes ]
We build a B+ Tree from first principles and binary search
Write-Optimized structures [ lsm_trees | bslm_trees | crimson_db | beta_epsilon | notes ]
We build up LSM trees and Beta-Epsilon Trees from first principles
The Shuffle Operation [ notes ]
We explore on-disk hashing and related strategies for partitioning data into manageable chunks
Bloom Filters [ notes ]
Using compact summary structures to avoid expensive on-disk operations
Dataframe Storage [ notes ]
We design, from first principles, a storage format for persistent, mutable dataframes (aka relational tables)
Buffer Management
We add support for caching to our dataframe storage model
Transactions Overview [ notes ]
ADT support for combining multiple operations together into a single, atomic operation.
Locking [ notes ]
Efficient strategies for enforcing transaction isolation on dataframes through locks
Logging [ slides ]
How to enforce transaction durability, how to efficiently support atomic durability, and an overview of the ARIES recovery protocol
Clustered and Unclustered Indexing
We extend our dataframe storage model with support for indexing and explore techniques for supporting efficient access over multiple attributes.
Versioned/Immutable Data
What are immutable data types, and how they can be used to support efficient concurrent access to data
Sketches (time-permitting) [ flajolet_martin | count | count_min ]
The statistical tricks that allow expensive data statistics to be computed using Count-Min and Hyperloglog


Data Structures (CSE 250) and Systems Programming (CSE 220) should be completed prior to enrolling in this course. There will be assignments with an implementation component that requires prior knowledge/experience with programming. We will also be making extensive use of asymptotic complexity (Big-O).

Course Requirements


Homework assignments for this course will be composed of:

There are two categories of assignments which will be given alongside one another. Programming assignments will generally take 3 weeks and be assigned an extra week prior to the previous assignment being due. Several assignments build on one another, and so it may be difficult for you to complete a subsequent assignment if you have difficulty with the first. For example, a programming assignment may ask you to build on the efforts of a prior programming assignment, or a writing assignment may require a complexity analysis of your implementation. Due to the nature of the content of the course, you may be required to analyze code that you have written, in addition to providing correct solutions to the problems. At the instructor's discretion, the class may be provided with a working implementation of a programming assignment after its due date has passed. You must score a 100% on the Academic Integrity and Setup assignments or you will be given an F in the course.

For homework assignments, we will only be accepting electronic submissions. These will be accepted via Autolab. Assignments will be submitted as described in the write-up. Written submissions are generally accepted in the form of a PDF. There are two ways to complete your written homework:

Make sure to double check your assignments before and after submission to ensure that part of your writing wasn't chopped off or distorted, as the integrity of your submission is your responsibility. Also, if you handwrite an assignment, make sure that you write legibly. You will not receive credit if your submission is invalid/corrupt/wrong file format or if your submission is illegible. It is fully your responsibility to determine if your submission is valid.

Late Policy

Late written assignments will be accepted up to 1 day late for a penalty of 50% of the total points. For example, if the homework is worth 100 points and you submit it one day late, you will receive the maximum of zero points, or your score earned minus 50 points.

Late programming assignments will be accepted up to 2 days late, for a penalty of 25% of the total points per day. For example, if the programming assignment is worth 100 points and you submit it one day late, you will receive the greater of zero points, or your score earned minus 50 points.

You have a total of five grace days to spend over the course of the semester. Each grace day can be used to negates one 'day' of late penalty for a homework or project. You may not use a grace day to submit a written assignment more than one day late or a programming assignment more than two days late. Grace days are automatically applied to the first instances of late submissions, and are non-refundable. Please plan accordingly. You will not be able to recover a grace day if you decide to work late and your score was not sufficiently higher.

Keep track of the time if you are working up until the deadline. Submissions become late after the set deadline, even by 1 minute.


There will be one midterm exam during the semester and one 3-hour final exam during finals week. The midterm exam is worth 15% of your grade. The final exam is worth 15% of your grade. We reserve the right to change the scaling of the exams.

No makeup exams will be given except in provably extreme circumstances. Please note the following additional policies/suggestions with respect to makeup exams:

Attendance and Participation

Attendance in lecture is not mandatory, but highly encouraged. You are, after all, paying us to deliver an interactive experience. If you don't understand something, wouldn't it be nice to just raise your hand and get to the bottom of it then and there? Lectures will typically be recorded, but recordings have been known to get corrupted; do not count on lecture recordings.

The instructor has also been known, in the past, to include questions on exams that can only be answered by students who regularly attend class.


There are no recitations.

Grading Policy

Here is the split of grades:

You must complete the AI Quiz and Setup assignments, or you will receive an F in the class.

An additional 1 point (max of 5 pt per student) will be awarded for every legitimate report of a typo in this syllabus or any assignment handout materials. Typos should be reported by email to the instructor. The point for any given typo will only be awarded to the first person to report it.

Here is a breakdown of the course grades required for the different letter grades.

Score (x) Letter Grade Quality Points
90% ≤ x ≤ 100% A 4.0
85% ≤ x < 90% A- 3.67
80% ≤ x < 85% B+ 3.33
75% ≤ x < 80% B 3.00
70% ≤ x < 75% B- 2.67
65% ≤ x < 70% C+ 2.33
60% ≤ x < 65% C 2.00
55% ≤ x < 60% C- 1.67
50% ≤ x < 55% D 1.00
0% ≤ x < 50% F 0

It is possible that these ranges and/or the grade weighting may be adjusted at the end of the semester to address inconsistencies or hardships that arise. Grades will not be curved/adjusted during the semester.

Students will receive a grade of F if they are found in violation of the academic integrity policy. Please make sure to thoroughly read and understand the policy for this course.

Students that do not participate in the class at all will receive a grade of F3, which denotes failure for non-attendance.. Students who do not complete a substantial portion of the course, or do not attend more than 60% of the course will receive a a grade of F2, which denotes failure for partial non-attendance.. Please note that there may be financial aid repercussions so you should consider resigning courses you are not planning on completing.


A grade of incomplete ("I") indicates that additional course work is required to fulfill the requirements of a given course. Students may only be given an "I" grade if they have a passing average in coursework that has been completed and have well-defined parameters to complete the course requirements that could result in a grade better than the default grade. An "I" grade may not be assigned to a student who did not attend the course. This is especially applicable in instances where a student misses work due to extenuating circumstances and are unable to makeup the work prior to the end of the semester. For example, missing the final exam due to a car accident and/or being hospitalized for an extended period during the semester are two examples where completing all coursework may not be possible before grades are due. See also: Explanation of Grades for more regarding the incomplete grade process. Incompletes will not be given as a shelter for poor grades. It is the student's responsibility to resign from the course in a timely manner if doing poorly. The last day to resign with a grade of R is April 16, 2024 (before 11:59:59pm).

Accessibility Resources

If you have any disability which requires reasonable accommodations to enable you to participate in this course, please contact the Office of Accessibility Resources in 60 Capen Hall, 716-645-2608 and also the instructor of this course during the first week of class. The office will provide you with information and review appropriate arrangements for reasonable accommodations, which can be found on the web at: http://www.buffalo.edu/studentlife/who-we-are/departments/accessibility.html

Critical Campus Resources

Sexual Violence

UB is committed to providing a safe learning environment free of all forms of discrimination and sexual harassment, including sexual assault, domestic and dating violence and stalking. If you have experienced gender-based violence (intimate partner violence, attempted or completed sexual assault, harassment, coercion, stalking, etc.), UB has resources to help. This includes academic accommodations, health and counseling services, housing accommodations, helping with legal protective orders, and assistance with reporting the incident to police or other UB officials if you so choose. Please contact UB’s Title IX Coordinator at 716-645-2266 for more information. For confidential assistance, you may also contact a Crisis Services Campus Advocate at 716-796-4399.

Mental Health Services

As a student you may experience a range of issues that can cause barriers to learning or reduce your ability to participate in daily activities. These might include strained relationships, anxiety, high levels of stress, alcohol/drug problems, feeling down, health concerns, or unwanted sexual experiences. Counseling, Health Services, and Health Promotion are here to help with these or other issues you may experience. You can learn more about these programs and services by contacting:

Study Time

In this course, you are expected to put in significant additional time beyond the scheduled class times. It is expected that for each credit hour for a course, students should typically expect to put in 2 to 3 hours of work each week outside of class. Since this course is 3 credit hours, expect roughly 6 to 9 hours of time outside of lecture and recitation each week. You may want to consider practicing coding to stay up to date and polish your skills to perform better on coding assignments. This is especially important if you don't feel confident about your programming after CSE-220, or complexity analysis after CSE-250. Additionally, the concepts and ideas of the theory in this course are not something you can simply memorize and regurgitate. You must understand the ideas and concepts in order to be able to apply them to different problems.

Miscellaneous Notes

Here are some other policies/suggestions to keep in mind:

  1. Your grade will solely depend on your performance in this semester: you will not get any opportunity to do extra work to improve your grade. It is your duty to make sure you understand what is expected of you. This course will require a fair bit of work so if you are busy this semester, please plan accordingly.
  2. If there is a genuine reason for re-grading, please contact the instructor within a week of when the graded material is handed out in class/completed in the grader. In particular, if you do not pick up/view your graded material on time, you may lose the opportunity to get back to us within the stipulated time period.
  3. Feel free to make up a group of students to work on homework and study the course. Piazza offers a mechanism to search for group-mates. In a course like this it is very important to discuss problems with one another to better study. Teaching is the best way to learn material!

Academic Integrity

As a gentle reminder, please re-read the academic integrity policy of the course. I will continue to remind you throughout the semester and hope to avoid any incidents.

What constitutes a violation of academic integrity?

These bullets should be obvious things not to do (but commonly occur):

You should know that seeking solutions to the assignment does not fall under solving the problem yourself. Things that may not be as obvious:

The assignments should be solved individually with only assistance from course staff and allowed resources. You may discuss and help one another with technical issues, such as how to get your compiler running, etc. It is not acceptable that you both worked together and have nearly identical code. If that is going to be a problem for you, don’t solve the problems in that close of proximity.

What Collaboration is Allowed?

There is a gray area when it comes to discussing the problems with your peers and I do encourage you to work with one another to solve problems. That is the best way to learn and overcome obstacles. At the same time you need to be sure you do not overstep and not plagiarize. Talking out how you eventually reached the solution from a high level is okay:

I used a stack to store the data and then looked for the value to return.

but explaining every step in detail/pseudocode is not okay:

I copied the file tutorial into my code at the start of the function, then created a stack and pushed all of the data onto the stack, and finished by popping the elements until the value is found and use a return statement.

The first example is OK but the second is basically a summary of your code and is not acceptable, and remember that you shouldn’t be showing any code at all for how to do any of it. Regardless of where you are working, you must always follow this rule: Never come away from discussions with your peers with any written work, either typed or photographed, and especially do not share or allow viewing of your written code.

If you have concerns that you may have overstepped or worked closely with someone, please address this with me prior to deadlines for the assignment, for example by sending me an email as below:

Dear Dr. Kennedy,

I wish to inform you that I ... on my submission for Assignment N. The functions foo() and bar() are not entirely of my own authorship. I wish to withdraw my submission to preserve academic integrity.

J.Q. Student
Person #12345678
UBIT: jqstuden

Sincerely, J

Upon receipt of this email, I would award J a zero for Assignment N, but disregard any AI issues with the problematic submission.

What Resources are Allowed?

With all of this said, please feel free to use any [files|examples|tutorials] that we provide directly in your code (with proper attribution). Feel free to directly use anything from lecture or recitations. You will never be penalized for doing so, but should always provide attribution/citation for where you retrieved code from. Just remember, if you are citing an algorithm that is not provided by us, then you are probably overstepping.

More explicitly, you may use any of the following resources (with proper citation/attribution in your code):

Omitting citation/attribution will result in an AI violation (and lawsuits later in life at your job). This is true even if you are using resources provided.

Lastly, if you think you are going to violate/have violated this policy, please come talk to me ASAP so we can figure out how to get you on track to succeed in the course. This policy on assignments is here so that you learn the material and how to think yourself. There is no benefit to submitting solutions (which likely exist in some form).

Formal Departmental AI Info

Academic integrity is a fundamental university value. Through the honest completion of academic work, students sustain the integrity of the university while facilitating the university's imperative for the transmission of knowledge and culture based upon the generation of new and innovative ideas.

The academic degrees and the research findings produced by our Department are worth no more than the integrity of the process by which they are gained. If we do not maintain reliably high standards of ethics and integrity in our work and our relationships, we have nothing of value to offer one another or to offer the larger community outside this Department, whether potential employers or fellow scholars. For this reason, the principles of Academic Integrity have priority over every other consideration in every aspect of our departmental life, and we will defend these principles vigorously. It is essential that every student be fully aware of these principles, what the procedures are by which possible violations are investigated and adjudicated, and what the punishments for these violations are. Wherever they are suspected, potential violations will be investigated and determinations of fact sought. In short, breaches of Academic Integrity will not be tolerated.

Departmental Statement on AI in Homework Assignments

The following statement further describes the specific application of these general principles to a common context in the CSE Department environment, the production of source code for project and homework assignments. It should be thoroughly understood before undertaking any cooperative activities or using any other sources in such contexts.

All academic work must be your own. Plagiarism, defined as copying or receiving materials from a source or sources and submitting this material as one's own without acknowledging the particular debts to the source (quotations, paraphrases, basic ideas), or otherwise representing the work of another as one's own, is never allowed. Collaboration, usually evidenced by unjustifiable similarity, is never permitted in individual assignments. Any submitted academic work may be subject to screening by software programs designed to detect evidence of plagiarism or collaboration.

It is your responsibility to maintain the security of your computer accounts and your written work. Do not share passwords with anyone, nor write your password down where it may be seen by others. Do not change permissions to allow others to read your course directories and files. Do not walk away from a workstation without logging out. These are your responsibilities. In groups that collaborate inappropriately, it may be impossible to determine who has offered work to others in the group, who has received work, and who may have inadvertently made their work available to the others by failure to maintain adequate personal security. In such cases, all will be held equally liable.

Departmental Policy on Violations of Academic Integrity

The CSE Department has a zero-tolerance policy regarding academic integrity (AI) violations.

When there is a potential violation of academic integrity in a course, the course director shall first notify the concerned students. This notification begins the UB Academic Integrity Policy review and appeals process (Consultative Resolution, Departmental Level Procedures, Decanal Level Procedures, Vice Provost Level Procedures).

Upon conclusion of the review and appeals process, if the department, school, and university have determined that the student has committed a violation, the following sanctions will be imposed upon the student:

  1. Documentation. The department, school, and university will record the student's name in departmental decanal, and university-level academic integrity violations databases.
  2. Penalty Assessment. The standing policy of the department is that all students involved in an academic integrity violation will receive an F grade for the course and may lose financial aid and/or lose financial support from the department. The course director may recommend a lesser penalty for the first instance of academic integrity violation, and the adjudication committees that hear the appeal at the department, decanal and provost level may recommend a lesser or greater penalty.

This page last updated 2024-05-17 15:43:39 -0400