CS302 - Data Structures
​using C++

Level: CS302
Overview: The goal of the course "CS302 - Data Structures" is to introduce you into the concepts of data structures emphasizing both on fundamental concepts but also their implementation using C++. 

Main Textbook

Download Full Course Syllabus

Download the Ubuntu 16.04 Virtual Machine with g++ 5.4

Note: to be used with VirtualBox

Makefiles & CMake

E-mail Contact of TAs (Spring 2019): Tung Dang (tung.dang@nevada.unr.edu), Mustafa Solmaz (msolmaz@nevada.unr.edu)

Lecture Slides and other Material

Section 1: What should be known

• CS302-1.1-Object-Oriented-Solutions
• CS302-1.2-Designing an ADT
• CS302-1.3-C++ Classes
• CS302-1.4-Recursion Basics
• CS302-1.5-Recursion with Arrays
  • CS302-1.5-1-Recursion Examples
• CS302-1.6-Towers of Hanoi
  • CS302-1.6-Towers of Hanoi - Slides
• CS302-1.7-Code ArrayBag Methods
• CS302-1.8-Other ArrayBag Methods
• CS302-1.8-(External Reading​)-C++ Classes
• CS302-1.9-Memory Allocation

Section 2: Link-based Implementation

• CS302-2.1-Linked Chain Concepts
• CS302-2.2-Core LinkedBag Methods

Section 3: Stacks

• CS302-3.1-The ADT Stack
• CS302-3.2-Using the ADT Stack
• CS302-3.3-Implementations of the ADT Stack

Section 4: Lists

• CS302-4.1-Lists
• CS302-4.2-Using the ADT List
• CS302-4.3-List Implementations

Section 5: Efficiency of Algorithms

• CS302-5.1-Algorithm Efficiency
• CS302-5.2-Understanding Big O
• CS302-5.3-Formal Definitions
• CS302-5.4-More Examples

Section 6: Sorting Algorithms & Efficiency

• CS302-6.1-Basic & Faster Sorting Algorithms

Section 7: Sorted Lists

• CS302-7.1-Sorted Lists
  

Section 8: Queues

• CS302-8.1-Queues & Priority Queues
• CS302-8.2-Implementation of Queues

Section 9: Trees - Binary Search Trees

• CS302-9.1-Trees
• CS302-9.2-Tree Implementations (BinaryTree)
• CS302-9.3.-Tree Implementations (BST)

Section 10: Heaps

• CS302-10.1-Heaps

Section 11: Dictionaries

• CS302-11.1-Dictionaries & Implementations

Section 12: Balanced Search Trees

• CS302-12.1-Balanced Search Trees Intro
• CS302-12.2-Balanced Search Trees
• CS302-12.3-Red Black Trees
• ​CS302-12.4.-Left-Leaning Red Black Trees Implementation
• Quick Summary: Balanced Search Trees​

Section 13: Graphs

• CS302-13.1-Introduction to Graphs
• CS302-13.2-Spanning Trees
  • CS302-X-Prim's Algorithm (new slides)
• CS302-13.3-Shortest Paths
  • CS302-X-Dijkstra's Algorithm (new slides))
• CS302-13.4-Traveling Salesman Problem
• CS302-13.5-Graph Coloring Problem (short)
• CS302-13.6-Boost Graph Library

Section 14: Processing Data in External Storage

• CS302-14.1-Processing Data in External Storage

Section 15: Intro to STL

• CS302-15.1-Intro to STL
  • Example of trailing return type of decltype(auto) use

Homework Assignments

Quizzes

• Homework #1 (N/A for Fall 2019)
• Homework #2 & Supporting Code Package (Fall 2019 Update)
• Homework #3 (Fall 2019 Update)
• Homework #4 (Fall 2019 Update)
• Homework #5 (Fall 2019 Update)
• Homework #6 & Supporting Code Package (from Online Resource) (Fall 2018) ​(Fall 2019 Update)​​
• Homework $7 (Fall 2019 Update)​​
• Homework #8 (aka "Grade Improvement Optional Assignment) (Spring 2019 Update)

• Homework #4 & Supporting Code Package (Fall 2018)
• Homework #5​ & Supporting Code Package (Fall 2018)
• Homework #6 (Fall 2018)
• Homework #7 (Fall 2018)
• Homework #8 & Supporting Code Package (from Online Resource) (Fall 2018)
• Bonus Assignment on Robot Navigation (Fall 2018)
• Bonus Assignment on the Art Gallery Problem (Fall 2018)

• Quiz #1 & Solutions (Spring 2019 Update)
• Quiz #2 & Solutions (Spring 2019 Update)
• Quiz #3 & Solutions (Spring 2019 Update)
• Quiz #4 & Solutions (Fall 2018)
• Quiz #5 & Solutions (Fall 2018)
• Quiz #6 & Solutions (Fall 2018)
• Quiz #7 & Solutions (Fall 2018)
• Quiz #8 & Solutions (Fall 2018)
• Quiz #9 & Solutions (Fall 2018)

Exam Study Guides

• Midterm Study Guide
• Midterm - Fall 2018 & Solutions​

​

• Final Exam Study Guide​
  • Example on sum of k-smallest values in BST
  • Examples on using Heaps with STL (and a bit on Priority Queues)
  • Example Task on Shortest Paths
  • Example on Trivial Hashing
  • Example on Depth-First Search for Graphs
  • Example on Breadth-First Search for Graphs
  • Example on Kruskal's Minimum Spanning Tree Algorithm
  • Example Task on the Traveling Salesman Problem
  • Example on the Traveling Salesman Problem with the Nearest Neighbor Heuristic
  • Example on using Graphs for Treasure Hunting
  • Example Task on Red-Black Trees
    • Reference for Nominal RBT Implementation
• Final Exam - Fall 2018

Material to help you with C++

Slides & Notes

• Variables, Basic Types, Control Structures​
• Introductory Examples and Notes on Smart Pointers
• Safe Memory Management using Smart Pointers

Suggested courses online

• Modern C++ Course (UNIBONN)

Build environment

• A Simple Makefile Tutorial
• What is a Makefile and how does it work? 
• CMAKE Tutorial (official)
• CMAKE by example blogpost
• CMAKE Cheatsheet​

---

Study links

• www.cplusplus.com/C++ Reference
• C++ Data Structures Cheat Sheet

Open-Source Code

• TBA

More

• Compile Test Code with OnlineGDB [link]