CSci 1901: Class Notes

[Week 1 -- Scheme | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10 | Week 11 | Week 12 | Week 13 -- Python | Week 14 | Week 15 ]

Week 13

This week we will start learning Python. To learn the language, take a look at the Python Tutorial by Guido van Rossum. We will cover the control flow (chapter 4, 4.1, 4.2, and 4.3), defining functions (4.6), and the list data structure (3.1.4, 5.1.1. and 5.1.4).

Monday, April 16

Wednesday, April 18

Week 14

Monday, April 23

  • In Python more operations mutate objects than in Scheme, but the concepts are the same as in Scheme. Sharing and mutations can be confusing. Let's work through some examples:

    Wednesday, April 26

    Friday, April 28

    Week 1 - Intro to Scheme

    This week we will start with the basic aspects of Scheme

    Wednesday. January 17

    Introduction to the objectives of the course and to Scheme. Why we learn Scheme.

    Friday, January 19

    Week 2 -- recursion

    This week we will learn how to write more complex procedures and we will learn about recursion as a way of decomposing problems.

    Monday, January 22

    Wednesday, January 24

    Friday, January 26

    Week 3 - complexity

    This week we will learn about complexity of procedures. We will learn how to control complexity by understanding the computational process that different procedures generate and we will learn how to speed up computations by thinking about clever algorithms.

    Friday, February 1 and Monday, February 5

    Here are the files John used in during his lectures.

    Monday, January 29

    Wednesday, January 31

    We will look at how to make faster programs by being more careful in how we write programs. We will look, in particular at the problem of finding if a number is prime. Read the material in the textbook on exponentiation (Section 1.2.4) and on prime numbers (Section 1.2.6)

    Try solving Exercise 1.16 (page 46), Exercise 1.17 (page 46), Exercise 1.25 (page 55), and Exercise 1.26 (page 55).

    Friday, February 2

    Week 4 - lists

    This week we will learn about writing constructors and selectors to build and access abstract data types. We will work in particular on sequences or lists.

    Wednesday, February 7

    Friday, February 9

    How lists are represented and more examples of using lists. Here are the problems we did in class:

    Week 5 - lambda, let, filter

    Monday, February 12

    Wednesday, February 14

    Today we will work on more examples of recursion on lists. We will learn about patterns, or templates, we can use to abstract similar operations. In the case of lists, we have already seen some of the patterns:

    Friday, February 16

    Week 6 - trees

    Monday, February 19

    Midterm exam

    Wednesday, February 21

    We will start working on more complex data structures, in particular on hierarchical data structures (often called nested lists or trees).

    Friday, February 23

    Week 7 - map, accumulate, sets

    Monday, February 26

    More practice on map and accumulate.

    Wednesday, February 28

    Friday, March 1

    Review of the use of the binary tree representation for sets.

    Week 8 - sets

    Monday, March 5

    This week we will talk about using abstractions via constructor/selectors to hide details on data structure choices.

    Wednesday, March 7

    Here are the files John used in lecture:

    Friday, March 9

    Week 9 - local state

    This week we will start Chapter 3 and talk about how to change the value of a symbol (or a datastructure) in Scheme and how to write procedures that keep local state.

    Monday, March 19

    Wednesday, March 21

    Friday, March 23

    Week 10 - mutators

    Monday, March 26

    Practice and second quiz. Look at the solution.

    Wednesday, March 28

    Guest lecture by Prof. Dovolis. Review of set!. Examples of set-car! and set-cdr!

    Friday, March 30

    Week 11 - tables

    Monday, April 2

    Wednesday, April 4

    The table data structure.

    Friday, April 6

    Pop Quiz 8
    Write a procedure (remove-2nd! lst) to remove the second element of a list. Assume the list contains at least two elements.
    STk> (remove-2nd! '(a cold happy easter is coming))
    (a happy easter is coming)
    STk> (remove-2nd! '(enjoy it))
    Could you write a procedure to remove the first element of list? explain why or why not

    Here is a solution that modifies the data structure (note the ! at the end of the procedure name).

    (define (remove-2nd! lst) (set-cdr! lst (cddr lst)) lst)
    The figure shows the environment after the following:
    STk> (define a '(a cold happy easter is coming))
    STk> (remove-2nd! a)
    (a happy easter is coming)
    STk> (remove-2nd! a)
    (a easter is coming)
    We cannot remove the first element of a list by modifying the local data structure, since we do not know who points to the datastructure and we cannot change what they point to. A way of doing this is to keep the first cons box of the list but change its contents to be the contents of the second element and then remove the second element. This works only if the list contains at least 2 elements, otherwise when we remove the first element we are left with an empty list and the method will not work.
    (define (remove-1st! lst)
      (set-car! lst (cadr lst))
      (remove-2nd! lst))
    or directly
    (define (remove-1st! lst)
      (set-car! lst (cadr lst))
      (set-cdr! lst (cddr lst)) 

    Week 12 - queues and agenda

    Monday, April 9

    The queue data structure. What is a queue and how to implement it. Operations on queues, such as insert and delete, require modifying the data structure (as opposed to make a modified copy of it). To modify a data structure we use set-car! and set-cdr!. To understand how to write procedures to modify the data structure, make a graphical representation of it, mark on it the pointers that need to be changed, and write the corresponding scheme expression for each change. Make sure your procedures are correct when the queue is empty and when it becomes empty. You'll see in the procedures in the textbook two cases, one for the empty queue and another for a non empty queue. Try using ~boley/stk/runenvdraw to visualize the objects.

    Wednesday, April 11

    The agenda data structure and preparation for the AIBO lab.
    Look at the lecture notes for details.

    Friday, April 13

    More on the agenda. Recall that this is the data structure agenda.

    Pop Quiz 9
    1. Where does after-delay insert things?
    2. What's the difference between after-delay and add-action!
    3. Write a procedure to count how many actions are in an agenda
    4. How does propagate work?
    Copyright: © 2000-2007 by the Regents of the University of Minnesota
    Department of Computer Science and Engineering. All rights reserved.
    Comments to: Maria Gini
    Changes and corrections are in red.