/Algorithms

important notes and topics for Algorithms

Algorithms

  1. Sorting - Quicksort, Mergesort, Heapsort
  2. Search - BST, Red-Black BST, Hash Table
  3. Graphs - BFS, DFS, Prim's Algorithm, Kruskal's Algorithm, Dijstra's Algorithm
  4. Strings - Radix Sort, Tries, KMP, Regex, Data Compression
  5. Advanced - B-Tree, Suffix Array, Maxflow
Common Questions
  • Binary Search(iteratively, recursively)
  • Randomized QuickSort(partition subroutine)
  • MergeSort
  • BFS in graph
  • DFS in graph(augment to detect cycles)
  • Tree Traversal (Pre, inorder, Past)
  • Topological Sort (Tarjan's Algorithm)
  • Dijstra's Algorithm (without decrease-key)
  • Longest Common Subsequece (using dynamic programming with matrices)
  • Knapsack Problem (DP)
  • Amortized vs. Average, Worse Case
  • High Level Assembly
  • BFS, DFS through a matrix
  • HeapSort (but don't bother coding it, O(1) but slow to cache efficiency)
  • Quick Select and median-of-medians
  • Bit Manipulations
  • Signed Integer
  • Cache, Cache inefficiencies, Cache Miss
  • Reading from register: lightning-fast, various cache: pretty fast, memory: slow, hard disk: abysmally slow
  • Implement a LRU Cache, write and worst case O(1) time (Common interview problem)
  • DNS Lookup, request-response cycle, HTTP Verbs
  • How cookies work
  • Standard ways to speed up a slow website (adding database indices to optimize common queries, better caching, loading front-end assets from a CDN, cleaning zombie listeners, pretty rabbit holey)

Spring 2017 CSc 22000 Professor Ahmet Yuksel (CCNY)

  1. Introduction to Algorithms
  • Insertion Sort, Correctness of Insertion Sort
  • (HW 1: Correctness of Insertion Sort)
  1. Evaluating Functions using limits with Big(O), omega, theta
  • (HW 2: Evaluating Functions using limits with Big(O), omega, theta)
  1. Merge Sort
  • Short intro to Recursion, and Recursion trees
  1. Ways of Solving Recurrences:
  • Masters Theorem
  • Recursion Trees
  1. Homogeneous and Inhomogeneous Recurrence Relations
  2. Heap Sort (Max Heap)
  • First Programming Assignment
  1. Priority Queues, and Matrix Multiplication
  2. Strasser's Algorithm, and Matrix Multiplication
  • Binary Search
  1. Binary Search
  • Quick Sort
  1. Decision Tree for Comparison Algorithm (with the use of Sterling's Approximation)
  • Counting Sort Algorithm and Runtime
  1. Recall on Counting Sort --> stable, not an in-place algorithm
  • Radix Sort
  • Inorder, preOrder, postOrder Tree Traversals
  • BST Search
  1. BST (getMin, getMax, successor, predecessor
  • Red-Black Trees .......................................................................................

Programming Assignments (Coming Soon)

  1. Runtime Comparison
  2. Knapsack Problem (Dynamic Programming)