CSCI 2200: Foundations of Computer Science (FoCS)

Spring 2013



Announcements

HW 8 will be posted on April 10.

The class on Monday, April 8, will focus on solving problems on counting and discrete probability. Nivas Nambirajan and Abhisek Kundu will solve problems from HWs 6 and 7, as well as additional problems.


General Course Information PLEASE NOTE: The instructor will hold office hours in his office at Lally 317. The TAs will hold office hours at the rooms noted above.

Textbooks: The main textbook for this course is "Discrete Mathematics and its Applications," by Kenneth H. Rosen (McGraw Hill, 7th edition). The first 16 lectures of the course will be based on chapters 1, 2, 3, 5, 6, and 7 of K. Rosen's book (we will not cover all the material in the aforementioned chapters). A second textbook is also recommended: "Introduction to the Theory of Computation", by Michael Sipser (PWS Publishing Company). The last eight lectures of the course will be based on M. Sipser's book. Both books should be available at the RPI bookstore. Please note that the slides are the primary source of study material for this course. We will not cover all the material in the above books and we will cover some topics that are not covered in either book.

Grading: Homeworks 30%, Midterm 30%, Final 40%. There will be ten homeworks. The midterm will be in class and the final will be during the final exams week. Students whose course average is above 90% will get an A in this course, students whose course average is between 80% and 90% will get a B in this course, students whose course average is between 70% and 80% will get a C in this course, and students whose course average is between 60% and 70% will get a D in this course. The instructor might lower these bounds depending on the final curve of the grades in the course.

Description: The course will have two parts. The first part (approximately 16 lectures) will cover discrete mathematics. More specifically, the first part of the course will cover logic, including propositional logic, predicate logic, and quantifiers; proofs in predicate and propositional logic; sets, functions, sequences, and sums; induction and recursion; counting arguments, including permutations and combinations; and an introduction to discrete probability. The second part (approximately eight lectures) will be an introduction to models of computation. More specifically, the second part of the course will cover finite automata (deterministic and non-deterministic) and regular languages; context free languages and grammars; Turing machines; and, decidability and an introduction to complexity theory.

Learning outcomes: At the end of the course, the student (i) is able to formulate mathematical proofs using logic, (ii) is able to apply mathematical tools such as induction and resursion, (iii) can recall key definitions from set theory, (iv) is able to formulate combinatorial arguments, (v) is able to distinguish between various computational models, (vi) is able to think critically on the difficulties of key questions in foundations of computer science, and (vii) can recall key facts regarding finite automata and Turing machines.


Lectures
(Slides for lectures 1 through 16 are heavily based on material prepared by K. H. Rosen for the course textbook.)
  • Logic (Lectures 1, 2, and 3)[.pptx]
  • Proofs (Lectures 4 and 5)[.pptx]
  • Sets, Functions, Sequences, and Sums (Lectures 6, 7, and 8)[.pptx]
  • Induction and Recursion (Lectures 9, 10, and 11)[.pptx]
  • Counting (Lectures 12, 13, and 14)[.pptx]
  • Discrete Probability (Lectures 15 and 16)[.pptx]
  • Models of Computation: Languages and (deterministic and non-deterministic) Finite Automata (Lectures 17 and 18)[.ppt]
  • Context-Free Grammars (Lecture 19)[.ppt]
  • Turing Machines (Lectures 20 and 21)[.ppt]
  • Decidability (Lectures 22 and 23)[.ppt]
  • P vs. NP and NP-Completeness (Lecture 24)[.ppt]
Homeworks

Homeworks should be written by individuals alone. If anyone is caught cheating, then severe measures will be taken, depending on the gravity of the offense. Such measures include significant lowering of the final grade and reporting the event to the appropriate authorities in the campus.

Read this paragraph carefully!! No homework extensions will be granted under any circumstances, unless approved by the Student Experience office (4th floor of Academy Hall, x8022, se at rpi dot edu). Homeworks are generally due on Thursday, by 5pm (sharp), in the box outside the instructor's office at Lally 317. You can check your grades online at LMS. Once the grades have been posted, you can pick up the assignment from folders outside the instructor's office at Lally 317. Any request to re-evaluate a grade must be made within one week of the return date of the homework in question; return dates will be posted. Solutions for the homeworks will be posted at LMS in the "HW Solutions" folder.
  • [[GRADES, SOLUTIONS POSTED 2/15]] Homework 1, due by 5pm on 2/7. Graders: Problems 1 and 2: Qian, Problems 3 and 4: Iyer, Problem 5: Briggs.
  • [[GRADES, SOLUTIONS POSTED 2/26]] Homework 2, due by 5pm on 2/14. Graders: Problems 1 and 2: Iyer, Problems 3 and 4: Qian, Problem 5: Briggs.
  • [[GRADES, SOLUTIONS POSTED 3/1]] Homework 3, due by 5pm on 2/21. Graders: Problems 1 and 2: Briggs, Problems 3 and 4: Iyer, Problem 5: Qian.
  • [[GRADES, SOLUTIONS POSTED 3/20]] Homework 4, due by 5pm on 2/28. Graders: Problems 1 and 2: Qian, Problems 3 and 4: Iyer, Problem 5: Briggs.
  • [[GRADES, SOLUTIONS POSTED 3/31]] Homework 5, due by 5pm on 3/21. Graders: Problems 1 and 2: Briggs, Problems 3 and 4: Qian, Problem 5: Iyer.
  • [GRADES, SOLUTIONS POSTED 4/2]] Homework 6, due by 5pm on 3/28. Grader: TA Iyer, all problems.
  • [[TAs ARE GRADING]] Homework 7, due by 5pm on 4/4. Graders: Problems 1 and 3: Briggs, Problems 2 and 4: Qian.
  • [[NOT AVAILABLE YET]] Homework 8, due by 5pm on X/XX. Grader: TA XXX.
  • [[NOT AVAILABLE YET]] Homework 9, due by 5pm on X/XX. Grader: TA XXX.
  • [[NOT AVAILABLE YET]] Homework 10, due by 5pm on X/XX. Grader: TA XXX.
Exams

There will be one short midterm after the first ten or eleven lectures and a final exam during final exams week. Exams are closed book, but you may bring one double-sided A4 page with notes in the exams.
  • Midterm: In class, Monday, March 4, 2013. Grades were posted on March 14; grades are out of 80 (NOT 100) and the average grade is 53. The midterms are available outside the instructor's office. If you want to discuss your grades talk to the appropriate TA: for problems 1, 2, and 9 talk to Qian, for problems 5, 6, and 8 talk to Iyer, and for problems 3, 4, and 7 talk to Briggs.
  • Final (during final exams week): Thursday, May 16, 2013 from 11:30 to 14:30.