Date: Tue, 14 Jan 1997 22:51:25 GMT Server: Apache/1.1b4 Content-type: text/html Content-length: 18556 Last-modified: Sat, 21 Dec 1996 00:20:04 GMT CptSci 112a: Lecture schedule

CptSci 112a: Lecture schedule

Return to the CptSci 112a home page.

Previous lectures and events.

12/20/96, at 2:00pm, in WLH 116
Final Exam. The final will be a cumulative closed-book exam. Just like the midterm, but half again as long. A sample final (with solutions) is available.
12/12/96, 7:00pm, in AKW 500
Review session.
12/6/96
Retrospective. Where to go from here.
12/4/96
Binary trees.
12/2/96
Recursive search procedures.
11/22/96
More examples of divide-and-conquer. Algorithms and their worst-case costs. Binary search and mergesort.
Demos:
  • mergesort.p Unlike the demo in lecture, this program actually works.
11/20/96
Recursion. Divide-and-conquer as a tool for solving problems. Finding all combinations and permutations of letters in a string.
Readings:
Chapter 16.
11/18/96
Queues.
Readings:
Sections 15.2-15.3.
Demos:
11/15/96
Abstract data types. Concrete representations vs abstractions. Dictionaries and stacks.
Readings:
Sections 15.1, 15.4-15.6
11/13/96
Hash tables. A hash table is a trick for speeding up access to the elements of a linked list by splitting the list into many separate lists (stored in an array). To find out which list each element goes in, one uses a hash function that transforms each element into a consistent but random-looking number. The effect is a bit like using a filing cabinet with many separate folders to store data instead of one big stack of paper. See the demo program for an example.
Demos:
11/11/96
Linked lists. Traversal, insertion, deletion.
Demos:
Readings:
Sections 14.12-14.16
11/8/96
Pointer basics. Declaring pointer variables. Operations on pointers. New and Dispose. Declaring and adding elements to a linked list.
Readings:
Sections 14.1-14.11.
11/6/96
More file munching. Using files to communicate between different programs.
Demos:
  • draw.p. Drawing program that saves its work to a file.
  • redraw.p. Displays files in the format generated by draw.p.
  • autodraw.p. Generates a file suitable for loading in redraw.p.
  • circle. Output of autodraw.p.
  • monet. A formerly huge drawing of a smiley-face, signed by the master. This is a compressed version of the test file drawn in class. The compression was done on a Unix machine using a program written in Perl, which demonstrates how data files with well-defined formats can be manipulated by a wide variety of tools.
  • picasso. Another fine work of art from class.
Handouts:
Assignment Eight.
11/4/96
Files. Reading and Writing files. Basic file commands: Reset, Rewrite, Close, NewFilename, OldFilename.
Readings:
Sections 9.3-9.6
Demos:
11/1/96
Sets.
Readings:
Sections 13.3-13.5.
Demos:
10/30/96
Operations on characters. Chr and Ord. Parsing using finite-state machines.
Readings:
Section 8.1.
Handouts:
Assignment Seven.
10/28/96
Built-in functions for manipulating strings: pos, copy, omit, include, and concat.
Readings:
Section 8.5
Demos:
  • replacer.p With bonus YesMaster procedure, not shown in lecture!
10/25/96
Strings and characters. The Length function. Treating a string like an array of characters.
Readings:
Sections 8.1-8.4, plus Length description in 8.5.
Demos:
10/23/96
Variant records.
Readings:
Sections 13.6 and 13.7.
Demos:
Handouts:
Assignment Six.
10/21/96
Enumerated data types.
Readings:
Sections 13.1 and 13.2.
Demos:
  • conquest.p This program didn't appear at all in lecture, but I wrote it beforehand while playing around with enumerated data types, and it has some nice examples of doing things with them and 2-d arrays. So I figured it would make more sense to put it up here than let it go to waste.
10/18/96
Multi-dimensional arrays and their uses.
Readings:
Section 11.9. Ignore the discussion in Section 11.8 on parallel arrays. The technique discussed there is almost always better done with an array of records as described in Section 12.2.
Demos:
  • toxic.p (This version is slightly improved from the one shown in lecture; it includes a version of ButtonClick that works better.)
