CSE-250 Data Structures (Fall 2021)

This course provides a rigorous analysis of the design, implementation, and properties of advanced data structures. Topics include time-space analysis and tradeoffs in arrays, vectors, lists, stacks, queues, and heaps; tree and graph algorithms and traversals, hashing, sorting, and data structures on secondary storage. Surveys library implementations of basic data structures in a high-level language. Advanced data structure implementations are studied in detail. Illustrates the importance of choosing appropriate data structures when solving a problem by programming projects in a high-level language.

4 credit hours (3 credits for lecture + 1 credits for recitation)


Course Resources

Required Textbooks
Optional Textbooks
Online Resources

Course Staff

Oliver Kennedy (Instructor)

Please familiarize yourself with everyone involved with the course. We will strive to offer a large amount of office hour availability for students to interact with us, the course staff. 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 250] 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.


Lectures

Section Dates Time Location Registration #
Section A M/W/F 11:30 AM - 12:20 PM Knox 110 10573
Section B M/W/F 1:50 PM - 2:40 PM Davis 101 19963

Recitations

Section Dates Time Location Registration #
Section A1 M 10:20 AM - 11:10 AM Bell 340 10995
Section A2 M 9:10 AM - 10:00 AM Bell 340 18343
Section A3 M 4:00 PM - 4:50 PM Bell 340 10748
Section A4 M 3:00 PM - 3:50 PM Bell 340 11075
Section A5 Tu 3:00 PM - 3:50 PM Bell 340 11449
Section A6 Tu 11:30 AM - 12:20 PM Bell 340 17485
Section B1 M 8:00 AM - 8:50 AM Bell 340 19006
Section B2 Tu 10:20 AM - 11:10 AM Bell 340 10660
Section B3 W 3:00 PM - 3:50 PM Bell 340 20050
Section B4 M 11:30 AM - 12:20 PM Bell 340 11361
Section B5 Tu 1:00 PM - 1:50 PM Bell 340 17484
Section B6 Tu 2:10 PM - 3:00 PM Bell 340 17486

Please attend the recitation you are registered for.


Course Schedule

Date Deliverable Topic Materials
Mon 08/30/21 Intro, Logistics slides
Wed 09/01/21 Scala
Fri 09/03/21 Debuggers and Profilers
Sun 09/05/21 Add-Drop Deadline
Mon 09/06/21 No Class: Labor Day
Wed 09/08/21 AI0 Runtime Analysis
Fri 09/10/21 Runtime Analysis (contd...)
Mon 09/13/21 Collections, Sequences, ADTs
Wed 09/15/21 PA0 Array Lists
Fri 09/17/21 Linked Lists
Mon 09/20/21 Recursion Intro
Wed 09/22/21 Divide and Conquer, Tail Recursion
Fri 09/24/21 Recursion (contd...)
Mon 09/27/21 Recursive Analysis; Sorts
Wed 09/29/21 WA0 Recursive Analysis (contd...)
Fri 10/01/21 Data-Bounded Analysis
Mon 10/04/21 Composite Data Structures, Stacks, Shortest Path
Wed 10/06/21 PA1 Queues, Shortest Path revisited
Fri 10/08/21 Graphs Intro
Mon 10/11/21 Graph ADTs: Edge Lists
Wed 10/13/21 Graph ADTs: Adjacency List, Adjacency Matrix
Fri 10/15/21 DFS, BFS, Analysis
Mon 10/18/21 Midterm Review
Wed 10/20/21 Midterm Exam
Fri 10/22/21 Priority Queues, Orderings
Mon 10/25/21 PA2 Heaps
Wed 10/27/21 Trees
Fri 10/29/21 Binary Search Trees, Tree Iteration
Mon 11/01/21 WA1 Balanced Trees (AVL)
Wed 11/03/21 Balanced Trees (Red-Black)
Fri 11/05/21 Balanced Trees (contd...)
Mon 11/08/21 Associative Map ADTs
Wed 11/10/21 PA3 Hash Functions
Fri 11/12/21 Hash Table Basics
Fri 11/12/21 Resign Deadline
Mon 11/15/21 Hash Table Analysis
Wed 11/17/21 WA2 Hash Tables with Open Addressing
Fri 11/19/21 Double-/Cuckoo-Hashing
Mon 11/22/21 Bloom Filters
Wed 11/24/21 No Class: Fall Recess
Fri 11/26/21 No Class: Fall Recess
Mon 11/29/21 Secondary Storage (Paging)
Wed 12/01/21 PA4 Secondary Storage (B+Trees)
Fri 12/03/21 Buffer / Advanced Data Structures
Mon 12/06/21 Wrap-Up / Review
Wed 12/08/21 WA3 Wrap-Up / Review
Fri 12/10/21 Wrap-Up / Review
??? Final Exam

Prerequisites

Introduction to CS for Majors (CSE 116) and Discrete Structures (CSE 191) 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 covering many mathematics concepts that rely heavily on skills acquired in discrete structures (such as proofs and mathematical notations), so plan accordingly if you are not as comfortable with these topics.


Student Learning Outcomes

# Upon completing this course, students will be able to... Student Outcome (CS/CE)* Assessment Methods
1 compute, compare, and analyze runtime and function growth using asymptotic notation. (1,2,5,6) / (1,2,5,7) Written Assignments, Exams
2 identify functionality of basic data structures. (1,2,6) / (2,7) Written and Programming Assignments, Exams
3 identify the tradeoffs of different data structures, given their implementation. This also includes recognizing which situations benefit or suit the use of one data structure over another. (1,2,5,6) / (1,2,5,7) Written Assignments, Exams
4 use data structures in programming. (1,2,5,6) / (1,5) Programming Assignments
5 implement and analyze basic algorithms such as searching and sorting, as well as recursive algorithms, tree traversal algorithms, and graph traversal algorithms. (1,2,5,6) / (1,2,5,7) Written and Programming Assignments, Exams

