CS 1050 A - Constructing Proofs

Fall 2008

[ Lectures] [Homework]


Basic primitives and paradigms of rigorous (formal, mathematical) methods essential in all aspects of computer science.
Tentative list of topics:
Elements of Logic, in particular as they apply to Computer Science.
Fundamental Proof Techniques (Direct proofs and Reductions, Invariants, Proofs by Contradiction, Exhaustive Case Analysis, Existential/Non-Constructive Proofs) with many examples arising in Computer Science.
Induction and Recursion, with emphasis on the Design and Analysis of Data Structures and Algorithms.
Functions and Order of Growth, with emphasis on their relevance in Quantifying Computational Resources (such as time, space and communication).
Elements of Probability and Statistics, with emphasis on very efficient estimation and prediction, especially over massive data sets.
Paradigms from Graph Theory and their applications in fundamental Modeling and Problem Solving.
Elements of Formal Models in Computation: Grammars as building blocks of Programming Languages (and Recursion revisited). The notion of Universal Computational Models (e.g. Turing machines). The Limits of Computability exposed by Diagonalization and analogies with Countable versus Uncountable Sets.
Basics of Number Theory related to Arithmetic over Large Integers and Modern Cryprography.


Tue-Thu 1:30-3:00, KACB (Klaus) 1443.
The material covered in each lecture together with references and/or notes will be posted in the Lectures web page, within reasonable time, and certainly before the homework referring to a particular lecture is due. It is very important to understand that lecture notes are outlines and not substitutes for attending the class or for assigned reading material. from the lecture.


Milena Mihail, Associate Professor
Office hours: Wed 9-11 and 1-2, Klaus 2138, or by appointment.
All email concerning this course should have a subject entitled CS1050.
Your professor welcomes technical and administrative questions and concerns,
and particularly invites your comments (positive and negative) about the class,
including new ideas, suggestions, pointers to related materials (such as readings, web sites, etc),
topics that interest you and you want to explore further (topics that you see no point why you should bother...), and so on.
Office phone: 404-385-0617 (unreliable answering machine)
Cell Phone: 404 379-1460 (quickest and most reliable communication, but use only if necessary)

Teaching Assistants

Ashish Sangwan, email: ashish.sangwan@gmail.com and sangwan@cc.gatech.edu,
Office Hours: Tue 3-5 in the Theory Lab(s) Klaus 2116 and/ot 2124.
Phillip Wright, email pwright@gatech.edu,
Office Hours: Wed 11:30-1:55 in commons area oustide Klaus 2138 (this is 1:55 sharp, Phillip has Class at 2:00)
Ivan Antonov, email: antonov.ivan@gatech.edu,
Office Hours: Mon 11:30-2:00 in commons area oustide Klaus 2138
in the College of Computing Commons Area


Discrete Mathematics and its Applications, by Kenneth Rosen, 6th Edition.
Available at the Engineering Bookstore and everywhere over the internet (probably cheaper).


Weekly or biweekly homeworks, posted in the Announcement Section below and in the Homework web page (we shall drop the lowest 2 grades): 33.33%.
You may collaborate or read any resource you want in solving the problems, but please indicate your collaboration group and/or the resources you used. You MUST write your answers by yourselves, without any collaboration and without using any resource, as if you are taking a test.
Academic conduct is subject to the Georgia Tech Honor Code.
Complete solutions will be always posted on Homework web page shortly after the deadline.
Late homework policy: no credit for late homeworks.
Finally, please be respectful to your professor and your TAs by using your best handwriting when writing up your solutions (or otherwise type them up). We cannot guarantee that we will read and grade illegible or very tiny handwritings.

Three to Four quizes: 33.33%.
First quiz is Tuesday September 23.
Final: 33.33%.
Academic conduct is subject to the Georgia Tech Honor Code

Web Announcements

You are responsible for reading these announcements at the end of the day every Tuesday and Thursday.

Tue Aug 19: Homework 0 is now posted and due this coming Thu Aug 21. The purpose of this homework is to get to know a little bit about you, and to get a rough feeling of your current mathematical background. This Homework 0 is mandatory, but your grade will be either 100 (if you put a descent effort in either answering the questions, or explaining what background you think you are missing in the case where you cannot answer a particular question or questions), or zero (if you do not hand in the homework, or if you clearly put no time or effort). Only for this particular homework, please asnwer it without collaborating with others, and use as few external references or other resources as possible. In any case, if you use external references or other resources, please do list them. Try to complete the entire homework in no more than 2 hours. In any case, please write how long it took you to complete the homework.

Thu Sept 4: Homework 1 is now posted and due Thu Sept 11. Instructor is holding extra office hours Mon Sept 8, 11-1, for questions concerning Homework 1. Lecture outlines and readings and now posted in the Lectures web page.

Thu Sept 11: Homework 2 will be posted by the end of the day today, and will be due Thu Sept 18. Lecture Outlines and Solutions to Homework 1 will be posted by noon tomorrow Fri Sept 12. Make sure you read these announcements again tonight and tomorrow afternoon.

Thu Sept 11: NON-TECHNICAL ANNOUNCEMENT: A student note taker is needed in this course to take notes for a student with a disability. The note taker will be paid a stipend for this assignment. Skills needed are the ability to take accurate, legible, and organized notes and a commitment to attend every lecture. If interested, please contact Kashif Awan or Tina Allen via office phone at 404-894-2563 or via email at notetaker@vpss.gatech.edu as soon as possible. Be sure to indicate the Professor's name, time, day and course number in the subject line of the announcement.

