shiva-karthick / competitive-programming Goto Github PK

HackerRank Practice Java, C++, Algorithms

• What are some useful features of java that you are allowed to use in CS2040s?
  • ArrayList(better than standard arrays), LinkedList, PriorityQueue, HashMap, HashSet that's about it I think
  • You will be implementing most of the data structures yourself
  • most of the linear data structures are available in java.util

Linear Data Structures:

• Arrays
• Lists (ArrayList/LinkedList)
• Stack (Stack)
• Queue (use the LinkedList class - O(1) enqueue and dequeue time)
• Map (Either HashMap/HashSet)

Nonlinear Data Structures:

• Binary Heap (PriorityQueue)
• PriorityQueue (PriorityQueue)
• UFDS (implement your own)
• Tree (implement your own - typically has to be a balancing one),
• Graphs (can represent them using Arrays for adjMatrix, List<List> for adjList and List<Triple> for edgeList)
• TreeMap and TreeSet available but don't really need to use as much. (These are lifesavers for where you need map ordered by keys)

I think this covers 2040S DS portion For Algorithms I remember:

Linear:

• Hashing Algorithm (just a brief overview)

Non-linear (Primarily for Graphs and Trees):

Traversal:

• Breadth First Search [BFS]
• Depth First Search + variations (inorder/preorder/postorder) [DFS]

MST:

• Prim's
• Kruskal's

Strongly Connected Components:

• Kosaraju's

Single Source Shortest Path:

• Bellman-Ford
• Dijkstra (modified and non-modified)
• BFS

All Pairs Shortest Path:

• Floyd-Warshall
• Dijkstra from every node

CS2040

• https://takefivee.wordpress.com/2021/06/24/cs2040-data-structures-and-algorithms/
• https://www.reddit.com/r/nus/comments/oxz7ct/cs2040_under_tst/