CSE 30331/CSE 34331 is about the data structures and algorithms that are the core of computer science and the building blocks for nearly every computer program you will write. In this course, you will explore the fundamental techniques in the design and analysis of non-numerical algorithms and their data structures. Elementary data structures such as lists, stacks, queues and more advanced ones such as priority queues and search trees will be examined along with design techniques such as divide-and-conquer in the context of sorting and searching and graph algorithms.
Upon successful completion of this course, you will know these data structures inside and out:
Inside: You will be able to analyze the performance of data structures in order to select the right one for each situation, as well as create or extend data structures to fit new situations.
Outside: You will be able to combine data structures to solve real world problems, employing abstractions to make them work together cleanly and safely.
Unit | Date | Topics | Assignment |
---|---|---|---|
Introduction | 08/24 | Introduction, Syllabus Slides (Bui) Slides (Kumar) Handout | Reading 00 |
08/26 | ADTs, Complexity Slides (Bui) Slides (Kumar) | ||
Unit 1: Fundamental Data Structures | 08/29 | C++, Dynamic Arrays Slides (Bui) Slides (Kumar) | Reading 01 |
08/31 | Linked Lists Slides (Bui) | Challenge 01 | |
09/02 | Stacks, Queues, Deques Slides (Bui) | ||
09/05 | Binary Trees Slides (Bui) | Reading 02 | |
09/07 | C++11, Smart Pointers | Challenge 02 | |
09/09 | Arithmetic Scheme Interpreter | ||
Unit 2: Sorting and Priority Queues | 09/12 | Priority Queues, Binary Heaps Slides (Bui) | Reading 03 |
09/14 | Selection Sort, Insertion Sort, Heap Sort Slides (Bui) | Challenge 03 | |
09/16 | Recursion, Divide and Conquer Slides (Bui) | Project 01 | |
09/19 | Merge Sort Slides (Bui) | Reading 04 | |
09/21 | Quick Sort Slides (Bui) | Challenge 04 | |
09/23 | Sorting Linked Lists Slides (Bui) | ||
Unit 3: Searching and Search Trees | 09/26 | Binary Search and BSTs Slides (Bui) | Reading 05 |
09/28 | B-Trees Slides (Bui) | Challenge 05 | |
09/30 | Red-black Trees Slides (Bui) | Project 02 | |
10/03 | Red-black Trees | Reading 06 | |
10/05 | Treaps Slides (Bui) | Challenge 06 | |
10/07 | Key-Value Store I Slides (Bui) | ||
Midterm | 10/10 | Review | |
10/12 | Checklist 01 | ||
10/14 | Midterm | ||
Fall Break | |||
Unit 4: Hash Tables | 10/24 | Hash Tables Slides | Reading 07 |
10/26 | Separate Chaining Slides | Challenge 07 | |
10/28 | Hash Functions Slides | Project 03 | |
10/31 | Open Addressing Slides | Reading 08 | |
11/02 | Bucket Sort Slides | Challenge 08 | |
11/04 | Bitsets Slides | ||
Unit 5: Graphs | 11/07 | Graph Representations Slides | Reading 09 |
11/09 | Graph Traversals Slides | Challenge 09 | |
11/11 | Topological Sort Slides | Project 04 | |
11/14 | Shortest Path Slides | Reading 10 | |
11/16 | Minimum Spanning Tree Slides | Challenge 10 | |
Miscellaneous Topics | 11/18 | Git Slides | |
11/21 | Map-Reduce Slides | Reading 11 | |
11/23 | Thanksgiving | ||
11/25 | Thanksgiving | ||
11/28 | Bloom Filters Slides | Challenge 11 | |
11/30 | Test-Driven Development | Project 05 | |
Final Project | 12/02 | Sprint | |
12/05 | Sprint | ||
12/07 | Presentations | ||
12/09 | Presentations Slides | Final Project | |
Final | 12/12 | Final (Bui) Checklist 02 | |
12/15 | Final (Shreya) |
Component | Points |
---|---|
Readings Weekly reading assignments and corresponding writing prompts. | 10 × 4 |
Challenge Weekly individual programming challenges. | 10 × 4 |
Projects Collaborative group programming projects. | 6 × 20 |
Exams A midterm and a comprehensive final exam. | 40 + 60 |
Total | 300 |
Grade | Points | Grade | Points | Grade | Points |
---|---|---|---|---|---|
A | 282-300 | A- | 270-281 | ||
B+ | 260-269 | B | 250-259 | B- | 240-249 |
C+ | 230-239 | C | 220-229 | C- | 210-219 |
D | 180-209 | F | 0-179 |
All your Readings, Challenges, and Projects are to be submitted to your own private GitLab repository.
Students are expected to attend and contribute regularly in class. This means answering questions in class, participating in discussions, and helping other students.
Foreseeable absences should be discussed with the instructor ahead of time.
Notre Dame has implemented an Echo360 classroom recording system. This system allows us to record and distribute lectures to you in a secure environment. You can watch these recordings on your computer, tablet, or smartphone. The recordings can be accessed within Sakai. Look for the tool labeled "Echo360 ALP" on the left hand side of the course.
Because we will be recording in the classroom and/or using an active learning environment, your questions and comments may be recorded. (Video recordings typically only capture the front of the classroom.) If you have any concerns about your voice or image being recorded, please speak to me to determine an alternative means of participating. No content will be shared with individuals outside of your course without your permission except for faculty and staff that need access for support or specific academic purposes.
These recordings are jointly copyrighted by the University of Notre Dame and your instructor. Posting them to other websites, including YouTube, Facebook, Vimeo, or elsewhere without express, written permission may result in disciplinary action and possible civil prosecution.
In the case of a serious illness or other excused absence, as defined by university policies, coursework submissions will be accepted late by the same number of days as the excused absence.
Otherwise, there is a penalty of 25% per day late (except where noted). You may submit some parts of an assignment on time and some parts late. Each submission must clearly state which parts it contains; no part can be submitted more than once.
All work that you submit must be your own. Collaboration is encouraged but must be disclosed by all parties. Print or online resources are allowed, but must be disclosed. However, you may not look at solutions from other current or past students, or any other source.
Any student who has a documented disability and is registered with Disability Services should speak with the professor as soon as possible regarding accommodations. Students who are not registered should contact the Office of Disability Services.