CSCI 2200 - Foundations of Computer Science

CSCI 2200: Foundations of Computer Science (FoCS)

Spring 2013

Announcements

HW 1 has been posted. It is due on Thursday, February 7, by 5pm.

TA office hours have been posted.

Important announcement for students who *have completed* Math 2800 but *have not completed* CSCI 2400: you are allowed to opt-out from this course and take PHIL-2140, PHIL-4140, PHIL-4420, or any course in MATH and MATP at the 2000 level or above (except MATH 2800). The substitute course MUST BE taken in Spring 2013 (this semester). If you want to pursue this option read these instructions carefully: as described in the instructions, you will need to send an email to opt-out from FoCS.The deadline to opt-out is February 1st, 2013.

General Course Information

Time and location: Monday and Thursday, 10:00-11:40, at Eaton 214.
Prof: Petros Drineas, Lally Hall 317, ext. 8265, drinep at cs dot rpi dot edu. Office Hours: Mon 12:00-13:30.

TA: Chander Iyer, iyerc at rpi dot edu. Office Hours: Tue 15:00-16:30 at AE 125 and Wed 14:00-15:00 at AE 125.

TA: Yi Qian, qiany3 at rpi dot edu. Office Hours: Wed 12:00-13:30 at AE 217 and Thu 12:00-13:00 at AE 217.

TA: Lily Briggs, briggl at rpi dot edu. Office Hours: Wed 11:00-12:00 at AE 217 and Thu 13:00-14:30 at AE 217.

Advising and Learning Assistance Center's Tutors: click here to check for hours and locations. This resource is not managed by the instructor, so if you have any questions contact Rensselaer's Advising and Learning Assistance Center directly.

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.

[[POSTED, DUE 2/7 by 5pm]] Homework 1, due by 5pm on 2/7. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 2, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 3, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 4, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 5, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 6, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 7, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 8, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 9, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.
[[NOT AVAILABLE YET]] Homework 10, due by 5pm on X/XX. Grader: TA XXX. Grades posted on XX/XX, pick up your homework from Lally 317.

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 (this date is the current estimate and might change).
Final (during final exams week): date, time, and location to be announced.