CSE 💯: Advanced Data Structures

Welcome to CSE 100!

This course will help you:

• Select appropriate data structures to solve problems, considering their strengths and weaknesses
• Implement advanced data structures in C++, which might include any of: Binary Search Trees, Balanced Trees, Heaps, Treaps, Randomized Search Trees, Graphs, and Priority Queues
• Critique different implementations of the same ADT/data structure
• Implement core algorithms that leverage advanced data structures, such as compression algorithms and graph algorithms
• Design and Debug medium-scale C++ programs
• Use the C++ STL effectively
• Use a version control system (git) for code management
• Derive best-case, worst-case and average-case running times of core data structures
• Compare empirical running times to theoretical expectations
• and more!

The specific data structures covered in this version of CSE 100 will include:

• Binary Search Trees
• Balanced trees (AVL trees, Red-Black Trees, B-Trees)
• Tries
• Ternary Search Trees
• Hash tables
• Graphs
• Possibly one or two additional advanced data structures

Prerequisites

CSE 100 has the following prerequisites: CSE 12, CSE 21 or Math 15B, and CSE 30 or other C or C++ experience. We do expect you to have at least some C and/or C++ experience, as well as the following knowledge and skills:

• Designing and implementing code for basic data structures and ADTs such as linked lists, stacks, and queues.
• Performing running time analysis using Big-O notation
• Writing C++ programs
• Debugging C ++ programs using the gdb debugger
• Working with basic probabilities