Academics

  /  

Courses

  /  

Descriptions

COMP_SCI 296: Mathematical Foundations of Computer Science I - Honors

VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

COMP_SCI 110 or COMP_SCI 111

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 substitute for CS 212, which is required Core course in the CS curriculum in McCormick and Weinberg. You can use this course instead of CS 212 for the core requirement, and to satisfy any pre-requisites that CS 212 satisfies.

RECOMMENDED TEXTS:

• Fall & Winter Section: Mathematics for Computer Science by Lehman, Leighton, and Meyer (e-book: https://courses.csail.mit.edu/6.042/spring18/mcs.pdf)

COURSE INSTRUCTORS: Prof. Aravindan Vijayaraghavan 

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.

PREREQUISITES: - COMP_SCI 110 or COMP_SCI 111

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