UCSC BME 194 Winter 2004

Resource-efficient Programming

(Last Update: 18:27 PST 2 March 2004 )

Quick index to this webpage (http://www.soe.ucsc.edu/~karplus/bme194/w04):

registering for the class
who, when, and where
textbooks
evaluation
holidays
reading assignments
programming assignments
academic integrity
rough list of topics
skills required to pass
core topics

This course is being offered for the first time in Winter 2004, and does not yet have a permanent number. The BME 194 number is for a "group tutorial" and is a way to get the course offered before it is put in the catalog. The class will probably have a different number in future.

Registering:: This class is not in the winter time schedule. To register for it, you must come to class and get the secret code that allows you to register.
Content:: The course teaches students to write programs that use computer resources (time and memory) efficiently. The students will learn to measure resource usage and modify programs to get better performance. Programming exercises in the course will be done in the c programming language, as it is a simple, low-level language which has few hidden costs, making the effect of program changes for efficiency easier to understand. It is also commonly the language of choice for programmers who care about how efficient their programs are.
Target audience:: The course is particularly appropriate for programmers working at the limits of their hardware (bioinformaticians, game programmers, and embedded system programs).
Prerequisites:: CMPS 12B or 13H, CMPE 16, and MATH 19A. Students must already know how to program in a block-structured language (such as java, c, or Pascal); must have had an introduction to recursion and induction, logic, probability, and combinatorics; and must understand differentiation well enough to be able to optimize functions. CMPS 101 and CMPE 12C are not required prerequisites, but mastering the material in those classes would make resource-efficient programming easier.
Requirements satisfied:: The course can be used by bioinformatics majors as their dvanced programming elective (in place of CMPE 177, CMPS 104A, or CMPS 109). Students in other majors will have to petition their Undergraduate Directors to have the course counted as an elective.

Who, When, and Where:

Instructor: Kevin Karplus ( karplus@soe.ucsc.edu) http://www.soe.ucsc.edu/~karplus
Office hours: Wed 10--11, in 315B Baskin Engineering

TA: None.

Lectures: MWF 2-3:30 Earth and Marine Sciences B214

Texts

There will be two required texts, plus additional readings that will be distributed either on paper or via the Web:

Programming Pearls (2nd edition) Jon Bentley: This paperback book is a rewrite of a collection of columns that Jon Bentley wrote for the Journal of the Association for Computing Machinery. Some of the observations in them are rather trivial, but others are thought-provoking.
The C Programming Language (2nd edition) Kernighan and Ritchie: This book contains a concise summary of the C programming language and can be used both as a reference manual and as textbook for learning c.

Evaluation

The course will be evaluated primarily on the basis of weekly assignments. The assignments will usually consist of a programming exercise and some measurements to do to compare different approaches to the program. The programs will be evaluated on their correctness, their efficiency, and the quality of the documentation, both internal and external. The external documentation may contain such things as the results of timing tests and memory measurements.

The relative weights of the assignments in the evaluation has not been determined yet---it should be roughly proportional to how much time the different assignments take to do well. We will try to assign points to each assignment as it is given, but the total number of points won't be known until we've created all the assignments.

There may be some tests or quizzes, if this seems to be necessary to ensure that students are doing their own work and understanding the material. An announcement will be made in class and on this web page if exams or quizzes are to be given.

Holidays

Class will not meet Monday 19 January 2004 and Monday 16 February 2004. Prof. Karplus will not be able to attend class Feb 11 and Feb 13, but this will not be a holiday---there will be guest lectures by programmers who care deeply about efficiency.

Reading Assignments

You must do the reading, as I will be assuming in the lectures that you have read the relevant chapters of the books before coming to class. Feel free to ask about anything in the books or the lectures you don't understand, but don't ask dumb questions if you haven't done the reading!

Read by	Programming Pearls	The C Programming Language
Fri Jan 9	Column 1	Chapter 1
Mon Jan 5	Column 2	Chapters 2&3
Mon Jan 12	Columns 3&4	Chapter 4
Wed Jan 21	Columns 5&6 & Appendix 4	Chapter 5
Mon Jan 26	Columns 7&8 &Appendix 2	Chapter 6
Mon Feb 2	Columns 9&10	Chapter 7
Mon Feb 9	Column 11
Wed Feb 18	Column 12
Mon Feb 23	Column 13
Mon Mar 1	Column 14
Mon Mar 8	Column 15

Note: the goal is to have you know and be competent in programming in C by the beginning of February, so that the rest of the quarter can focus on using the programming skills.

Homework Assignments

I'm still in the process of figuring out the programming assignments---this is a tentative list and will certainly need more modification. Homework will be turned in via the "submit" command on the CATS Solaris machines. The "class locker" for submissions in bme194-kk.w04, so to submit hw1 you would give the command

    submit bme194-kk.w04 hw1 timing knights-tour.c

Homework assignments will be listed here as they become available:

Due date	Assignment	Submit directory	Files
14 Jan	time knight's tour	hw1	timing,knights-tour.c
28 Jan	bitset sort	hw2	README,.c and .h files,timing output,bitset-time.gnuplot
4 Feb	quicksort	hw3	README, time-sort.c, time-sort.out, time-sort.gnuplot, (optionally) time-sort.pdf
Fri 13 Feb	heapsort	hw4	README,.c,.h
Mon 23 Feb	hashing	hw5	README,.c,.h, example output
Fri 5 Mar noon	packed tries and memory use	hw6	README, .c, .h, example output
Thurs 11 Mar	redo any assignments that you aren't satisfied with	redo-hw1 ... redo-hw6	README (explaining what has changed!) and whatever else is needed

Classes begin Monday Jan 5. There are two holidays: Monday Jan 19, and Monday Feb 16. The last day of class is Friday March 12. There will be no final exam in the Monday March 15 8am--11am slot.

Academic Integrity

Anyone caught cheating in the class will be reported to their college provost (see UCSC policy on academic integrity) and may fail the class. Cheating includes any attempt to claim someone else's work as your own. Plagiarism in any form (including close paraphrasing) will be considered cheating. Use of any source without proper citation will be considered cheating.

Collaboration without explicit written acknowledgement will be considered cheating. If you ask people for help, get their names and acknowledge them in the assignment you turn in. If you offer someone help, make sure that they record your name in the program or assignment.

Rough list of topics we'll probably cover (not necessarily in order)

Note: this list is tentative---I have not yet gotten the reading and this topic list coordinated, and what is presented will depend on the class. How much time we spend on details of C will depend on how much C experience the class has previously had, for example. I'll try to keep a list of the topics actually presented.

The course will start with an introduction to the C programming language, including pointers, pointer arithmetic, arrays, and linked lists.
After introducing the language, we will cover many of the tools for creating, debugging, and profiling programs: emacs, gcc options, gdb, gprof, getrusage, ... . Assignments will include using breakpoints for debugging and measuring the execution time of routines (which in turn will require averaging over large samples).
After the students have attained some competence at measuring programs, we'll start looking at ways to improve program efficiency, possibly starting with converting linear search to hash tables (data structure conversion). An algorithmic conversion (such as linear search to binary search) is also a good early topic.
We'll then start looking at different algorithms and data structures for simple problems (sorting). We'll look both at algorithmic differences (the difference between insert sort and merge sort) and data structure differences (merge sort with array copying and merge sort with linked lists). As before, we'll be concentrating more on measured results of changes than on theoretic analysis.
Somewhere along the way we'll look at the speed of different I/O operations, particularly looking at one-pass vs. multi-pass tradeoffs, and reading a character at a time versus a line at a time.
We'll end the quarter with some more sophisticated data structures involving binary and n-ary trees. Heaps and heap sort will be presented as a space-efficient tree representation.

Skills required to pass

The following skills will need to be demonstrated in order to pass the class:

Able to use breakpoints and a debugger to debug C programs efficiently.
Able to use calls to timing routines and profilers to identify the time-critical parts of a program and modify the programs for greater speed.
Able to construct, debug, modularize, and optimize medium-size programs (less than 1000 lines).
Able to use hash tables, arrays, linked lists, and other data structures appropriately.

Core topics

The following topics are core material for the course and must be taught somewhere in the course:

Use of breakpoints, profilers, and other debugging and performance measuring tools. This must include some measurements of I/O time, not just CPU time.
Basic sorting algorithms (insertion sort, at least one divide-and-conquer algorithm such as quicksort or merge sort, heap sort).
Graph algorithms: depth-first search (typically a puzzle example, such as knight's tour or 8-queens).
Data structures: array, linked list, doubly-linked list, binary trees, n-ary trees, heaps, hash tables
Programming skills:
1. the use of pointers, procedures, header files, and makefiles for data hiding and abstraction;
2. how to construct, debug, and modularize large programs.
3. preconditions and postconditions
Documentation:
1. variable naming
2. what to comment on (and what not to comment on)
3. describing recursive routines with an external view

SoE home UCSC Bioinformatics Home Page BME 194 home page

Questions about page content should be directed to

Kevin Karplus
Computer Engineering
University of California, Santa Cruz
Santa Cruz, CA 95064
USA
karplus@soe.ucsc.edu
1-831-459-4250