Notes N1 -- INTRODUCTION FOR MATH 10

Math 10 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

1. Preliminary Note

Be very careful when reading manuals, books, or handouts (like this one) pertaining to computers and Computer Science. They are written by people who already know the computers. They are also notoriously hard to read. Often, they are very exact - each word has a meaning and an exact and unique meaning. Individuals should read pertinent information BEFORE trying to do anything on a machine. To do otherwise is like being a wrong-way driver on a freeway on-ramp - ignoring the signs and going on anyway. You have to expect trouble if you fail to read important information carefully before you attempt something significant.

2. Introduction to the Course

Over the years, the introductory course to Computer Science as taught in the Mathematics and Computer Science Department has changed several times. Originally, three things were taught: (1) workings of a computer (introduction to machine architecture, now taught in COEN 21); (2) machine language (now taught in COEN 20); and (3) Fortran IV (Fortran-90/95 is now taught in Math 60).

Since 1982, the course has been re-structured and updated (sometimes yearly) based on the most recent national recommendations, the computers currently available at Santa Clara, and the development of computer languages. Now, this course covers the following topics:

1. Programming in a multi-user environment (using the Unix operating system).
2. Programming on personal computers - DOS/Windows or Macs.
3. Editors - how to get information into computers and change it when needed.
4. Disciplined, structured, meticulously exact, general programming concepts (language independent) (perhaps the most important aspect).
5. The programming language C++ (and its special features, e.g., recursion, pointers, data structures, data encapsulation, object-oriented programming).
6. Algorithms.
7. The connection between computers/technology and society.

The language BASIC or Pascal is not taught in this course, and previous programming experience is not considered a prerequisite for the course either. This is a first course in Computer Science for majors, but also a general course for other majors as well.

There is much to learn about any computer language, but we will not cover every aspect/feature of C++. One reason is that few people have ever had to use every feature of a specific language. Another reason is that some of the subtleties of the languages are only grasped after a few years of use. THEREFORE, don't expect to be able to program Tetris by the end of the quarter.

Instead, what I hope to do is to teach (1) the basics of C++, (2) a disciplined method of programming, and (3) a way of learning (from books and manuals) further features of C++ and other programming languages.

