Computational Methods II

Identifier
COMS 5040X
Professor(s)

Last Updated: Spring 2025

  1. Credits and contact hours: 3 credits, 3 contact hours
  2. Textbook, title, author, and year: None
  3. Other supplemental materials: None

Specific course information

  1. Brief description of the content of the course: Basics of graph theory, number theory and discrete probability. Big O Notation and algorithm analysis. Analysis of sorting and searching algorithms. Algorithm design techniques such as divide and conquer, greedy method and dynamic programming. Graph algorithms.
  2. Prerequisites or co-requisites: graduate standing or permission of the instructor

Brief list of topics to be covered

  • Logic and proofs
    • Basics of functions, relations, sets
    • Propositional and predicate logic: syntax and semantics
    • Proof strategies for program / algorithm correctness
      • Invariants and induction, recursion and structural induction
    • Counting and analyzing runtime of programs
  • Probability basics and hashing
  • Algorithms
    • Runtime Analysis, big-O notation
    • Data structures, Heap
    • Graphs and graph exploration
    • Algorithm strategies
      • Greedy algorithms
      • Divide and conquer
      • Dynamic programming
    • NP and Computational Intractability