Fall 2008
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.
mihail@cc.gatech.edu
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)
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
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.
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.