Computer Science Fundamentals (CS153 2003S)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Experiments in Java]
[Scheme Reference]
[Scheme Report]
[CS153 2002S (Walker)]
[CS151 2003S (Rebelsky)]
[CS152 2000F (Rebelsky)]
[SamR]
This is an abbreviated course syllabus. Like everything else in this course, it is likely to change.
Weeks: 1, 2, 3, 4, 5, 6, 7, 8, break, 9, 10, 11, 12, 13, 14.
Week 1: Starting Scheme | |||
(01) Monday, 20 January 2003 Introduction to The Course Definitions: Computer science, computer programming, computing, ialgorithm, and more. Course basics. Administrative issues. Getting started with the ECA. Assignments: Scan through the various administrative handouts (due Tue). Fill out the introductory survey (due Tue). Take the administrivia quiz (due Tue). Read: Beginning Scheme (due Tue). Skim: The DrScheme Lab (due Tue). |
(02) Tuesday, 21 January 2003 Starting Scheme About Scheme Lab: The DrScheme Programming Environment. Lab: Starting Scheme. Assignments: Read Symbolic Values in Scheme. Read Lists in Scheme. Read Numbers in Scheme. |
(03) Wednesday, 22 January 2003 Basic Types: Symbols, Lists, and Numbers Overview of Types Symbols Lists Numbers Lab on Types Assignments: Read Procedures in Scheme (due Fri). Do Laboratory Writeup 1 (due Mon). |
(04) Friday, 24 January 2003 Procedures Why define your own procedures? How to define your own procedures. Lab on user-defined procedures. Assignments: Read Conditional Evaluation in Scheme. |
Week 2: Control Structures | |||
(05) Monday, 27 January 2003 Conditionals A problem: Turning numbers into letters (in English and Scheme). Making life easier: Conditionals. What kinds of tests can you use in conditionals? Due: Laboratory writeup 1. Assignments: Read Boolean values. |
(06) Tuesday, 28 January 2003 Conditionals Lab Lab. Assignments: Read Repetition with Recursion. |
(07) Wednesday, 29 January 2003 Recursion with Lists Reflections on Recursion. Lab: Repetition with Recursion. Assignments: Do Homework 1: Deep Recursion. Read Recursion with Natural Numbers. |
(08) Friday, 31 January 2003 Recursion with Numbers Introduction to numeric recursion. Lab. Assignments: Read Local bindings with let .
|
Week 3: Procedures, Revisited | |||
(09) Monday, 3 February 2003 Local Bindings Why name things. Naming things with let .
Naming things with let* .
Naming procedures.
Lab: Local Bindings with
let .
Assignments: Read Preconditions and Postconditions. |
(10) Tuesday, 4 February 2003 Preconditions and Postconditions The need for documentation. Verifying preconditions. An example: Sum of squares. Husk and Kernel programming. Other uses of Husk and Kernel. Lab. Due: Homework 1: Deep Recursion. Assignments: Laboratory Writeup 2: Preconditions and Postconditions. Read Local Procedure Bindings with letrec .
|
(11) Wednesday, 5 February 2003 Local Procedures Lab. Assignments: Read Variable-Arity Procedures. |
(12) Friday, 7 February 2003 Variable-Arity Procedures Definition of arity. Why have variable-arity procedures. How to write variable-arity procedures. Lab. Assignments: Read Characters in Scheme. Read Strings in Scheme. |
Week 4: More Types | |||
(13) Monday, 10 February 2003 Strings Short introduction to strings. Lab: Characters and Strings. Assignments: Scan Sam's Quick HTML Reference. Read CGI Scripting in Scheme. |
(14) Tuesday, 11 February 2003 CGI Scripting What is CGI? Giving input to CGI programs. Reading input in CGI programs. Lab: CGI. Assignments: Read Pairs and Pair Structures. |
(15) Wednesday, 12 February 2003 Pairs and Pair Structures Behind the scences in Scheme: Memory. Pairs and Cons cells. Dotted pairs. Lab. Assignments: Start Exam 1. Read Vectors. |
(16) Friday, 14 February 2003 Vectors Problems with lists. A solution: Vectors. Side note: The begin construct.
Assignments: Read Design Patterns and Higher-Order Procedures. Read pp. 69-73 of Bailey. (Stop right before 4.1.2.) |
Week 5: Higher-Order Procedures and More | |||
(17) Monday, 17 February 2003 Higher-Order Procedures Design patterns, revisited. Key ideas of higher-order procedures. Two key higher-order procedures: map and apply .
Lab.
Assignments: Read more higher-order procedures. Scan chapters 1 to 3 of Algorithms for Functional Programming. |
(18) Tuesday, 18 February 2003 More Higher-Order Procedures Operator sections. Currying. Questions on readings. Lab. Assignments: Review sections from Bailey. |
(19) Wednesday, 19 February 2003 Algorithm Analysis Comparing Algorithms. Asymptotic Analysis. Eliminating Constants. Asymptotic Analysis in Practice. The Role of Details. |
(20) Friday, 21 February 2003 More Algorithm Analysis Big O notation, revisited. Doing Big-O Analysis. Dominant terms. Big-O Analysis of Recursive Procedures. Experimental analysis. Due: Exam 1. Assignments: Homework 2: Some Web Services. Read Tail Recursion. |
Week 6: Algorithms | |||
(21) Monday, 24 February 2003 Tail Recursion Kinds of recursion. Why do tail recursion. Generating lists tail-recursively. |
(22) Tuesday, 25 February 2003 Searching Algorithms for common problems. A key problem: Searching. Searching Examples. Lab. Assignments: Read: Searching. |
(23) Wednesday, 26 February 2003 Sorting The problem of sorting. Writing sorting algorithms. Examples: Insertion sort, Selection sort. Lab. Assignments: Read Sorting. |
(24) Friday, 28 February 2003 Fast Sorting Algorithms Formalizing the problem. Merge sort. Quicksort. Lab. Assignments: Read Merge Sort. Read Quicksort. Read Randomness and Simulation. Laboratory Writeup 3. |
Week 7: Scheme, Concluded | |||
(25) Monday, 3 March 2003 Sorting Laboratory Due: Homework 2. Assignments: Read Randomness and Simulation. |
(26) Tuesday, 4 March 2003 Randomness and Simulation The Problem of Simulation. Scheme's random procedure.
Simulating the roll of dice.
Lab.
Assignments: Read Input. |
(27) Wednesday, 5 March 2003 Program Input Interacting with programs. Scheme's output procedures. Scheme's input procedures. Lab. Assignments: Start Exam 2. Read Files in Scheme. |
(28) Friday, 7 March 2003 Files Files and ports. Reading values. Reading characters and lines. Lab. Due: Lab writeup 3. Assignments: Exam 2. Read the introduction to Java in Bailey. Read introduction and discussion of Experiments in Java, laboratory J1. |
Week 8: Introduction to Java | |||
(29) Monday, 10 March 2003 Getting Started with Object-Oriented Programming An introduction to object-oriented programming. Assignments: Read Introduction to J2: Objects in Java and Discussion for J2: Objects in Java. |
(30) Tuesday, 11 March 2003 Getting Started with Java About Java. Your first Java program. Java in the MathLAN. Lab. Assignments: Read Introduction to J2: Objects in Java and Discussion for J2: Objects in Java. |
(31) Wednesday, 12 March 2003 Java Lab Preparation. Lab. |
(32) Friday, 14 March 2003 Objects, Methods, and Classes Building Classes. The Problem: A Fraction Class. Overview of a Class Declaration. Fields. Methods. Constructors. Different Class Uses. Some Design Issues. Due: Exam 2. Assignments: Read Lab J4: Boolean Expressions and Conditionals. |
Spring Break | |||
Week 9: More Java Basics | |||
(33) Monday, 31 March 2003 Conditionals Review. Boolean expressions in Java. Basic conditionals: the if statement.
Other conditionals: the switch statement.
Lab.
Assignments: Read J5: Loops. |
(34) Tuesday, 1 April 2003 Loops Review of Conditionals. Iterative Repetition. While Loops. Do Loops. For Loops. Lab (J5.1 and J5.3). Assignments: Read Lab X3 (focus on the section on exceptions). Do Homework 3 (due next Tuesday). |
(35) Wednesday, 2 April 2003 When Things Go Wrong Problems in Programs. Techniques for Handling Errors. Exceptions: Java's Primary Error-Handling Technique. Dealing with Procedures that Throw Exceptions. Optionally-Catchable Exceptions. Throwing Exceptions. Defining Exceptions. Assignments: Read J6: Arrays and Hash Tables. |
(36) Friday, 4 April 2003 Arrays Introduction to Arrays. Arrays in Java. An Application: Fibonacci Numbers. An Application: Box Packing. |
Week 10: Object-Oriented Design | |||
(37) Monday, 7 April 2003 Exam 2 Quicksort. From Strings to Values. Assignments: Think about what you know about inheritance for tomorrow. |
(38) Tuesday, 8 April 2003 Designing Objects Introduction to Object-Oriented Design. Why do Object-Oriented Design. Some basic strategies. Reuse. Assignments: Read Lab O1, Lab O2, and Lab O3. |
(39) Wednesday, 9 April 2003 Inheritance Reuse. Inheritance. Inheritance in Java. Special issue; Constructors. Special issue: Interfaces. Special issue: Abstract Classes. Example: Prerequisites. |
(40) Friday, 11 April 2003 Polymorphism Quick review of inheritance. Questions from previous class. Polymorphism. Interfaces. An Example. Abstract Classes. Assignments: Exam 3: Java Basics. Read Chapters 1 (The Object-Oriented Method) and 6 (Lists) of Bailey. |
Week 11: Lists | |||
(41) Monday, 14 April 2003 Polymorphism Example Review: What is a Prereq ?
Building the PrereqOr class.
Building the PrereqAnd class.
Building the PrereqCourse class.
|
(42) Tuesday, 15 April 2003 Introduction to Abstract Data Types and Data Structures Organizing Data. Example: Arrays. An ADT Hierarchy. Collections. |
(43) Wednesday, 16 April 2003 Some List ADTs What is a list? A SimpleList ADT. An OrderedList ADT. An SortedList ADT. The java.util perspective. |
(44) Friday, 18 April 2003 List ADT Design, Continued Due: Exam 3. |
Week 12: Other Linear Structures | |||
(45) Monday, 21 April 2003 Sorting Out Sorting |
(46) Tuesday, 22 April 2003 Implementing Lists with Arrays Implementation: Using Arrays. Due: Exam 3. Assignments: Homework 4: A To-do List. |
(47) Wednesday, 23 April 2003 Implementing Lists with Nodes Deletion in Array-Based Lists. Detour: Packages in Java. Scheme Lists, Pairs, and Nodes. Implementing Lists with Nodes. Variants. |
(48) Friday, 25 April 2003 LInear Structures About linear structures. Stacks. Queues. Implementation notes. Assignments: Read the chapter on linear structures in Bailey. |
Week 13: Dictionaries | |||
(49) Monday, 28 April 2003 Priority Queues, Heaps, and Heap Sort Priority Queues. Simple Implementations. Trees. Heaps. Assignments: Read Bailey on Dictionaries and Hash Tables. Begin Exam 4. |
(50) Tuesday, 29 April 2003 The Dictionary ADT Introduction to the Dictionary ADT Applications. More Details. Dictionaries vs. Databases. |
(51) Wednesday, 30 April 2003 Implementing Dictionaries with Lists Review: The Design of Dictionaries. Central Dictionary Methods. Dictionaries vs. Databases. Implementing Dictionaries with Lists. |
(52) Friday, 2 May 2003 Implementing Dictionaries with Hash Tables Dictionaries vs. Arrays. The Idea of Hashing. Hash Functions. Hashing in Java. Handling Hashing Conflicts. Exceptions. |
Week 14: Wrapup | |||
(53) Monday, 5 May 2003 Implementing Dictionaries with Binary Search Trees Review. An ADT for binary search. Binarya search trees. BSTs and dictionaries. Assignments: Read About End-of-course Evaluations (due Wed). Fill out the development evaluation (distributed in paper form) (due Wed). |
(54) Tuesday, 6 May 2003 Algorithm Design, Revisited ADT Design. Algorithm Design. A Problem: Filling Book Shelves. A Solution: Dynamic Programming. Due: Exam 4. |
(55) Wednesday, 7 May 2003 Evaluation Final project presentations. About evaluations. Evaluations. Final statements. |
(56) Friday, 9 May 2003 Wrapup Final comments. |
This document is automatically generated from a number of other documents. Hence, I may not always remember to update the history.
Friday, 12 January 2001 [Samuel A. Rebelsky]
Course at a Glanceform.
Tuesday, 7 Janaury 2003 [Samuel A. Rebelsky]
Tuesday, 14 January 2003 [Samuel A. Rebelsky]
Sunday, 16 February 2003 [Samuel A. Rebelsky]
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]
-
[EC]
[Honesty]
[Instructions]
[Links]
[Search]
[Syllabus]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Lab Writeups]
[Outlines]
[Readings]
[Reference]
ECA:
[About]
[Grades]
[Quizzes]
[Submit Work]
[Change Password]
[Reset Password]
Misc:
[Experiments in Java]
[Scheme Reference]
[Scheme Report]
[CS153 2002S (Walker)]
[CS151 2003S (Rebelsky)]
[CS152 2000F (Rebelsky)]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Tue May 6 09:19:12 2003.
The source to the document was last modified on Sun Feb 16 20:54:53 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS153/2003S/Handouts/glance.html
.
You may wish to
validate this document's HTML
;
;
Check with Bobby