The Student Outcomes from the Engineering Accreditation Commission of ABET have been adopted; see:

Program Outcome Support

0: Not supported   1: Minimally Supported   2:Supported   3: Strongly Supported

Computer Science ABET Outcomes Support
Program Outcome 1 2 3 4 5 6
Support Level 2 2 0 0 2 2
Computer Engineering ABET Outcomes Support
Program Outcome 1 2 3 4 5 6 7
Support Level 2 1 0 0 2 0 1

Course Requirements

Assignments

Homework assignments for this course will be composed of:

There are two categories of assignments which will be given alongside one another. Written assignments will generally be given on a shorter basis, with around 1 week to complete. Programming assignments will generally be longer and assigned over a larger time period, with around 2 weeks to complete. It is possible that not completing one assignment may disqualify you from completing another related one (for example, a programming assignment may ask you to implement something and then a follow-up written assignment may ask you to explain and analyze your code but if you do not have code, you cannot complete this work). 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. This will likely be separated between the written and programming assignment, though there is no requirement that this is the case. Expectations will be clearly noted when the assignments come out as well as the duration of the assignment. Please pay attention to the amount of time that each assignment provides and begin early. There will be roughly 1 written assignment due each week and roughly 1 programming assignment due every two weeks, though the frequency may be lesser. You must score a 100% on the Academic Integrity assignment 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 our system called Microbase and/or 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 for Written Assignments

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 your score minus 50 points (to a minimum of 0 points). No grace days may be applied to written assignments.

Early/Late Policy for Programming Assignments

The policy for submissions on programming assignments is as follows:

Each submission is graded individually according to the bonus/penalty scale above. Your final score for the assignment is the highest score earned for any submission. A new submission will never lower your grade. Note that all assignments must be submitted within two days past the assigned deadline. For assignments with multiple component submissions, only 1 penalty will be assessed based on the file submitted latest. If a staggered deadline is given (e.g., two components due one week apart), the earlier deadline will be a hard deadline and no late submissions will be accepted for the first component.

For example, suppose PA1 is a programming assignment assigned September 3 with 3 deliverables: Tests.scala, Foo.scala, and Bar.scala where testing in Tests.scala is due September 10 and a deadline of September 17 at 5pm. This means that Tests.scala will only be accepted until the hard deadline of September 10 with no late credit. Suppose you submit Tests.scala on September 10, Foo.scala on September 12, and Bar.scala on September 14 at 3pm. In this case, you would receive +3 points for PA1 (overall). Alternatively, if you submitted Foo.scala on September 12 at 3pm and Bar.scala on September 18 at 8pm you would be charged 2 grace days for PA1 due to the late submission of the Bar.scala component.

You will have the ability to use three grace days throughout the semester, and at most two per programming assignment (since assignments are not accepted beyond two days late). Using a grace day will negate the 25% point penalty for one day of late submission, but will not allow you to submit more than two days late.

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. Grace days are automatically applied to the first instances of late submissions, and are non-refundable. For example, if an assignment is due on a Friday and you make a submission on Saturday, you will automatically use a grace day, regardless of whether you perform better or not. Be sure to test your code before submitting, especially with late submissions, in order to avoid wasting grace days.

Keep track of the time if you are working up until the deadline. Submissions become late after the set deadline, even by 1 minute. Keep in mind that submissions will close 48 hours after the original deadline and you will no longer be able to submit your code after that time.

Exams

There will be one midterm exam during the semester and one 3-hour final exam during finals week. The midterm exam is worth 20% of your grade. The final exam is worth 40% of your grade. If you have taken the midterm exam and score higher on the final exam, then the final exam score will replace your midterm score. I reserve the right to change the scaling of the exams. A weighted average of your written assignments and final exam (0.3 * written percentage + 0.7 * final exam percentage) must exceed 50% or you will receive a grade of F in the course.

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 mandatory in order to succeed in this course. We may use online forms to take attendance in lecture, as well as to ask questions and provide an interactive lecture environment. Questions posed in lecture may be graded for participation or correctness. These questions will be in addition to attendance for the day. You may miss 3 lectures without penalty. After your third missed lecture, you will be penalized 2%-points per absence from your overall course grade.

Recitations

We will be meeting for recitation to go over homework assignments and any questions you have about the material. In addition, the recitations may review or extend lecture and are an excellent environment to ask more individual questions regarding the course material. Attendance in recitation is not mandatory, however, it is highly encouraged in order to perform well.


Grading Policy

Here is the split of grades:

The final exam grade will replace the midterm grade if it is higher.

Note: Failure on the final exam will result in failure of the course.

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 complete a substantial portion of the course (do not complete more than 60% | do not attend more than 60% of the course) and achieve a grade of F in the course will receive a grade of FX which denotes failure for non-attendance. This is only a grade designation for those students that have failed AND did not attend and is not awarded if you passed the course. Please note that there may be financial aid repercussions so you should consider resigning courses you are not planning on completing.

Incompletes

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 Friday, Nov. 12, 2021 (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 4 credit hours, expect roughly 8 to 12 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-116. 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.

Amnesty Policy

If you have concerns that you may have overstepped or worked closely with someone, please address this with me, 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. This amnesty policy only applies if you resch out to me (for example with an email like the one above) before we discover the AI violation on our own

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.

Portions of this syllabus derived from the CSE-250 2021 Spring syllabus by Andrew Hughes, and Ethan Blanton's Academic Integrity policy.


This page last updated 2021-08-31 00:18:46 -0400