Identifier
COMS 5040X
Professor(s)
Last Updated: Spring 2025
- Credits and contact hours: 3 credits, 3 contact hours
- Textbook, title, author, and year: None
- Other supplemental materials: None
Specific course information
- 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.
- 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