CSE 303 - Schedule and Lecture Notes, Winter 2010

Course Schedule

Please note that the schedule is subject to minor changes based on our progess.

The lecture slides, the list of readings for each class, and other extra information are at the bottom of this page.

Lecture 1

• Slides: lecture1.pdf (lecture slides will be posted before lecture when possible)
• Lecture 1 extras:
  • In class, we poked around the file system on a linux machine. Among others, we walked all the way up to the root directory and explored the /bin and /homes subdirectories. We encourage you to log in to attu and try to create some subdirectories in your home directory (the mkdir command creates a directory) and otherwise poke around to get some practice. Here is a link to the instructions that will help you get started using attu.
  • Here is the history of all the commands that we executed in class: lecture1-history
  • The readings below go over what we did in more detail (there won't be that much to read for each lecture).
• Readings: please read the following sections from the Linux Pocket Guide
  • What's in This Book (pages 1-5)
  • Getting Help (pages 7-8)
  • In the Filesystem section
    • Introduction (page 13)
    • Home Directories (pages 14-15)
    • File Protections (pages 19-20)
  • The Shell (pages 19-33 but skip the section on Installing Software)
• Additional documentation:
  • Pages 37 through 46 in the Linux Pocket Guide give more details about the commands we used in class.

Lecture 2

• Slides: lecture2.pdf
• Lecture 2 extras: No extras for this class. You can find more information about the commands that we used in class in your Linux Pocket Guide in the sections outlined below.
• Readings: please read the following sections from the Linux Pocket Guide
  • The Shell (pages 19-33) [This is the same as last lecture]
• Additional documentation:
  • File Properties (pages 56-65)
  • Viewing processes (pages 104-107)
  • Controlling processes, only the kill commnd (page 108)
  • Pages 60 through 63 in the Linux Pocket Guide give more details about some of the commands we used in class
  • If you are curious, feel free to read pages 110 through 165. We talked a little bit about some of those topics, but we will not go into this any deeper. You do not have to read any of this stuff. This is just for your own enjoyment and knowledge.

Lecture 3

• Slides: lecture3.pdf
• Lecture 3 extras:
  • trivial.sh and trivial.sh.output
  • variable.sh and variable.sh.output
  • inner.sh and outer.sh. Please experiment with these scripts as shown in the lecture notes.
  • arguments.sh and arguments.sh.output (this is the output of executing ./arguments.sh a b c d)
  • example1.sh. This script has sophisticated side effects. Please run it on attu to see what happens
• Readings: please read the following sections from the Linux Pocket Guide
  • Programming with Shell Scripts (pages 166-178)
  • Selected bash features (pages 21-29)
• Additional documentation:
  • Linux Pocket Guide. "File Creation and Editing" (about emacs) pages 51-55

Lecture 4

• Slides: lecture4.pdf
• Lecture 4 extras:
  • variable.sh and variable.sh.output
  • arithmetics.sh and arithmetics.sh.output (output when executing arithmetics.sh 1 2 3)
  • loops.sh, loops.sh.output,and numbers2.txt
  • arrays.sh, arrays.sh.output, and numbers.txt
• Readings: please read the following sections from the Linux Pocket Guide
  • Shell Variables (pages 23-24)
  • Programming with shell scripts (pages 166-179)
• Additional documentation:
  • Bash reference manual Section 6.5 (Arithmetics) and 6.7 (Arrays)

Lecture 5

• Slides: lecture5.pdf
• Lecture 5 extras:
  • history-lecture5
• Readings: please read the following sections from the Linux Pocket Guide
  • egrep (pages 73-74)
• Additional documentation:
  • Lots of documentation on the web including the following
  • http://analyser.oli.tudelft.nl/regex/
  • http://www.panix.com/~elflord/unix/grep.html
  • http://www.robelle.com/smugbook/regexpr.html

Lecture 6

• Slides: lecture6.pdf
• Lecture 6 extras:
  1. Sed: ex1-commands.txt, ex1.txt, ex2-commands.txt, ex2.txt, ex3-commands.txt, ex3.c
  2. Additional exercises for sed: sed-questions.txt and sed-answers.txt. Additional files for exercises: ex4.txt and brackets.txt
  3. Awk: awk-commands.txt, grades.txt, grades2.txt

1. Readings: please read the following sections from the Linux Pocket Guide
   1. More Powerful Manipulations (pages 80-81).
2. Additional documentation:
   1. sed
   2. awk

Lecture 7

1. Slides: lecture7.pdf
2. Lecture 7 extras: Please take a careful look at the examples we went through together in class
   1. hello.c and hello.output.txt
   2. pointer.c and pointer.output.txt
3. Readings: please read the following chapters from Programming in C
   1. Chapter 1, 2, and 3
   2. Chapter 11 (pages 235-240)

Lecture 8

1. Slides: lecture8.pdf
2. Lecture 8 extras: Please take a careful look at the examples we went through together in class
   1. scope.c and scope.output.txt
   2. bool.c and bool.output.txt
   3. null-pointer.c and null-pointer.output.txt
   4. dangling.c and dangling.output.txt [Note that the output may be different for you when you try this program]
   5. pointer-to-pointer.c and pointer-to-pointer.output.txt
   6. format.c and format.output.txt
   7. fileIO.c, file1.txt, and fileIO.output.txt [Very useful for hw3]
3. Readings: please read the following chapters from Programming in C
   1. Skim chapters 4, 5, 6, and 8
   2. Chapter 11 Pointers and Functions (pages 254-259)
   3. Chapter 16 Formatted I/O (pages 348-359)

Lecture 9

1. Slides: lecture9.pdf
2. Lecture 9 extras: Please take a careful look at the examples we went through together in class
   1. simple-array.c and simple-array.output.txt
   2. array.c and array.output.txt . Additional examples are commented out in the code. Try to uncomment different examples to experiment with them.
   3. multi-array.c and multi-array.output.txt
   4. string.c and string.output.txt
3. Readings: please read the following chapters from Programming in C
   1. Chapter 7, 10, and 11
   2. Chapter 8, Section "Functions and Arrays" (pp 137-152)

Lecture 10

1. Slides: lecture10.pdf
2. See above lecture 8 and 9 extras. We looked at some of them.
3. Lecture 10 extras:
   1. arguments.c and arguments.output.txt, output when executed with arguments "Hello there" Hi world
   2. debug_me.c and fixed.c
4. Readings: please read the following chapters from Programming in C
   1. Chapter 18 (skip the first part about using the pre-processor for now. It will make sense after lecture 14).
   2. Chapter 16 "Input and Output Operations with Files" and "Special Functions for Working with Files" (pages 359-371)

Lecture 11

• Slides: lecture11.pdf
• Docs: http://subversion.apache.org/ and http://svnbook.red-bean.com/

Lecture 12

• Slides: lecture12.pdf
• Lecture 12 extras: Please take a careful look at the examples we went through together in class.
  • struct.c and struct.output.txt
  • struct-functions.c and struct-functions.output.txt
  • cast.c and cast.output.txt
  • struct-dynamic.c and struct-dynamic.output.txt
  • Here is an additional example that shows a concrete and practical use of dynamic memory management. In this example, we create an array that grows automatically when elements are added to it. This is a simple and frequently used implementation of dynamically resizable arrays. As you can see, using an array that resizes itself does not come without a cost. From time to time, we must recopy all the elements of the existing array into a bigger one. growing-array.c
• Readings: The material we covered in class corresponds to the following chapters in Programming in C. Please read these chapters if you want more information about the topics that we covered:
  • Chapter 9
  • Chapter 14 sections on "Typedef Statement" and "Data Type Conversions" (pp 325-330)
  • Chapter 17 section on "Dynamic Memory Allocation" (pp 383-388)

Lecture 13

• Slides: lecture13.pdf
• Lecture 13 extras: Please take a careful look at the examples we went through together in class.
  • Stack example: stack.h, stack.c, and main-stack.c
    To compile this example: gcc -g -Wall -o main-stack main-stack.c stack.c
  • Additional example showing a queue data structure: queue.h, queue.c, and main-queue.c
  • The concept of a "pointer to a pointer to a Node" is difficult. To understad it better, try the following:
    • Modify functions push and pop to take a Node* instead of a Node** as argument. See if the statements inside the functions make sense to you. However, see what happens when you push elemets onto and pop elements from the stack now.
    • On a piece of paper, draw the content of the stack when you declare the following local variables:
      • Node my_element;
      • Node *top = &my_element;
      • Node **ptr_top = ⊤
      • What appears at the memory locations reserved for ptr_top, top, and my_element?
• Readings: No readings for this class

Lecture 14

• Slides: lecture14.pdf
• Lecture 14 extras: No extras
• Readings:
  • http://www.cnn.com/2010/TECH/02/04/wired.olympics.mind.control.lights/index.html
  • http://dsc.discovery.com/news/2007/01/10/thoughtrobot_tec.html
  • http://seattletimes.nwsource.com/html/localnews/2003488286_robot21m.html

Lecture 15

• Slides: lecture15.pdf
• Lecture 15 extras: Please take a careful look at the examples we went through together in class.
  • include.c, includeA.h, headers/includeB.h. The output of this program is irrelevant, just look at the list of included header files and how they were included.
  • include2.c and includeC.h. The output of this program is irrelevant, just look at the list of included header files and the #ifndef directives. You can try and comment out the #ifndef directives to see what error message your will get during compilation.
  • constant.c
    • The output of this program is irrelevant, what we want is to examine the output of the preprocessor. The output from runing: gcc -E constant.c is here: constant.preprocessed.txt. I'm including the entire output just to show you that a whole bunch of things get inserted because of the #include <stdio.h>. The important thing is to take a look at the end of the file where you will see how MESSAGE got replaced with "Hello World".
    • Just to see the difference, here is the output from running gcc -E constant.c after commenting out the #include directive: constant.preprocessed2.txt
  • macro.c. The output of the program: macro.output.txt. The output of the preprocessor: macro.preprocessed.txt.
  • assert.c
    • Output when compiled with gcc -g -Wall -o assert assert.c is assert.output1.txt
    • Output when compiled with gcc -D NDEBUG -g -Wall -o assert assert.c is assert.output2.txt
  • conditional.c
    • Output when compiled with gcc -g -Wall -D DEBUG -o conditional conditional.c is conditional.output1.txt
    • Output when compiled with gcc -g -Wall -o conditional conditional.c is conditional.output2.txt
  • fancy-conditional.c
    • Output when compiled with gcc -g -Wall -D LOG_LEVEL=2 -o fancy fancy-conditional.c is fancy.output1.txt
    • Output when compiled with gcc -g -Wall -D LOG_LEVEL=1 -o fancy fancy-conditional.c is fancy.output2.txt
    • Output when compiled with gcc -g -Wall -o fancy fancy-conditional.c is fancy.output3.txt
• Readings: The material we covered in class corresponds to the following chapters in Programming in C. Please read these chapters to get more information and extra examples about the topics that we covered:
  • Chapter 13
  • Appendix C "Compiling programs with gcc"
  • Chapter 18 section on "Debugging with the Preprocessor" (pp 389-395)

Lecture 16

• Slides: lecture16.pdf
• Lecture 16 extras:
  • Makefiles: Makefile.v1, Makefile.v2, Makefile.v3, Makefile.v4, Makefile.v5
  • Source code: main-queue.c, main-stack.c, queue.c, queue.h, stack.c, stack.h
• Readings: The following are some extra references about the material we covered in class.
  • Programming in C, Chapter 15 and Appendix C
  • Tutorial on static and shared "C" librarires (if you want to learn more)
    • LUPG Tutorial (there are other useful tutorials on this site)
  • Make/Makefile online documentation and tutorials:
    • GNU Make manual
    • University of Hawaii, College of Engineering Make tutorial
  • Manpages for gcc, ranlib, ar, and ld can also be helpful
  • In the future (after this class), you should try to learn cmake, autoconf and automake.

Lecture 17

• Slides: lecture17.pdf
• Lecture 17 extras:
  • Hello world in C++: hello.cc
  • Namespaces: namespace.cc
  • Our first C++ class: Property.h, Property.cc,main.cc, a simple Makefile (and wtf). We only started to examine the content of files Property.h and Property.cc. We will go through main.cc and actually execute this program in Lecture 18.
• Readings: You may find it helpful to take a look at one of many C++ tutorials available on the web
  • C++ tutorial at cplusplus.com

Lecture 18

• Slides: lecture18.pdf
• Lecture 18 extras:
  • Our example with inheritance (note that Property.h and Property.cc below are slightly different from the above):
    • Source code: common.h, Property.h, Property.cc, Land.h, Land.cc, House.h, House.cc, and main.cc
    • Additional files: Makefile, env.sh, and wtf.
    • Program output with DEBUG defined: inheritance.output.txt
• Readings: No readings for this class

Lecture 19

• Slides: lecture19.pdf
• Lecture 19 extras: our example with inheritance (note that the code is, again, different from last lecture):
  • Source code: Element.h, common.h, Property.h, Property.cc, Land.h, Land.cc, House.h, House.cc, and main.cc
  • Additional files: Makefile, env.sh, and wtf.
  • Program output for examples with type casting: estate.cast-examples.output.txt
  • Program output for examples with virtual functions: estate.virtual-function-examples.output.txt
  • Program output for examples with abstract classes: estate.abstract-classes-examples.output.txt
• Readings: No readings for this class

Lecture 20

• Slides: lecture20.pdf
• Lecture 20 extras:
  • Simple template example: template.cc and template.output.txt
  • Examples using stl : main.cc with the output: estate.output.txt
  • The above example depends on our usual files common.h, Property.h, Property.cc, Land.h, Land.cc, House.h, and House.cc
  • Additional files: Makefile, env.sh, and wtf.
• Readings: No readings for this class
• Documentation on the Standard Template Library

Lecture 21

• Slides: lecture21.pdf
• Lecture 21 extras: No extras
• Readings: No readings

Lecture 22

• Slides: lecture22.pdf
• Lecture 22 extras: No extras
• Readings: No readings for this class

Lecture 23

• Slides: lecture23.pdf
• Lecture 23 extras:
  • Readable code: unreadable.cc and unreadable.output1234.txt, the output of the program when executed as: unreadable 1 2 3 4
  • Defensive programming and encapsulation: StringList.h, StringList.cc, main.cc, Makefile, and main.output.txt
  • What we have studied helps produce higher quality and more stable code, but does not mean that the code is secure: timing.c
• Readings: No readings for this class

Lecture 24

• Slides: lecture24.pdf
• Lecture 24 extras: No extras
• Readings: No readings for this class

Lecture 25

• Slides: lecture25.pdf
• Lecture 25 extras: No extras
• Readings: No readings for this class

Lecture 26

• Slides: lecture26.pdf
• Lecture 26 extras: For this lecture, you do not need to learn about the syntax of threads, just the main principles (e.g., concurrency, race conditions, locks, deadlocks). We used the following examples in class to illustrate these issues. Note that our use of "sleep" in these examples only helps us emphasize some of the issues. These issues arise without using "sleep".
  • Basic threads with a race condition: bank.cc
  • Fixed race condition with threads: bank-fixed.cc
  • Deadlock illustration: bank-deadlock.cc
  • Fixed deadlock: bank-nodeadlock.cc
  • Makefile
• Readings: No readings for this class

Lecture 27

• Slides: lecture27.pdf
• We did not get to any of the sample problems in the slides, but feel free to try them on your own time.
• Lecture 27 extras:
  • Makefile for all the executable programs in the extras
  • "Bad pointer = crash!" (stack/heap confusion): bad-pointer.c
  • Misuses of free(): free-tree.c
  • Stack/heap distinction for C++ object method calls: stack-vs-heap.cc
  • Virtual and non-virtual C++ method calls: cows.h, cows-main.cc
  • Example makefile: sample-makefile
• Readings: No readings for this class