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)
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.
| 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 |
| 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.
| Date | Deliverable | Topic | Materials |
|---|---|---|---|
| Mon 08/30/21 | Intro, Logistics | ||
| 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 | DFS, BFS, Analysis | ||
| Fri 10/15/21 | PA1-Tests | Priority Queues, Orderings | |
| 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 | ||
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.
| # | 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:
0: Not supported 1: Minimally Supported 2:Supported 3: Strongly Supported
| Program Outcome | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Support Level | 2 | 2 | 0 | 0 | 2 | 2 |
| Program Outcome | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Support Level | 2 | 1 | 0 | 0 | 2 | 0 | 1 |
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 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 your score earned minus 50 points and 0 points. No grace days may be applied to written assignments.
The policy for submissions on programming assignments is as follows:
From this policy, you will see that all assignments must be submitted within two days past the assigned deadline. Each submission receives a grade based on the date it was submitted. Your final score is the highest score of any of your individual submissions. 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 January 12 at 3pm and Bar.scala on January 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.
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. You must receive a passing final exam score (50% orhigher) 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 in lecture and recitation 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.
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.
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.
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).
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
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.
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:
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.
Here are some other policies/suggestions to keep in mind:
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.
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.
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.
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).
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 University Undergraduate Academic Integrity policy.
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.
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.
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:
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 2024-09-19 13:18:42 -0400