Algorithms Part 1 by Princeton University

Self-study "workbook" for programming assignments implemented in Typescript.

npm install

Week 1

Union find algorithms

• Quick Find
• Quick Union
• Quick Union w/weighting
• Quick Union w/weighting and path compression

npm run w1test

Assignment

• Percolation problem

npm run w1assignment

Week 2

Stacks and Queues

• Stack w/linked list

• Stack w/resizable array

• Queue w/linked list

• Queue w/resizable array

• Queue w/circular resizable array

• Bag with Iterator

• Arithmetic expression evaluation (Dijkstra's two stack algorithm)

• Selection sort

• Insertion sort

• Shell sort

• Shuffling

npm run w2test

Assignment

• Deque implementation using
  • Linked list
  • Resizable array
  • Circular resizable array

  npm run w2assignment-deque
  

• Randomized queue

  npm run w2assignment-randomized-queue
  

Week 3

Mergesort & Quicksort

• Mergesort Recursive implementation
• Mergesort Bottom-up implementation (w/o recursive)
• Quicksort implementation w/o shuffling
• Quicksort implementation w/shuffling

npm run w3test

Assignment

npm run w3assignment

Week 4

Priority Queues

• MaxPQ implementation w/unordered array

• MaxPQ implementation w/binary heap

• MinPQ implementation w/unordered array

• MinPQ implementation w/binary heap

• HeapSort implementation

• Binary Search Tree basic operations

• Find k-th min/max elements in array using Priority Queue (just for fun)

npm run w4test

Week 5

Balanced Search Trees

• Red-Black Binary Search Tree implementation (w/o deletion)

npm run w5test