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.