10/16/96
Midterm. The midterm will be give in class at the usual time and location. It will be a closed-book test, covering everything discussed in class up to 10/11/96. You should be comfortable with the material in Chapters 1, 2, 3 (Sections 3.1-3.4 only), 4, 5, 6, and Sections 11.1-11.4 and 12.1 and 12.2 in the book. A sample midterm is available showing roughly the length and types of questions you should expect; you may wish to try going through this before the review session to see if you have any questions. Note that questions on the sample midterm are not exhaustive: the real midterm may touch on different subjects and use different types of questions.
Handouts:
Assignment Five.
10/14/96
Review session.
10/11/96
More tricks with arrays. Computing minima and maxima, searching, sorting.
Readings:
Sections 11.6, 11.7.
Demos:
10/9/96
Arrays.
Readings:
Sections 11.1-11.4, 12.2.
Demos:
10/7/96
Records and abstract data types.
Readings:
Section 12.1. (Yes, this is skipping ahead a lot. We'll come back.)
Demos:
10/4/96
Procedures with state. Most procedures maintain no information from one call to the next, so they always act exactly the same way. Sometimes this isn't what we want, so by used of a global variable or a call-by-reference parameter we can produce procedures like iterators (returning e.g. 1,2,3,4,5, etc.) or pseudorandom number generators (which return random-looking numbers; see also the library of useful procedures).
10/2/96
Examples of using call-by-reference parameters and functions. Getting input from the mouse.
Demos:
  • average.p illustrates use of various techniques to return information from procedures.
  • mouse.p A simple drawing program.
  • button.p Detecting button clicks.
Handouts:
Assignment Four.
9/30/96
How Pascal uses memory. Global variables vs local variables. Call-by-reference (var) parameters. Functions.
Readings:
Sections 6.2-6.4.
9/27/96
Examples of using while and repeat..until loops.
Demos:
9/25/96
More applications of loops: animation. Unbounded loops.
Handouts:
Assignment Three.
Demos:
Readings:
Sections 5.3, 5.5.
9/23/96
More about for loops. Debugging. Fencepost errors.
Demos:
9/20/96
Introduction to loops. Bounded loops: for/to and for/downto.
Demos:
  • bottles.p "99 Bottles of Beer on the Wall" --- a simple program using a for loop.
  • circles.p. Draws a bunch of circles; example of nested for loops.
Readings:
Sections 5.1, 5.2, 5.8 (first part).
9/18/96
The case statement. Local variables.
Demos:
personality.p (Case statement demo).
Handouts:
Assignment Two.
Readings:
Section 4.7 (case statement), Sections 2.3, 2.4, 6.1.
9/16/96
More tricks with if/then statements. Boolean expressions and variables. Preview of recursion.
Demos:
Readings:
Sections 4.4, 4.6, 4.8. Resist the temptation to read Section 4.5: the description of how to get the mouse position will not work in Think Pascal.
9/13/96
Pascal syntax and the mysteries of semicolon placement. Begin..end blocks. If/then statements.
Readings:
Sections 4.1-4.3 (various forms of if/then statements).
9/11/96
More graphics. Decomposing tasks into subtasks, and then building procedures to do all the subtasks.
Demos:
face.p Draws a bunch of cartoon faces.
Handouts:
Homework One
Readings:
Sections 3.1-3.4, 3.10 (basic graphics commands).
9/9/96
Arithmetic. Integers vs reals. Graphics commands.
Demos:
drawing.p (Basic drawing commands).
Readings:
Sections 2.1-2.3, 2.5 (arithmetic); 2.7-2.8 (drawing lines).
9/6/96
Declaring and using constants and procedures. How avoiding redundancy increases clarity and power of programs.
Demos:
Old MacDonald program.
Handouts:
HOW TO sheet.
Readings:
Sections 1.8 (simple procedures), 2.12 (constants), 6.1 (procedures with parameters). You should probably also read Sections 2.10 and 2.11 (input and output).
9/4/96
Introduction. How the course is set up. What programming is all about. Running Think Pascal.
Demos:
boring.p
Handouts:
Readings:
Chapter 1.

Return to the CptSci 112a home page.