COURSE INFORMATION

Description.   The course will cover a variety of mathematical tools and techniques most useful in thinking about algorithms and computation.

Topics.   Following is a tentative list of topics to be covered:

• Induction, counting, asymptotic analysis.

• Elements of graph theory, graph coloring, matching, Hall's theorem.

• Stable matching, mechanism design.

• Linear programming and basic applications.

• Probability, expectation, concentration inequalities.

• Applied probabilistic analysis, sampling algorithms, streaming algorithms.

• Online algorithms.

• Elements of cryptography: RSA, zero-knowledge proofs.

• Elements of computability and computational complexity: undecidability, NP-completeness.

Prerequisites.   COS 126 and 226 (or sufficient mathematical background), and MAT 175, 202, 204 (or permission of instructor). COS 226 can be taken along with COS 340 in the same term. If you have any questions about prerequisites, please contact the professor.

Lectures.   Monday and Wednesday 3:00pm–4:20pm in CS 105. Attendance is strongly recommended. All required readings and lecture notes will be posted on Blackboard. Following is a list of readings for every lecture.

Date	Topic	Notes	Self reading	Open problems	TrueShelf topics	TrueShelf tags
Sep 11 2013	Introduction	none	none	none
Sep 16 2013	Mathematical Induction	Chapters 2,3 from LL.pdf	Section 3.2 from LL.pdf	none	DISCRETE MATHEMATICS	#induction
Sep 18 2013	Counting	Chapter 14 from LL.pdf	none	none	COMBINATORICS	#counting #pigeonhole-principle
Sep 23 2013	Counting (contd.)	Chapters 15,16 from LL.pdf	Sections 15.2, 16.3, 16.4 from LL.pdf	Sets with distinct subset sums	COMBINATORICS	#n-choose-k #binomial-theorem
Sep 25 2013	Graph Theory	Chapter 6 from LL.pdf	---	---	GRAPH THEORY	#cycle #graph-complement #bipartite-graph
Sep 30 2013	Graph Theory (contd.)	Chapter 6 from LL.pdf	Section 6.3 from LL.pdf	Prove graceful tree conjecture for trees with diameter 6.	GRAPH THEORY	#trees #graph-labeling #graph-isomorphism
Oct 2 2013	Graph Theory (contd.)	Chapter 7 from LL.pdf and more notes coming soon.	---	---	GRAPH THEORY	#eulers-formula #eulerian-graph #graph-coloring #tournament #planar-graphs
Oct 7 2013	Graph Theory (contd.)	---	---	---	GRAPH THEORY	#matching

Precepts.   Attendance is strongly recommended. A preceptor will work through problems that are similar in spirit to those on the problem sets. Every friday evening we will post precept problems on Blackboard.

Office hours.   You are welcome to attend the office hours of any staff member.

Undergraduate course assistants.   James Bedell.

Online forum.   If you have general questions about the problem sets, lectures, textbook, or other course materials, please post via Piazza. Posts marked private are viewable only by the course staff.

Course website.   The course website is at http://www.cs.princeton.edu/courses/archive/fall13/cos340/.

Homeworks.   Homeworks and solutions will be posted on Blackboard. See infosheet.pdf for more details about collaboration policy.

Grading.  

• Homework assignments: weekly problem sets -- 40%;

• 2 take-home midterms -- 30%;

• a take-home 24-hour final exam -- 30%.

Regrading.   To request a regrade, you can stop by during office hours to discuss your solutions and grading concerns.