Foundations of Computer Science

CMPU 145 Section 01 (Fall 2020)

· Instructor: Tom Ellman (thellman@vassar.edu)

· Classes: Tuesdays and Thursdays, 12pm - 1:15pm

· Labs: Fridays 11am - 1pm

· Office Hours: Tu, Th 1:30pm - 2:45pm; Wed 1pm - 2:30pm

· Class, Lab and Office Hours Zoom

· Class Moodle Page

Overview

This course introduces the theoretical, structural, and algorithmic foundations of computer science. Topics include: sets, relations, functions, recursive data structures, recursive functions, induction, structural induction, probability, logic, and Boolean algebra. The course will emphasize the exploration of these topics through programming exercises, but it will also focus on developing proof techniques in written exercises. A weekly laboratory period provides guided hands-on experience.

Prerequisites

CMPU 101: Problem-solving and Abstraction

Although this course covers the mathematical theory behind computer science, the only math you need as a prerequisite is high-school algebra. Everything else will be introduced as we go.

Course Goals

By the end of the semester, you should understand:

· how to model computational problems using discrete structures

· how to prove a claim rigorously

· the intimate connection of mathematical theory and computing practice.

This course provides essential background for 200-level computer science courses. It forms the immediate basis for the exploration of the limits of computation in CMPU240 (Language Theory and Automata), which you should (ideally) take next semester.

This syllabus is a plan, not a contract. I want us to work together to find the best way for you to learn. If you have questions or concerns about the course, talk to me. My email address is thellman@vassar.edu. My office hours will are listed on our class website and my Vassar web page.

Calendar

The calendar with lecture notes, assigned readings and exercises, and exams is on our course Moodle page, and will be updated throughout the semester. Student coaches will be available during scheduled labs and at other peak hours of laboratory use, such as evenings and weekends. The coaching schedule will available on our class Moodle page.

Readings

Our textbook is: Sets, Logic and Maths for Computing, second edition David Makinson. The textbook is available for free online. A link to the textbook is on our class Moodle page. Our readings will also include handouts that will be made available as we go along. A schedule of assigned reading in the textbook and handouts is on our class Moodle page.

Lectures

My lectures will be recorded asynchronously and stored on our class Moodle page. You should view and hear each lecture prior to the corresponding meeting. I will not normally be giving lectures during our class meetings.

Class Sessions

The class sessions are intended to augment and support the material readings and recorded lectures. Our meetings will provide opportunity for in-depth discussion of topics, working through examples, and the chance for you to ask questions. The material covered each week builds on what was covered in prior weeks. As such, it is essential that you attend every class meeting and keep up with the reading assignments.

Computing Environment

We will use Racket (The Language Formerly Known as Scheme) in the DrRacket programming environment. DrRacket is installed on the Linux workstations in our classroom and labs. It can also be downloaded from racketlang.org if you want to install it on your own computer. Programs written in DrRacket have the same behavior on all platforms (e.g., Linux, macOS, Windows). Therefore you do not need to worry what kind of machine you use when you run DrRacket programs. Depending on which professor you had for CMPU101, you you learned to program in one of several dialects of Racket or Scheme. In this course we will use the full Racket language. The website for the Racket language provides a Racket Guide and a Racket Cheat Sheet, which you may consult for more details.

Course Work

To develop and assess your understanding of the topics presented in this course, there will be weekly labs, regular homework assignments, two midterm exams, and a final exam (during the final exam period).

Labs

The purpose of the labs is to give you hands-on programming experience using the concepts from the readings and lectures. Lab sessions are two hours long. Different people work at different speeds. Sometimes people finish the lab before the two hours are up. When that happens, you can leave after getting a coach to check off your work. Sometimes people cannot finish the lab in the allotted time. When that happens, you may continue working on the lab after the session is over, and go to coaching hours so a coach can check off your completed work. In any case, when you complete a lab and a coach has checked off your work, you should: (1) Make a single Zip archive of your work and (2) submit the archive to the drop box on our Moodle page that is associated with the lab. Lab work is not accepted after the beginning of the class immediately following the lab session – because solutions will be posted on Moodle at that time. Please submit whatever work you have done by the deadline, so I can give partial credit.

Assignments

Assignments are similar to labs, but you are expected to do the work on your own time. We will usually have one assignment each week. Some of the problems on these assignments will require you to write, test and run programs. Others will require you to write proofs using techniques discussed in class. Details will be provided with the assignments. Each assignment will indicate the due date and a late date. Late work gets a 10% grade penalty; however, work submitted after the late date will receive no credit. Completed assignments should Zipped and submitted to the appropriate Moodle drop box, just as with labs. Incomplete work can be submitted for partial credit.

Exams

Our course will have two take-home mid-term exams. These exams will be open-book and open-notes. They must be carried out during a time period specified in the exam document. At the end of the time period, you should Zip your work and submit it to the appropriate Moodle drop box.

Grading Policy

Assignments	35%
Labs	15%
Exam 1	15%
Exam 2	15%
Final Exam	20%

Academic Integrity

All assignments must be done individually; collaboration is not allowed unless it has been explicitly authorized. Receiving and copying solutions (code, pseudocode, proofs, etc.) from any source (a classmate, a friend, a published text, an online source, etc.) is disallowed. Note that using code or other material from sources (other than those explicitly given as course resources) as “inspiration” and submitting highly derivative solutions is viewed as copying. Please read “Going to the Source”, available from the Dean of the College website. Note that the guidelines that apply to writing in general apply equally to the writing of computer programs. Copying someone else’s code without attribution is plagiarism. Give proper attribution for the help you receive. Quoting from Chapter X, “In suspected cases of plagiarism, the instructor prepares a written statement of complaint to the Academic Panel.” Please don’t put yourself or your professor in that position. When in doubt, stop and ask me first.

Title IX

Vassar College is committed to providing a safe learning environment for all students that is free of all forms of discrimination and sexual harassment, including sexual assault, relationship abuse, and stalking. If you (or someone you know) has experienced or experiences any of these incidents, know that you are not alone. Vassar College has staff members trained to support you in navigating campus life, accessing health and counseling services, providing academic and housing accommodations, helping with legal protective orders, and more. Please be aware all Vassar faculty members are “responsible employees,” which means that if you tell me about a situation involving sexual harassment, sexual assault, relationship abuse, or stalking, I must share that information with the Title IX Coordinator. Although I have to make that notification, the Title IX office will only provide outreach by email. You will control how your case will be handled – you don’t have to read or respond to the email, and it is completely up to you whether to pursue a formal complaint. Our goal is to make sure you are aware of the range of options available to you and have access to the resources you need.

If you wish to speak to someone privately, you can contact any of the following on-campus resources:

• Counseling Service (counselingservice.vassar.edu, 845-437-5700)

• Health Service (healthservice.vassar.edu, 845-437-5800)

• Nicole Wong, SAVP (Sexual Assault and Violence Prevention) director (savp.vassar.edu, 845-437-7863)

• SART (Sexual Assault Response Team) advocate, available 24/7 by calling the CRC at 845-437-7333 and asking for SART

The SAVP website (savp.vassar.edu) and the Title IX section of the EOAA website (eoaa.vassar.edu/title-ix) have more information, as well as links to both on- and off-campus resources.

Acknowledgements

This course is based in large part on work by other professors, including Luke Hunsberger, Eric Aaron, Jonathan Gordon, Jan Gullberg, David Makinson, Keith Schwarz and Allison Randal.