Data Structures and Algorithms

Build

g++ <program>.cpp -o <program>.o -std=c++17

There are various exercises covering:

• hashtables, sorting/hashing, heaps, stacks, arrays, linked lists, priority queues
• big-O analysis
• NP-complete problems (traveling salesman, knapsack), Dijkstra, A*, binary search trees
• Basic tree construction, traversal and manipulation algorithms; binary, n-ary, and trie-trees.
• Balanced binary tree, red/black tree, splay tree, or an AVL tree.

Complete Binary Tree: All levels are completely filled except possibly the last level Balanced Binary Tree: The height of the left and right subtrees of every node differ by at most one. Spray Tree: A self-adjusting BST that reorganizes recently accessed elements closer to root Red/Black Tree: A self-balancing BST where each node has an extra bit for denoting red or black. AVL Tree: A self-balancing BST where the height of the left and right subtrees of any node differ by at most one.