CMPU-145

Foundations of Computer Science

Spring 2013



Instructor Luke Hunsberger
Lectures Mon/Wed @ 1:30 - 2:45 p.m., OLB 205
Labs Mon @ 3:10 - 4:25 p.m., OLB 105

Contents and Frequented Links


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

The primary textbook for the course is: Sets, Logic and Maths for Computing by David Makinson (c) 2012, published by Springer-Verlag.

We will be following the chapters in this book quite closely; however, there will be occasional supplements distributed in class. The material in the text will be complemented by regular programming assignments.

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:

Labs 20%
Assignments 45%
Exams 35% (midterm: 15%, final: 20%)

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.

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!