Instructor: Prof. Keller, Olin 1253, x18483, keller at
cslhmcledu,
AIM: MuddProf
Meets: MW 1:15-2:30, Parsons 1285. My office
hours: MTWTh 2:45-4, or
drop-in
First-year
students only, grading
P/HP/NC, Homework 50%, Midterm 15%, Final 30%, Participation 5%
Languages we use: Scheme, Java, Prolog
The purpose of CS
65 is to provide an accelerated introduction for first-year students who are
advanced and who posess more than the usual motivation for study of computer
science. A student completing this course will have learned the topics in both
the general introductory course CS 5, as well as the second course CS 60.
Catalog Description
Accelerated
breadth-first introduction to computer science as a discipline for first-year
students who have some programming background. Computational models of
functional, object-oriented, and logic programming. Data structures and
algorithm analysis. Computer logic and architecture. Grammars and parsing.
Regular expressions. Computability. Extensive practice constructing
applications from principles, using a variety of languages. Prerequisite:
Permission of Instructor. 3 credit
hours. (Fall.)
|
Day |
Date |
Topics |
|
Wed. |
9/3 |
Lists,
S-Expressions, Scheme language, Overloading, Functions, Association Lists,
Unit Testing |
|
Mon. |
9/8 |
High-Level
Functional Programming, Problem Decomposition, Anonymous Functions (Lambda
expressions) |
|
Wed. |
9/10 |
Low-Level
Functional Programming, Recursion, Number representation |
|
Mon. |
9/15 |
Propositional
Logic Functions, Functional Completeness, Logic simplification |
|
Wed. |
9/17 |
Memory
organization, Lists vs. Arrays, Complexity considerations |
|
Mon. |
9/22 |
Directed
Graphs and Relations,
Graph
Searching |
|
Wed. |
9/24 |
Trees
and DAGs |
|
Mon. |
9/29 |
Language
Interpreter |
|
Wed. |
10/1 |
Open
lists in Java |
|
Mon. |
10/6 |
Copying
and Equality, Exceptions |
|
Wed. |
10/8 |
Abstractions
and Interfaces, Higher-Order Functions in Java |
|
Mon. |
10/13 |
Enumerations,
Closed Lists, Inner Classes, |
|
Wed. |
10/15 |
Inheritance,
Abstract Classes, Event-Handling, Graphics |
|
Mon. |
10/20 |
Fall
Break |
|
Wed. |
10/22 |
Take-home
Mid-term exam |
|
Mon. |
10/27 |
Threads,
Garbage Collection |
|
Wed. |
10/29 |
Grammars
and Parsing |
|
Mon. |
11/3 |
Finite-State
Machines, Regular Expressions |
|
Wed. |
11/5 |
Logic
synthesis, Hardware components, Processors |
|
Mon. |
11/10 |
Turing
Machines |
|
Wed. |
11/12 |
Predicate
logic, Prolog and databases |
|
Mon. |
11/17 |
Non-determinism,
Backtracking, Constraint solving |
|
Wed. |
11/19 |
Machine
interpretation, Assembly language |
|
Mon. |
11/24 |
Constructing
a compiler |
|
Wed. |
11/26 |
No
class the day before Thanksgiving |
|
Mon. |
12/1 |
Program
correctness |
|
Wed. |
12/3 |
Complexity,
Algorithm design, Sorting |
|
Mon. |
12/8 |
Undecidability,
the Halting Problem |
|
Wed. |
12/10 |
Incomputability
Reductions |
|
Tue. |
12/16 |
Final
Exam,
2-5 pm |
Collaboration Policy
Independent
work is desired. You can discuss solution approaches with other students, so
long as no viewing or copying of code, either electronically or on paper, is involved.
If you get significant help from someone, including a grutor, professor,
classmate, or other or work in a group, it is your obligation to cite the
circumstances and acknowledge the individuals involved. Otherwise it is unfair
to others who prefer to work alone. In the long run, undue collaboration can
hurt you.
Grutors (Grader+Tutors)
Below
are the times when a grutor will be in the CS lab, B102 Beckman Hall, to help
you.
|
Saturday |
Sunday |
Monday |
Tuesday |
Wednesday |
|
2-5 pm |
2-4 pm |
|
|
|
|
|
|
|
|
6:30-8 pm |
|
|
7-10 pm |
8-11 pm Marty Field |
8-9 pm |
8-11 pm |
|
|
|
|
|
10-12 pm |
Resources
Wikipedia: Scheme | Java | Prolog | Computabilty