CS141 Lab 1

Class Webpage:  http://www.cs.ucr.edu/~jiang/141-homepage.html

For the labs of the first week:

• Introduction of the TA and the rules.

• Hand out fortune slips and encourage subscription to class mailing list.

• Brief introduction to Linux and C++ in linux

1. Commonly used linux commands (ls, cp, mkdir, mv, rm, emacs...)
2. Makefile
3. argc, argv command line parameters.    
• e.g. file (right-click your mouse, then choose "save link as..."):  arg.cc
4. Discuss debugging: gdb (ddd is a graphic interface to gdb) and simple commamds  

(setting a break, tracing step by step etc)

Here is a more complete tutorial on gdb

Take a look at the programming material from:

http://www.literateprogramming.com/kelseylick.pdf

GNU Emacs Reference Card (pdf, 80 KB)

• Count time in a C++ execution

1. through linux "time" command: $ time  YourProgramName

2. using the following codes in C++: mytime.cc  Makefile

• A quick example program concerning linked list: finding an element in linked list of numbers, returning a pointer to the record containing the number, and deleting the record.

To see how it works, download files (right-click your mouse, then choose "save link as..."):
 link.h  link.cc   main.cc   Makefile

(Please see comments in the files for explanations.)

• The concept of a graph (undirected and directed), and how a graph is represented in programs. Some simple examples of adjacency matrix and adjacency list, as in Levitin Ch 1.4 and CLRS

• The concepts of trees and binary trees, and how they are represented in programs. Some simple examples of tree/binary tree data structures from Levintin and CLRS. This review can be moved to Lab 2 if time is an issue.

• The notation of pseudo-code. Real program vs pseudo-code. Give an example algorithm written in pseudo-code but hard to write in C++. For example, an algorithm to test if a map is 2-colorable or a code written in a shell/scripting language (Perl, Python) to do some meaningful thing.

• If time allows, review the top-down design approach for designing algorithms, using the problem of finding both the smallest and the largest elementis in a list. Develop an algorithm from rough pseudo-code to one with concrete data structures (i.e. a linked list or an array). Analyze the time complexity of the algorithm.

• In-lab exercise: Write an efficient algorithm for computing f(x) = x^n.

1. Write an efficient algorithm (in pseudo-code) for computing f(x) = x^{62} (i.e. x to the power of 62) by using the repeated squaring technique.
2. Does your algorithm use 9 multiplications?
3. (optional, for keen students) Can you do it in 8 multiplications?
4. (optional, for keen students) Can you generalize your algorithm to f(x) = x^n for any n? Can you implement your algorithm as a C++ code?

TA: Explain the repeated squaring technique. Keep track of which students completed the exercise.