Fri Sept 12, 3pm: Homework 2 is now posted and due Thu Sept 18.

Thu Sept 18: How to study for Quiz 1:

From Rosen Book:
Logic: Tables 1,3,4 pp 22-23
Intro Proofs (direct, contrapositive, contradiction): pp 75-78 everything, pp 80-81 everything after Proofs by Contradiction pp 89, example 6

From Outline Lecture Notes:
Lecture Outline (II), pp 1-11
Lecture Outline (III), everything
Lecture Outline (IV) and (V), everything
Lecture Outline (VI) and (VII), everything

Homework 1 Probelms 5,6,7,8,10.
Homework 2 Problems 1,3,4,5,6.
Practice Quiz 1 , everything.

Thu Sept 26: Homeworks 1 and 2 are graded. Quiz 1 will be graded by Friday Sept 26. You may come and look at your work Fri Sept 26, 10am-2pm in Klaus KACB 2138. (We are also trying to figure out how to post your grades on T-Square). Good news: 80-90% of the class is doing fine! If you you do not belong to that 80-90%, you will get email from your instructor.

Thu Oct 2: Homework 3 is now posted and due Thu Oct 9.

Thu Oct 16: Quiz 2 is rescheduled for Tue Oct 28. It will cover basic proof techniques, recursion and induction. In terms of lectures, this is material covered from Tue Sept 2, up to Thu Oct 16. In terms of homeworks, Quiz 2 will cover material in Homeworks 2,3 and 4, Quiz 1, and Practice Quizes 1 and 2. Practice Quiz 2 will be posted Tue Oct 21). Homework 4 is now posted and due Thu Oct 23. Make sure you are up to date with your reading and homeworks!

Tue Oct 21: Thu Oct 25 will be general review for Quiz 2. Quiz 2 is Tue Oct 28. It will cover basic proof techniques, recursion and induction. In terms of lectures, this is material covered from Tue Sept 2, up to Thu Oct 16. In terms of homeworks, Quiz 2 will cover material in Homeworks 2,3 and 4, Quiz 1, and Practice Quizes 1 and 2. Practice Quiz 2 will be posted Tue Oct 21). Homework 4 is due Thu Oct 23. Make sure you are up to date with your reading and homeworks!

Thu Oct 23: Quiz 2 is Tue Oct 28. Make sure you have gone through the materials of Homeworks 2 through 4, Practice Quiz 1 and Quiz 1, and ESPECIALLY Practice Quiz 2.


Thu Oct 30: Homework 5 is now posted and due Nov 6. Solutions to Quiz 2 are also posted. Reading and understanding solutions to Quiz 2, Practice Quiz 2, and Homework 4 are a good review, and will help you solve Homework 5 quite fast.

Tue Nov 11: Grades to Quiz 1 are now posted on T-Square. Grades to Quiz 2 are still processed, but they look very similar to Quiz 1 (we are normalizing). For Quiz 1: If you are above 90, you are fine! If you are in the 75-90 range, you are definitely passing, most likely with a B, but you are welcome to see me. If you are below 70, definitely make an appointment to see me.

Tue Nov 11: I will be posting lecture notes for order of growth, means, averages, and making intelligent inferences concerning large datasets very shortly. I will also post a large number of examples and HW 6. Homework 6 will be due Thu Nov 21.


Thu Nov 13: Grades to Quiz 1 AND Quiz 2 are now posted on T-Square. Please check your grades for BOTH quizes. Some grades of Quiz 1 have been updated (higher).

Thu Nov 13: You may come and take your Quiz 1 & Quiz 2 graded, so that you see where you went wrong, or how you did. YOU HAVE TO HAND IT BACK IN CLASS ON THU NOV 20, IF YOU WANT YOUR GRADES IN THESE QUIZES TO COUNT.

Thu Nov 13: We will discuss in class how to help people who are consistently below the average, but feel they can actually do better. If you were not present in class today, make sure you read these announcements.

Mon Nov 17: For those who did not do well in Quiz 2, there will be a 40 min mini makeup Quiz 2 on Thu Nov 20. The material will be INDIRECT PROOFS and SIMPLE INDUCTION. Use Practice Quiz 2, and Quiz 2 as study guides. We will do this the first 40 mins of the lecture.

Mon Nov 17: For those who do not take the 40 min mini makeup Quiz 2, I will bring a collection of (fun I hope) puzzles to work on.

Mon Nov 17: Homework 6 is now posted and due Nov 25.

Tue Nov 25: Quiz 3 is Tue Dec 2. Study guide: read Practice Quiz 2, Quiz 2 (with solutions), and solutions to HW 4, 5 and 6.

Thu Dec 4: Study Guide for Final (in the order that follows):
Quiz 3, Quiz 2, Practice Quiz 2, HW 6,5,4.
Quiz 1, Practice Quiz 1, Hw 3,2,1.

Thu Dec 4: The final exam is Friday Dec 12, 11:30-2:20, in the same classroom.

Thu Dec 4: In the final, you are allowed 3 single-sided pages with notes. Any notes you want is fine.

Class Web-site http://www.cc.gatech.edu/~mihail/index1050.html.

This site is maintained by Milena Mihail, please report problems to mihail@cc.gatech.edu.