Academics
  /  
Courses
  /  
Descriptions
COMP_SCI 212: Mathematical Foundations of CS Part 1: Discrete mathematics for computer science


VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

CS 150 or GEN_ENG 150-0 or GEN_ENG 151-0

Description

This course will discuss fundamental concepts and tools in discrete mathematics with emphasis on their applications to computer science. Example topics include logic and Boolean circuits; sets, functions, relations, databases, and finite automata; deterministic algorithms and randomized algorithms; analysis techniques based on counting methods and recurrence equations; trees and more general graphs.

  • This course is a required Core course in the CS curriculum in McCormick and Weinberg

RECOMMENDED TEXTS:

COURSE INSTRUCTORS: Prof. Aravindan Vijayaraghavan or Prof. Miklos Racz or Anjali Agarwal

COURSE COORDINATOR: Prof. Aravindan Vijayaraghavan

COURSE OBJECTIVES: In this course, students should develop mathematical thinking and problem-solving skills associated with writing proofs.  Students should also be exposed to a wide variety of mathematical concepts that are used in the Computer Science discipline, which may include concepts drawn from the areas of Number Theory, Graph Theory, Combinatorics, and Probability.

DETAILED COURSE TOPICS: All sections will deal with topics from Part I (Proofs and Mathematical Preliminaries), as well as a selection of topics from Parts II-IV.

Part I:  Proofs, and Mathematical Preliminaries 

  1. Introduction to Logic, Proofs.
  2. Principle of Mathematical Induction, Strong Induction.

Part II: Counting, Combinatorics, Probability

  1. Counting, Mapping, Functions, Bijection, Inclusion-Exclusion formula.
  2. Pigeonhole principle, Generalized Pigeonhole.
  3. Permutations and Combinations. Picking with repetition, without repetition.
  4. Binomial formula, Pascal Triangle, Generating functions.
  5. Introduction to Probability: Random Events, Conditional Probabilities, Independence, Bayes Rule.
  6. Expectation, Linearity of Expectation, Variance of random variables.
  7. Markov's inequality. Chebychev inequality, Union bound.
  8. Sums of random variables, Concentration of measure, Statistical significance.

Part III: Graph Theory

  1. Introduction to graphs, Properties of graphs.
  2. Connectivity, Connected components, Distances.
  3. Trees, Cycles,  Spanning Trees. 
  4. Planarity, Graph Coloring, Bipartite graphs.
  5. Matchings, Hall's theorem, Stable marriage.
  6. Linear Algebra: Adjacency matrix, Edge-vertex matrix. Relating graph properties. Eigenvalues, Eigenvectors.
  7. Independent set, Vertex cover, Network Flows, Cuts.
  8. Linear Programming, Duality.

Part IV: Number Theory & Miscellaneous

  1. Prime numbers, Divisibility, GCD algorithm.
  2. Modular arithmetic. Prime numbers. Fundamental theorem of arithmetic.
  3. Cryptography, Computational Complexity.
  4. Turing Machines, Reductions, NP-hardness. 

HOMEWORK ASSIGNMENTS: Varies by instructor

LABORATORY PROJECTS: None

GRADES: Varies by instructor