I will also point out local implementations/features of languages (i.e., the things that don't match the textbooks).

This course may make reference to other widely used languages, such as Fortran-90/95 and Java. Much of the syntax of Java is very similar to that of C++ although there are some significant differences. ( Fortran is the old standby and still very good for numerical calculations and, like English, it is widely used, particularly by numerical analysts, but no one really likes some of the out-dated style and rules. Fortran-90/95 is the subject of Math 60, taught in the winter quarter.)

3. Comment About Three Related Concepts

One has to distinguish carefully between three concepts related to computers. All of them involved ``commands,'' but they are used differently and must be kept separate in one's mind.

1. Operating System: this tells the particular computer you are using what to do (e.g., print a data file or execute a program). Each computer has a slightly (or drastically) different operating system. Each operating system has its own set of commands.

2. Editor: with an editor you create and change ``files'' in which are stored programs written in some computer language. There are several different editors and each editor has its own set of commands. Like word processing programs, editors enable a person to modify files, but unlke word processors, one does not format or print a file directly by means of this program.

3. Language (a primary objective of this course): we will deal with the computer language C++ and concepts related to object-oriented programming. However, you cannot do anything with any language unless you know how to use the operating system of the multi-user system (and Windows95/DOS or the Mac environment), and some editor.

Don't forget your password for your account and don't make it obvious (do not use `JOSHUA' a la the movie War Games, do not use your name or initials), don't give it to others (not even to your ``best'' friend-you are responsible for what happens from your account), change it once or twice during the quarter.

5. Health Concerns

Recent studies have indicated a repeated problem associated with long hours behind a computer-physical stress. People have developed eyestrain, ``typist''-cramp, carpal tunnel syndrome, and back strain due to not moving enough and over-concentration on the screen.

SOLUTIONS: 1) Do not spend a significant length of time at a computer without taking a break (even if for only 10 minutes an hour). 2) Remember that the computer is supposed to help you-you are in charge, even if it doesn't seem to understand you.

6. First Courses: Techniques and Creativity

Like first courses in many subjects, Math 10 teaches a lot of basics and a lot of techniques. Realize that people learn techniques by practice, and much of this course consists of hands-on practice by writing programs. Also, we have to be content with basics: We can't write great literature after just one course in English. Similarly with Computer Science: Don't expect to be able to re-write the program for the air traffic controllers after this one course. Computer Science (like math in general or even music or art) has two sides to it.

NOTE THE DIFFERENCES BETWEEN

It is very hard to teach creativity, since it takes long practice on the part of the learner. It is easier to teach and learn techniques, but they only go so far.

7. Images of Computer Science

Just because you can type and speak English, you will not automatically become another Shakespeare. Just because you drive a car or use plumbing, does not qualify you to fix a car or be a licensed plumber. Just because you can play a piano or a guitar, does not mean you are also a great composer.

In teaching someone how to ride a bike, one says: ``you put your feet on the pedals and move them up and down, hold the handlebars to steer in the correct direction, and keep your balance.'' What more can you say?

Part of using a computer is like writing symphonies or riding a bike - only so much can be taught - an instructor can only give so many rules and instructions. This course tries to teach a method. It is trying to teach how to use a computer and write programs. These are mainly self-taught skills, like music or bike-riding.

This first course also will teach some theoretical computer science, such as algorithms for searching and sorting, which are not bound to one specific computer language. Similar to a first course in music theory, this course will cover techniques (i.e., rules of the computer language) and will try to help you become creative with those techniques (i.e., write programs). Note, however, that it is relatively easy to teach technique, but no teacher can (easily) teach you how to be a great programmer (or musical composer).

8. Introductory Computer Science Courses

Introductory computer courses across the country have notorious reputations.

Some perceptions are true: courses are hard, time-consuming, and frustrating. Some perceptions may not be so true: bad teachers, worse books. Often times, machines are thought to be inadequate - too few machines in labs, and the multi-user system is always down.

I'll try to make the course as painless as possible. However, beware that there is a certain amount of difficulty to be expected, and, at times, frustration. A Purdue University Study (reported February 1984) said that over 5 year period, 65% of CS majors dropped out of the program and changed majors!

One of the greatest problem is reading instructions and not understanding or thinking they don't apply. It is like wrong-way drivers on freeways. They see ``DO NOT ENTER - WRONG WAY'' and think the sign doesn't apply to them. Remember what you read and try to apply it!

9. Translation - Compiling

Computers don't (directly) understand C++ or Java or Fortran or BASIC. They understand ``Machine Language.'' A machine language program would be similar to a program written for a programmable pocket calculator (e.g., HP).

The computer tries to translate a program written in C++ or Fortran into a new program in its own code, and then runs its own program. This process is called compilation and the program which does the translation is called the compiler. If the compiler is unable to make a complete translation because the programmer incorrectly typed the program (typos or incorrect use of statements), the compiler will give a list of errors. If no compiler errors appear, then the (translated, machine language) program can then be run. Running the machine language program is called execution. The original C++ program is also called the SOURCE program and the machine language program is called the OBJECT Code.

When the compiler cannot translate a program because it was mis-written, e.g., the rules of the language were not followed, it gives error messages. Carefully read these error messages. Sometimes, not all errors are caught. Usually the messages tell you the line to look at, although, sometimes you have to look at the previous line. You can then re-edit your program file and correct the errors, and try to compile again.

Some compilers have powerful debug features. Debuggers usually enable you to step through a program, line by line. This line by line step-through is particularly useful when a program ``runs'' without any compiler errors, but the answers are still wrong!

10. Introduction to ``Programming''

Whether you use a natural or artificial (i.e., computer) language, you must learn by practice. The proof that you can use a computer language is if you manage to communicate with a computer, i.e., if a machine accepts your ``program'' and does what you want it to do.

THEREFORE, in this course, there will be 10 programs to aid you in learning the computer language.

11. Programming Steps

1. Analyze the problem-design and plan the program. What information do I have? What do I want as results? What do I need in the middle? How is the information given? (also see section 15 below.)
2. Coding-write the program in a computer language. (also see sections 15-18 below.)
3. Preliminary de-bugging (``anti-bugging'')-correct syntactic errors (i.e. rules of language errors), correct compiler errors, typos. (also see section 20 below.)
4. Major de-bugging-find logical errors, unforeseen cases. (also see section 20 below.)
5. Correcting and updating-``Maintenance''

A lot of time and energy is spent in programming. Referring to these steps of programming just listed, if you are a good programmer and lucky, steps 3 and 4 will equal steps 1 and 2 in length of time. If not, step 4 (de-bugging) alone can take 5-6 times longer than the first three steps. A 1973 Department of Defense study on the cost of programming suggested that it took $75 per instruction for (initial) development of a program, but it took $4000 per instruction for maintenance!

12. Definition of Programming

Programming is the (creative) art of breaking a problem into minute details and (technically) coding these details in some technical ``computer language.'' Many people have said, ``Computers will always do what you tell them to do-however, this is not always what you actually want them to do!'' Be concerned about details! Programming can be an exercise in frustration because it shows us our shortcomings and lack of foresight. As the proverb says, ``The devil is in the details.''

Prof. Don Knuth, professor emeritus of the Department of Computer Science at Stanford, in fall 1998 suggested that ``about 2 percent of the general population has this way of thinking that makes them born to program ... A lot of people can write code, but I'm talking about people who are really in sync with computers.'' Thus, for many people, programming will not be easy to learn!

13. Writing Programs

The basic concept in programming is to be able to organize what you have to do in sequential order. In other words, you must decide what comes first, what comes second, what comes next, etc.

E.g., Graduation Program

1. National Anthem
2. Invocation
3. President's address
4. Awarding of Honorary degrees
5. Key address
6. Awarding of student degrees
7. Valedictory speech
8. Benediction.

The general rule is the next step is not done until the previous step is completed. This rule also holds true for computer programs.

We must also be careful of (unwritten and unconscious) assumptions! In the graduation program above, we make certain (unwritten) assumptions: We assume that both the students and the faculty have marched in and that the guests in the audience have arrived! We don't normally start the national anthem if no one is on stage or if they are still marching in!

In computer programs, we almost always have to be explicit about everything and cannot leave any assumptions unwritten!

Always have a program written before going to a workstation. NEVER write your program from scratch at the computer without some sort of pre-written code. You will probably waste a lot of time, and possibly keep someone (more prepared?) from using the computer you are occupying.

14. Breaking a Problem Apart

The major problem in writing programs is often learning how to break a problem apart to a coherent sequence of programming steps.

A helpful first step is to write out the individual steps in English.

For example, take the problem of converting Arabic numerals to Roman numerals, e.g., 23 Þ XXIII.

We need to analyze our own (unconscious) thought patterns.

Where did the XX come from?

Where did the III come from?

How do you (mathematically, i.e., using plus, minus, times, divide) ``break apart'' 23 into 2 and 3? How do you make sure that you don't break apart 23 into a 3 and a 2 and get XXXII!

How do you explain what you did (mathematically)?

For practice, look at the sample problems given in section 21 below. Spend a few minutes thinking about a solution to problem 1 (describe how to tie your shoe laces) and the first part of problem 4 (breaking a 4-digit number into the 4 separate digits).

15. Programming Hints

1. What information do I have? What do I want to do? What intermediate information do I need to obtain? How am I going to obtain that information?

2. What are the intermediate steps I need to do to solve the entire problem? List them in English words-then use ``successive refinement'' to break the problem down into even more steps. (see section 18c below.)

3. Are any of the steps too big? Am I doing too much at once without trying to break the problem down more?

4. Do I need to repeat an action several times (i.e., do I need to include a loop)? What type of loop-counted or conditional? (Counted-C++ for; Conditional-while or do ... while) In a conditional loop, what is my condition? Do any condition variables actually change inside the loop?

5. Do I need to make a choice? For multiple alternatives, use a C++ switch. For simple alternative, use if ... else. WARNING: Choice structures do not automatically repeat!!!

6. Do I need information from outside the program (i.e. from an input file )? When should I read this information? Should I read it all at once, or one-by-one (processing and eliminating one bit of information before reading the next bit)? WARNING: do not attempt to ``read'' from memory-one uses values stored in memory-in C++, scanf or cin statements are used only to get information from outside the program (i.e., from some input file).

7. How should I store information-in separate variables, in an array, using a record structure? Do I need pointer variables?

8. How should I output the information-in a loop, with one cout or printf statement, or with many different output statements?

9. Can I use a subprogram (subroutine or function) to aid readability? Do I need a subprogram to avoid duplicating code? Will the subprogram be used recursively?

16. Programming Style

A good programming style has the following characteristics:

1. is readable, easy to debug (this may be more important than having a clever algorithm), clear.
2. is structured, well-organized, good flow, self contained with labeled sub-sections, logical pattern.
3. is modular, short segments (1-2 pages per segment or subroutine, with each subroutine/function doing one or two things), uses subprograms (procedures, functions).
4. uses the best features of the language (e.g., avoids global variables, uses data and procedural encapsulation).
5. is well-commented (see next section).
6. uses indentations to show sub-sections and substructures (see section 18d).
7. is efficient (both with regard to space and time), but not at the expense of the above qualities!

17. Comments

Programs should (and, for this course, MUST) have three types of comments:

a) Program Heading.

This is a block indicating 1) the title of the program, 2) the programmer's name, 3) the date it was developed, 4) other useful information (e.g., course and instructor).

b) Variable Explanations.

In C++, the variable names should be chosen to be self-evident (i.e. do not use x to refer to miles!). However, in other languages, restrictions on the length of identifiers may force an explanation section of what role certain variables play in the program, which are input variables, which are output variables, which variables change values, etc.

c) In-line Comments.

Sub-sections and sub-structures should be identified. Rarely does one see a program ``over-commented.'' Unknown algorithms (or algorithms or theorems not easily recognizable) should also be indicated. Sometimes closing braces (or ``end'' statements) should be labeled to distinguish multiple occurrences.

a) Use a ``structured'' language

(C++, Fortran-90/95, Ada). These newer languages force a good programming style. The older languages, such as BASIC and older versions of Fortran easily led to what is called ``spaghetti code'' (the logical flow of an old BASIC or Fortran program is about as obvious as the ``flow'' of a bowl of spaghetti). Most modern books (and teachers) rant and rave against the ``GO TO'' statement, a major villain linked to spaghetti code.

b) Flow charts.

These are diagrams which label the major parts or statements of a program and help a person see what the program does and in which order.

c) Successive Refinement.

This is a repetitive approach to programming, in which one first labels major goals/sections of the program, and then successively proceeds to refine the goals. E.g., ``find roots'' might be refined to ``(1) read coefficients; (2) use quadratic formula.''

d) Block structure and indentation.

It is visually very useful to see the structure when looking at program code. Subgroups should always be indented. In old BASIC and Fortran programs, each line usually started at the left edge right below the previous line, which made the program very difficult to read. Programs must be indented in this course.

e) COMMENTS!

As mentioned above, there should be 3 types of comments in each program. It is very rare to see a program over-commented. This is a major concern of industry today - that programs are well-documented and that the documentation is readable and useful for future maintenance. Programs must be commented in this course.

19. Rules for Machine Problems/Programs

a)

Help others, but not too much.

b)

Programs must be substantially your own work.

c)

Don't tempt others, especially on harder programs (either consciously, or unknowingly).

d)

Don't throw copies of programs away without destroying them or until after the program is due. (In some schools, people have been known to rummage through trash to get old print-outs in computer rooms).

e)

Don't leave copies of working programs in one room and go to another.

f)

It is better to turn in a partially working program that is all your own work than none at all, or to submit a completely running program which is more someone else's work than your own.

1. Remember that semi-colons need to be placed at the end of each C++ statement, whether on the same line or not.

2. Read error messages carefully-remember which line the error is on-remember that the real error may actually be before the line indicated in the error message.

   ·check if variables are misspelled or not declared
   ·check for missing semi-colons
   ·check for unbalanced blocks delimiters (braces).

3. After syntactical errors are eliminated (errors regarding the rules of the language which give compiler errors), you may still have logical errors which give incorrect answers. (You may want to use a debug option, if available for your compiler, or add output statements to check program flow or values of variables.)

4. You may want to re-read these notes after writing a few programs. Some of the instructions may make more sense after experience with programming. Early in the course, what is required is the ability to follow rules exactly more than many creative insights.

5. REMEMBER: most of the time on a computer is spent editing, making and correcting mistakes. One learns a lot by making mistakes, but it can be very time-consuming and frustrating.

21. Sample Problems

1. Write out detailed steps to tie your shoelace.

2. Write out detailed steps to start your car.

3. Write out the steps necessary to translate an Arabic number (any number under 39) to a Roman numeral.

4. Write a C++ program to analyze the following number theoretic problem.

   Take any four-digit number (with not all 4 digits being the same). Re-arrange its digits in two different ways-lowest to highest, and highest to lowest. Subtract the smaller new number from the larger new number to obtain another number. Repeat this process (of re-arrangement and subtraction) seven times each time using the final new number.

   Is there any pattern?

22. Brief History of Programming Languages

1. Ancient History - 1940s - 50s

   Early computers had limited memory and no auxiliary storage. This required short programs with tricky techniques. Programs were almost always written in machine language or sometimes in ``assembly'' (in which abbreviations are used instead of numerical codes).

2. Progress - 1950s - 60s

   The first few wide-spread languages appeared ( Fortran and COBOL). Improvements in hardware, particularly in memory technology, enabled languages to be designed with features making it easier to program (Algol, Algol-68). This led to fewer mistakes and more readable code. There was a new concern to make newer language definitions more exact and mathematical (by using ``BNF'' definitions of languages).

3. Modern History - 1970s - present

   Revisions of older languages were common along with the development of special purpose languages. The development of ``super-computers'' with vector and parallel processing possibilities complicates the revision of older languages.

4. Genealogy Chart

FORTRAN (55)
     |
     |                        ALGOL(60)          COBOL(60)
(FORTRAN II)        JOVIAL(60)   |          EULER
     |                           |            |          
     |        PL/I(65)           |            |
FORTRAN IV(66)                   |            |         BCPL(67)
     |                           |          Pascal        |
     |                           |       (1st draft 68)   |
     |                         ALGOL-68       |           |
     |                              (1st compiler 70)     B(70)
(WATFIV)                                  (rev'd 73)      |
     |                                        |           C(72)
FORTRAN 77                                    |           |
     |                 Ada (82)               |           |
     |                                   Modula-II (83)   |
     |                                        |           C++(84-88)
     |                                   Oberon (88,89)   |
FORTRAN 90                   Java(90-93)                  |
     |                            |                       |
FORTRAN 95                   Java 1.0 (95)                C++(ANSI-96) 
                                  |
                             Java 1.1 (97)