Data Structures and Algorithms in C++
Schedule
| Date | Topic | Readings | Assignments | ||
|---|---|---|---|---|---|
| Jan. 27 | C++ review/Inheritance | ||||
| Jan. 29 | Polymorphism/Exceptions | Planning, C++ Review, OOP, Exceptions | |||
| Feb. 3 | Recursion | Recursion | PA1 out | ||
| Feb. 5 | Snow day! | ||||
| Feb. 10 | Recursion | PA2 out | |||
| Feb. 12 | Quiz 1; Searching/Complexity analysis |
Complexity & Searching | PA1 due | ||
| Feb. 17 | No class—Presidents day | ||||
| Feb. 19 | Sorting | Sorting | |||
| Feb. 24 | More sorting | PA2 due | |||
| Feb. 26 | Exam 1 | ||||
| Mar. 3 | Data structures and ADTs; Lists/Vectors | Data structures and ADTs | |||
| Mar. 5 | Vectors/Linked Lists; Exam 1 Extra Credit | Due: get the code from last class to compile; implement isEmpty() and size() for Vector |
|||
| Mar. 10 | Linked lists | HW1: Lists due | |||
| Mar. 12 | Linked | HW2 due: implement add() method of SinglyLinkedList (submit on Canvas, no late days) |
|||
| Mar. 18, 20 | No class—Spring break | ||||
| Mar. 24 | Stacks and Queues | Stacks and queues | HW 3: Linked Lists due; Questions for reading due | ||
| Mar. 26 | Quiz 2; Stacks and Queues |
||||
| Mar. 31 | Trees | Trees | HW 4: RPN due | ||
| Apr. 2 | Binary Search Trees | BSTs | HW 5: Trees due | ||
| Apr. 7 | Binary Search Trees | HW 6: BST insert due | |||
| Apr. 9 | Exam 2 | ||||
| Apr. 14 | Binary Search Trees | ||||
| Apr. 16 | Hash tables | Hash tables | |||
| Apr. 21 | No class—Patriots day | ||||
| Apr. 23 | Hash tables | ||||
| Apr. 28 | Quiz 3; Hash tables | ||||
| Apr. 30 | Graphs | Graphs | HW8 due | ||
| May 5 | Graphs | HW9 due | |||
| May 7 | Graphs | ||||
| May 12 | Review | ||||
| May 14 10:15am–12:15pm |
Final Exam | ||||
Assignments
Programming Assignments and Homeworks
Each programming assignment is worth 10 points. They will be listed below as they become available.
- PA1: Recursion (Due Feb. 10)
- PA2: Sorting (Due Feb. 24)
- Homework 1: Lists (Due Mar. 10)
- Homework 2 (Due Mar 12): implement
add()method of SinglyLinkedList (submit on Canvas, no late days) - Homework 3: Linked Lists (Due Mar. 24)
- Homework 4: RPN (Due Mar. 31)
- Homework 5: Trees (Due Apr. 2 @ 2pm)
- Homework 6: BST insert (Due Apr. 7 @ 11:59pm)
- Homework 7: TreeMap (Due Apr. 17 @ 11:59pm)
- Homework 8: STL map (Due Apr. 30 @ 2pm)
- Homework 9: Graph parser (Due May. 5 @ 11:59pm)
Lecture Notes/Resources
- Jan. 27 — Solutions to pre-test
- Jan. 29 — TPS—OOP
- Feb. 4 — TPS—Recursion
- Feb. 11 — Lecture notes on recursion; TPS solutions
- Feb. 12 — Lecture notes on complexity and searching
- Feb. 19 — TPS answers, Lecture notes on sorting, Function pointers and namespaces (.cpp)
- Feb. 24 — TSP, Notes, exam topics, Pointers/templates (cpp)
- Mar. 3 —
Notes,
main.cpp,
List.h,
Vector.h,
Vector.cpp; to compile:
g++ main.cpp Vector.cpp -o main - Mar. 5 — Notes, Vector.cpp
- Mar. 10 — Notes, SinglyLinkedList.h, SinglyLinkedList.cpp
- Mar. 12 — Notes, Templates: List.h, Vector.h, Vector.hpp, vector-main.cpp
- Mar. 24 — Notes, Stack.h, SinglyLinkedListStack.h
- Mar. 26 — Implementation of List/Vector/SinglyLinkedList (Canvas), The stack and queue files can be found on Canvas as part of HW4
- Mar. 31 — Notes, trees.cpp
- April 2 — Notes, trees.cpp (with function pointers)
- April 7 — Notes
- April 14 — Notes
- April 16 — Notes, hash-examples.cpp, video about hash tables (Harvard), page about hash tables
- April 16 — TSP, hash-table.cpp
- April 28 — stl-example.cpp
- April 30 — TSP, Notes
- May 5 — Notes
- May 7 — Notes, Dijkstra's Algorithm (wikipedia)
- May 12 — Notes
Topics
Basics/CSC160 stuff
- Command line basics
- Getting a compiler set up
- Compiling and running a program
- Planning
- CSC160 page
- Style
CSC161 stuff
- C++ Review
- OOP, inheritance, and Polymorphism
- Exceptions
- Recursion
- Complexity analysis
- Searching
- Sorting
- Data structures and ADTs
- Stacks and queues
- Trees
- Binary Search Trees (BST)