This course is designed by Michael Hahsler for learning basic data structures, their implementation for current hardware, and their performance tradeoffs. We will use C++, a language widely used to implement performance-critical components of applications. C++ provides access to low-level memory management facilities and is therefore well-suited for learning about data structures and their efficient implementations. It will provide the basis for understanding the impact of the used data structures on memory consumption and runtime. This knowledge is especially important when using managed programming languages like Java or Python which hide important aspects from the programmer.
Textbook: Data Structures and Algorithm Analysis in C++ (Fourth Edition), by Mark Allen Weiss. Source Code by Mark Allen Weiss can be found here.
This course assumes that you know the basics of C++ programming, object-oriented design, and memory management from an introductory C++ course. To make sure you are ready, work through HOWTO prepare for this data structures course.
| Book Chapter | Lecture Notes and Code |
|---|---|
| 1 | Programming |
| 2 | Algorithm Analysis |
| 3 | Lists, Stacks, and Queues |
| 4 | Trees |
| 5 | Hashing |
| 6 | Heaps |
| 7 | Sorting |
| 9 | Graphs |
Code developed in class can be found in the CS2341_Scratch repository.
Course material and assignments for CS 2341 at SMU can be found on Canvas.
- Install Visual Studio Code (VS Code)
- Install compilers and
cmake:- On Linux you most likely have already everything you need installed (
gcc,cmake,valgrind). If not, then install the missing packages using your package manager (e.g., on Ubuntu usingsudo apt-get install build-essential cmake valgrind). - On Windows you will need to install WSL and use the VS Code remote-WSL Extension. You also need to install
cmakeandvalgrindusing the WSL shell (sudo apt-get install build-essential cmake valgrind). You will always need to open folders by clicking on the green><at the bottom left corner of VS Code and select open folder in WSL. - On MacOS you need to install clang and set up the path using shell command. You also need to install cMake (follow the instructions carefully and set the PATH). An installation option is Homebrew.
- On Linux you most likely have already everything you need installed (
- Install git and then you can use the VS Code integration.
- Install VS Code extensions for C++ and CMake.
The extensions are:
C/C++,C/C++ Extension Pack,CMake Tools. VS Code will prompt you to install these. Make sure that you install the extensions after you have the software above installed or it might not find it during setting up the extension.
If you have access to a linux host server with all development tools installed (see Genuse servers for SMU students) then you can work on the server by installing only VS Code and the VS Code extension Remote - SSH on your computer. You can then connect to the linux host by clicking on the green >< at the bottom left corner of VS Code (details).
This is a good option if certain tools
are not available for your computer architecture (e.g., valgrind is not available for MacOS with M1 and M2 processors).
Details on how to use ssh and the shell can be found below.
- HOWTO prepare for this data structures course
- GitHub Quickstart
- HOWTO Use a Shell and SSH
- HOWTO Compile Programs With VS Code and CMake
- HOWTO Good Coding Practice
- HOWTO Debug
- HOWTO Detect Memory Leaks
- HOWTO Test
- HOWTO Profile Code
All code and documents in this repository are provided under Creative Commons Attribution-ShareAlike 4.0 International (CC BY-SA 4.0) License.