CS 1050 B -- Proofs, Fall 2004

Description

Basic primitives and paradigms of the mathematical understanding of computation.
Tentative list of topics:
Propositions, Proofs, Propositional logic
Basics proof techniques
Induction and recursion
Modular arithmetic
Big O notation
Relations
Basic counting and probability
Diagonalization and uncomputability
Number theory: Euclid's algorithms, primality, RSA

Lectures

Tu, Th 9:35-10:55, ES&T L 1175.

Instructor

Dana Randall, Associate Professor
Office phone: 404-894-3156
Office hours: Wednesday 12-1, Thursday 4:30-5:30, College of Computing 239.
randall@cc.gatech.edu

Teaching Assistant

Rishi Saket
saket@cc.gatech.edu
Office hours: Wednesday 11-12
Help session: Tuesday 11-12 in room CCB 102
Location: the commons area

Text and Notes

• Discrete Mathematics and its Applications, by Kenneth Rosen.
• Supplementary resource: Lecture notes from a similar class at Berkeley.
  

Grading

Weekly homeworks. You may collaborate or read any resource you want to aid in solving these problems, but please indicate your colalboration group and/or the resources you use. You MUST WRITE the solutions by YOURSELF, without any collaboration and without copying from any of the resources, as if you are taking a test.

Academic conduct is subject to the Georgia Tech Honor Code.

Complete solutions will be posted on the web shortly after the deadline.

Late homeworks will not be accepted.

Important dates

Midterms: (Tell me NOW if there is an expected conflict!!!!)
• Sept 14
• Oct 26 (**** note new date !!!!! *****)

Homeworks

• Homework 1 (due Aug 26): ps, pdf
  Solution to Hw 1 (This was corrected 9/1/04.)
• Homework 2 (due Sept 2): ps, pdf
  Solution to Hw 2
• Homework 3 (due Sept 9): ps, pdf
  Solution to Hw 3
• Homeworks 4 and 5 (due Sept 30): ps, pdf (***This is a long one, so start early!!****)
  *** CORRECTIONS!!!! In problem 7, n is an integer. Please skip problem 8c since we haven't defined the symbol yet. (Sorry about these.-dr)
  Solution to Hws 4 and 5
• Homework 6 (due Oct 7): ps, pdf
  Solution to Hw 6
• Homework 7 (due Oct 14): ps, pdf
  Solution to Hw 7
• Homework 8 (due Oct 21): ps, pdf
  Solution to Hw 8
• Homework 9 (due Nov 4): ps, pdf
  Solution to Hw 9
• Homework 10 (due Nov 11): ps, pdf
  Solution to Hw 10
• Homework 11 (due Nov 18): ps, pdf
  Solution to Hw 11
• Homework 12 (due Tuesday Nov 30): ps, pdf
  Solution to Hw 12

Exams and solutions

• Practice Midterm 1
  Solution to Practice Midterm 1
  
• Solution to the Real Midterm 1
  
  
• Practice Midterm 2
  Solution to Practice Midterm 2
  
• Solution to the Real Midterm 2
  
  

**************************************************************
Remember the review for the final is Tuesday Dec 7 at 5:45 in CCB 101 !!!!
**************************************************************