Instructor Luke Hunsberger Lectures Mon/Wed @ 1:30 - 2:45 p.m., OLB 205 Labs Mon @ 3:10 - 4:25 p.m., OLB 105
The primary textbook for the course is: Sets, Logic and Maths
for Computing by David Makinson (c) 2012, published by
Springer-Verlag.
We will use the Scheme programming language and the DrScheme
software, available
at drscheme.org. (Pay no
attention to the pop-up window concerning DrRacket.)
The lab sessions will initially be devoted to getting familiar
with the DrScheme programming environment. (It is very similar to
DrRacket.) Some lab sessions may also include lectures.
There will be regular assignments, usually about one every two
weeks. Most of the problems on these assignments will require you
to write, test and run programs written in Scheme; however, some
of the problems, particularly in the first part of the semester,
will require you to write proofs using techniques discussed in
class. You are strongly encouraged to use PENCIL when writing
proofs! (It's a lot easier to erase than ink.) It is not
necessary to use a word processor for proofs; paper-and-pencil is
fine. Assignments involving computer programs will be submitted
both electronically and in paper form. Whether involving
handwritten proofs or typed-up programs, all assignments must be
clearly composed and laid out neatly on the page. Your programs
must include concise comments that make it clear what you are
doing; and your proofs must be legible. In general, at least
one blank line should separate consecutive problems/programs.
All assignments must be done individually. No
collaboration of any kind is allowed. Any cases of inappropriate
collaboration (cheating) have to be reported to the department
chair, and will be dealt with promptly. Any sharing of code---even
if it's just pointing out something on the screen that you've
written---will be considered cheating.
There will be one in-class exam during the semester, shortly
after Spring break. There will also be a final exam. All exams will
be paper-and-pencil affairs, with open-book/open-notes, but no
electronic devices (e.g., no calculators or computers), except
that we may provide you with access to an online browser that is
restricted to the cs145 website.
The elements of the course (exams, labs and assignments) will be
weighted as follows when determining your overall grade:
Academic accommodations are available for students with
disabilities who are registered with the Office of Disability and
Support Services. Please schedule an appointment with the
instructor early in the semester to discuss any accommodations for
this course which have been approved by the Director of Disability
and Support Services as indicated in your accommodation letter.
Overview
This course introduces a variety of fundamental concepts, tools,
algorithms and techniques that are used throughout the field of
Computer Science. Topics include: sets, relations, functions, proof
techniques, induction, structural induction, recursion, structural
recursion, proving program correctness, probability and logic. The
course will emphasize the exploration of these topics through computer
exercises; however, it will also focus on developing proof techniques
in handwritten exercises.
Nuts and Bolts
Labs 20% Assignments 45% Exams 35% (midterm: 15%, final: 20%) Calendar
Monday
Wednesday
Jan. 23
Introduction.
Scheme
summary.
Read sections 1.1-1.4 in
the textbook.
Jan. 28
Continuing with Chapter 1.
Lab 0 SOLUTIONS!!
Asmt. 0 SOLUTIONS!!
Jan. 30
Intersection and Union
Sample proof 1,
Sample proof 2.
Feb. 4
Power sets (Section 1.6) and Relations (Starting Chap. 2)
Lab 1 SOLUTIONS!!
Asmt. 1 SOLUTIONS!!
Feb. 6
Binary relations (as subsets of A × B).
Read: 2.1, 2.2.2, 2.3.1, 2.4.
Feb. 11
Reflexive, symmetric and transitive relations; equivalence relations
and partitions (Section 2.5).
Code from class
Lab 2 SOLUTIONS!!
Asmt. 2 SOLUTIONS!!
Feb. 13
GUEST LECTURE: Dimitri Wijesinghe -- Functions (Chapter 3: 3.1-3.4)
Feb. 18
GUEST LECTURE: Ben Stoutenburgh -- Command-Line Basics!
(If you attend another of Ben's Command-Line Basics lectures, you
don't have to attend this one.)
Lab 3 SOLUTIONS!!
Practice Problems
Feb. 20
Equivalence relations and partitions (Sec. 2.5
Proof from
class, plus a bit more.
Feb. 25
Further exploration of equivalence relations and partitions
Code from class
Lab 4 SOLUTIONS!!
Proof Techniques 1, Proof Techniques 2.
Feb. 27
Finishing up with functions; the number of elements in a set.
Asmt. 3 SOLUTIONS!!
March 4
Chapter 4: Induction, recursion and the natural numbers.
Numerical Recursion Handout.
Proof from class.
Lab 5 SOLUTIONS!!
March 6
Continuing with numerical induction.
Proof from class.
SPRING
BREAK!
March 25
Continuing with Induction/Recursion. From numbers to lists!
List-based Recursion/Induction
Lab 6 SOLUTIONS!!
Asmt. 4 SOLUTIONS.
March 27
Answers to Practice Problems; Alternative proof to
postage problem.
April 1
MIDTERM EXAM DURING LAB PERIOD in OLB 105!!
No Class Today
Exam will cover Chapters 1-3 and a little
bit of Chapter 4 (Numerical Induction/Recursion).
April 3
Order on Natural Numbers &
Strong Induction. Concluding Chapter 4 (thru section 4.5.2).
Starting Chapter 5: Counting.
April 8
Chapter 5: Counting! (Permutations & Combinations)
Code from class.
Lab 7 SOLUTIONS!!
April 10
Permutations and Combinations
April 15
Chapter 5: Combinations; Validating answers using simulation.
Lab 8: April 15, 2013
Code from class
Asmt. 5 SOLUTIONS!!
April 17
Continuing with Combinations: Bridge hands and Powerball Tickets!
April 22
Finishing up Chapter 5 (O-R+); Starting Probability in Chapter 6.
Lab9 SOLUTIONS!!.
Asmt. 6 SOLUTIONS!!
(Note: asmt6-helper.txt is now readable!)
April 24
Continuing with probability (Chapter 6).
April 29
Finishing up probability
CHAPTER 5 (5.1-5.4); CHAPTER 6 (6.1-6.4;6.6); CHAPTER 8 (8.1-8.3)
Lab 10 SOLUTIONS!!
May 1
Continuing with conditional probability;
starting propositional logic (Chapter 8).
Code from class
Asmt. 7 SOLUTIONS!!
May 6
Last day of class!
Lab 11 SOLUTIONS!!
This space for office use only!