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.
Lecture Time: Tue, Thu 9:30AM - 11:30AM
Lecture Location: Remote: real time and recorded
Credits: 4
Please sign up for the course on Piazza. You can post all questions related to lectures, quiz, and assignments on Piazza. Instructor posts announcement on piazza.
Instructor: Kelin Luo
Office: 306 Davis Hall
Office Hour: TBD
Except for the office hours provided, you can also schedule an appointment with me via email for additional office hours at least two days in advance.
Email: [first name][last name][at][buffalo][dot][edu]
You should have taken CSE 116 and (CSE 191 or MTH 311) and (MTH 141 or MTH 131 or MTH 121) or similar courses before. Engineering, Bioinformatics, Computational Physics, or Math Majors, Computer Science Minors, and Data Intesive Computing Certificate students only.
Upon completion of the course, students will be able to...
| Learning Outcomes | Method of Assessment |
|---|---|
| 1. compute, compare, and analyze runtime and function growth using asymptotic notation. | Quiz, Homeworks, Mid-term Exam, Final Exam |
| 2. identify functionality of basic data structures. | Quiz, Homeworks, Projects, Mid-term Exam, Final Exam |
| 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. | Quiz, Homeworks, Projects, Mid-term Exam, Final Exam |
| 4. use data structures in programming. | Quiz, Projects, Mid-term Exam, Final Exam |
| 5. implement and analyze basic algorithms such as searching and sorting, as well as recursive algorithms, tree traversal algorithms, and graph traversal algorithms. | Quiz, Homeworks, Projects, Mid-term Exam, Final Exam |
Your final grade will be computed as follows:
* Class Participation: 10% = 1% × (10 quizzes). Quizzes will be given weekly after the lectures.
* Homeworks: 20% = 5% × (4 homeworks).
* Programming Projects: 20% = 10% × (2 programming projects).
* Mid-term Exam: 20%. (2 hours)
* Final Exam: 30%. (2 hours)
Note: (1) Each component will receive a numerical score. The course grade will be based on the weighted total of all components. (2) Class participation includes attendance or quizzes. We will choose the best 10 scores out of a total of 11-15 quizzes for grading. (3) Although the weight of quiz is relatively low, it is a very
important and essential part for learning concepts and algorithms. Problems similar
to quiz may appear in the mid-term and final exams. (4) The mid-term and final exams will be closed-book. However, you will be allowed to bring in one double-sided 8.5"x11" page of notes. No other materials may be used.
The following outlines the grade breakdown that will be utilized for assigning grades in the course. Please note that these ranges may be subject to adjustment at the end of the semester to address any inconsistencies or hardships that may arise. It is important to emphasize that grades will not be curved/adjusted during the semester.
| Grade | Percentage |
|---|---|
| A | 90% - 100% |
| A- | 85% - 89.99% |
| B+ | 80% - 84.99% |
| B | 75% - 79.99% |
| B- | 70% - 74.99% |
| C+ | 65% - 69.99% |
| C | 60% - 64.99% |
| C- | 55% - 59.99% |
| D | 50% - 54.99% |
| F | Below 50% |
If you have a question about the grading of any piece of work, first consult on Piazza.
Any questions about the grading of a piece of work must be raised within
one week of the date that the work was returned by the teaching assistant or
the instructor.
Academic integrity is a fundamental university value. Through the honest completion of academic work, students sustain the integrity of the university and of themselves while facilitating the university's imperative for the transmission of knowledge and culture based upon the generation of new and innovative ideas. For more information, please refer to theGraduate Academic Integrity policy.
* Collaboration and Discussions: You are permitted to engage in discussions with your classmates regarding homework problems. Prior to discussing, please take the time to thoroughly consider each problem independently.
All solutions must be written in your own words and produced by you individually. If you collaborate with fellow students, you must provide their names when submitting your work.
* Use of Artificial Intelligence Technologies: The use of generative artificial intelligence, large language models (LLMs), and other artificial intelligence-related technologies is prohibited. This encompasses tools like OpenAI's ChatGPT, Google Bard, and AI models within search interfaces like Google or Bing. Utilizing these tools for course content creation, debugging assistance, idea generation, or similar purposes constitutes a breach of academic integrity. All work submitted for evaluation in this course must be exclusively your own.
* Consequences for Violations: Failure to follow to the aforementioned rules will be treated as cheating and a violation of academic integrity. In addition to receiving an immediate grade of F for the course, further actions in alignment with theDepartment's Academic Integrity Policy and theUniversity's Academic Integrity Policy will be taken.
Here are some of the University's available free resources:
* If you need help with writing, check UB Center for Excellence in Writing theWriting Support Services
* If you have issues with your device, the UB University Libraries provides access to computers, as well as equipment loans, see theEquipment Loans
* Your well-being is highly important, if you have any concerns, please check theCounseling Service
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 theAccessibility Resources.
There are no required textbooks for the course. All needed materials will be provided via the course's website.
Similar courses taught at UB:
| HWs/Projects | Releasing Date | Deadline |
|---|---|---|
| HW1 | Jun 03 | Mon, Jun 10 |
| HW2 | Jun 10 | Mon, Jun 17 |
| Project 1 | Jun 10 | Mon, Jun 24 |
| HW3 | Jul 01 | Mon, Jul 08 |
| HW4 | Jul 08 | Mon, Jul 15 |
| Project 2 | Jul 08 | Mon, Jul 22 |
Late assignments will be accepted up to 2 days late (by Email submission) for a penalty of 50% of the total points (lower your earned points by 50% of the possible points for the entire assignment).
If your latest submission was submitted:
* On or before the deadline: 100% of what you earn.
* Late penalty to 1 day (< 24 hours): 25% point penalty.
* Late penalty to 2 days (< 48 hours): 50% point penalty .
* > 2 days late: 0 points.
| Week | Date | Contents | Other Notes |
|---|---|---|---|
| 1 | May 28 | Course Syllabus and Course Introduction | |
| May 30 | Math Basics and Python Basics | ||
| 2 | Jun 04 | Complexity and Asymptotic Analysis | |
| Jun 06 | Abstract Data Types (ADTs): Array, ArrayList | ||
| 3 | Jun 11 | LinkedLists | HW 1 deadline Jun 10 |
| Jun 13 | Recursion | ||
| 4 | Jun 18 | Stack and Queues | HW 2 deadline Jun 17 |
| Jun 20 | Searching and Sorting | ||
| 5 | Jun 25 | Mid-term exam | P1 deadline Jun 24 |
| Jun 27 | Graphs: Adjacency Lists and Matrices, Traversals | ||
| 6 | Jul 02 | Shortest Path, Priority Queues, Heaps | |
| Jul 04 | Independence Day Holiday, no class | ||
| 7 | Jul 09 | Binary Search Trees | HW 3 deadline Jul 08 |
| Jul 11 | Balanced Tree | ||
| 8 | Jul 16 | Introduction to Hash Tables, Hash variants | HW 4 deadline Jul 15 |
| Jul 18 | Hash Table, Bloom Filters | ||
| 9 | Jul 23 | Review/Questions | P2 deadline Jul 22 |
| Jul 25 | Final Exam, Thursday, 09:30-11:30 |