cs2040_DSnA

Useful Links:

Main page: http://www.comp.nus.edu.sg/~stevenha/cs2040c.html

https://visualgo.net/en

Practice:

http://adventofcode.com/ https://open.kattis.com/

If you have time:

https://projecteuler.net/

Topics tested:

1. Sorting
   1. Bubble, Insertion, Selection, Radix (Counting), Merge, Quick
2. List ADT:
   1. Stack, Queue, LL, DLL, Deque, Priority Queue (Binary Heap)
3. Table ADT:
   1. Hash Table, BST, AVL
4. Graph ADT:
   1. AM, AL, EL
5. Graph Traversal
   1. DFS/BFS and uses (traversing, cycle detection, CCs, size of CCs, floodfil, Toposort on DAG, Bipartite Graph Check)
6. SSSP
   1. Unweighted Graph - BFS
   2. Weighted Graph - Dijkstra’s
   3. Weighted Graph with negative weight edge but NO NEGATIVE CYCLE - Modified Dijkstra
   4. Weight Graph with negative weight cycle - Bellman Ford
7. All-Pairs Shortest Paths
   1. Floyd Warshall
8. Special Graphs
   1. Directed Acyclic Graph, Tree, Eulerian Graph (path which visits each edge of the graph exactly once), Bipartite Graph