Computing & Software Systems 342:
Mathematical Principles of Computing
Fall 2011
Along with CSS 343, this fast-paced course is intended to bring you up to speed so you can take Junior and Senior level CSS courses. It does this by integrating the fundamental mathematics of computing with detailed instruction in program design. By the end of this quarter, you will be familiar with much of the C++ language and the basics of object-oriented programming. You will understand how to analyze a problem and design a solution. You will know many basic data structures, algorithms, and the tradeoffs among memory, running time, and implementation time associated with them. Topics include: recursion, computational complexity and algorithm analysis, logic, mathematical proofs and induction, lists, stacks, queues, sorting and searching, data abstraction, and object-oriented methods.
Instructor. Michael Stiber stiber@u.washington.edu, room UW1-360D, phone (425) 352-5280, office hours Mondays 10AM–12PM or by appointment.
Course Web. http://courses.washington.edu/css342/stiber/.
Lectures. Tuesdays and Thursdays, 3:30–5:30, room CC1-041.
Grading. Your course average is computed as: 25% homework + 10% peer design reviews + 25% midterm + 30% final + 10% online contribution
I don’t grade on a curve. I compute everyone’s quarter average based on the formula above. I then use my judgment to determine what averages correspond to an ‘A’, ‘B’, etc. for the quarter. Some quarters’ assignments, etc. turn out harder, and so the averages are lower. Other quarters, averages are higher. I adjust for that at the end. Decimal grades are then computed using the equivalences in the Time Schedule, linearly interpolating between letter-grade boundaries. Furthermore, I am well aware of the significance of assigning a grade below 2.0, in terms of impact on your career here at UWB. I can assure you that I examine in detail the performance in this course of each student before assigning a grade below 2.0.
What is the difference between this and grading on a curve? With the latter, the goal is to have X% ‘A’s, Y % ‘B’s, etc. My way, I would be happy to give out all ‘A’s (if they were earned). FYI, in a “typical” quarter, below 60% might be a ‘D’, 60%–75% a ‘C’, 75%–85% a ‘B’, and above 85% an ‘A’. You may use this as a rough guide; however, if you really want to know how you’re doing, please see me. I reserve the right to adjust these scores to reflect the specifics of assignments, test questions, etc. for each quarter.
The following is a brief summary of the most important things you can do to succeed in this class:
As indicated under “Grading”, above, your grade in this class is computed from a weighted average of five different activities during this quarter. You are of course familiar with tests; below I describe the others.
We will be making heavy use of the course discussion forum to provide a means for out-of-class, in-depth discussion, either of topics I select or of questions/comments by fellow students. I will generate a new thread for each week — some I will kick off with a question or other material to get the conversation started, and some wil merely be available for conversations surrounding the homework, tests, or whatever is going on in class that week. It is your responsibility to make valuable contributions to at least some of the conversations during the quarter (I will place a guide to what makes a contribution valuable elsewhere on the course web site). At the end of the quarter, you will be asked to submit your two best posts as evidence of your contribution; your contribution grade will be computed from those.
As an alternative to a forum post, you may substitute a substantive, non-duplicative entry into the CSS Wiki. Presumably, this entry will cover some aspect of using the CSS computing infrastructure, of workflow hints for inter-operation of your home computing environment with that in the CSS program, etc.
We will have both written exercises and programming assignments. While all programming assignments will have a value of 100 points, the value of written exercises will vary (likely in the range of 15–30 points). Subsequent sections of this syllabus carefully spell out (in detail) both the procedures for program submission and the content of what you should submit. Please read the syllabus carefully. If there is anything you don’t understand or are not sure about ask me. I will assume that you have done so, and will mark off if what you submit does not match what is required.
The philosophy behind the programming assignments is to exercise your growing abilities to solve problems using computers. Note that I do not say to exercise your programming ability; I assume that, though you may be a beginner, you are basically familiar and comfortable with the process of writing and debugging software. In this class, you will learn about a variety of problem-solving tools: algorithms and data structures (taken together, abstract data types), approaches (for example, recursion), and mathematical techniques to compare and develop new algorithms (algorithm analysis, logic, mathematical induction, etc). The homeworks are explicitly designed to be substantial — they will require you to use what you learn in a systematic manner. As an example, imagine that we have just covered the topic of lists, and in class discussed a list of integers. I would not assign a homework that has you implement a list of strings. The point of learning about lists would be to understand them so that you can use them to solve problems (and to know when they are appropriate for use). Therefore, a more suitable assignment would be one in which you are asked to implement a simple text editor, which internally might use a list to hold the lines of text. This would allow you to investigate how a generic abstract data type’s capabilities can be related to the specific functionality of a particular program.
Assignments will be due at specific dates and times. I will not accept any lateness in this class — if your assignment is submitted even a few minutes late, it will not be graded, and you will receive a zero for that assignment. In fact, we will be using the UW Collect It system, which will not accept late submissions. Except for special circumstances, such as medical and other emergencies, no exceptions will be made to this policy (this includes crashed/eaten/lost disks — make frequent backups). You are more than welcome to submit work before the due date.
We will be dividing assignments into two phases, and you will be responsible for completing each phase by the indicated deadline. Because of the amount of material and the tight timing of the quarter, it is absolutely essential that you carefully read and follow the procedures in this syllabus. I will present an initial assignment description during class and will expect you to commence on the assignment immediately. I make these assignment purposefully vague and incomplete in certain respects. The two phases are “specification and design” and “implementation”; they are graded separately — the former as part of a peer design review and the latter in testing by me.
Note that this represents one-half of the time allotted to your programming assignment. Therefore, before handing in your preliminary specification and design, you should ask yourself, “Does this represent 50% of the work I’ll do on this program?” 2. At this point, you will have roughly a week to implement your design. You will submit your program using the UW Collect It system. The Collect It area will only accept tar or zip files, and the submission size is strictly limited, so please submit only source code. I will unpack your submission in a directory dedicated to your assignment, compile all of the .cpp files into a single executable, and test it. Testing will be performed using g++ on one of the 320 lab Linux machines. It is your responsibility to ensure:
I allocate credit based on your coding style, your documentation, and on your program’s execution characteristics (“correctness”, determined by black-box testing). For example, if your program does not compile under g++, you will receive zero points for correctness. I will run your program against a set of test cases (which I will not release ahead of time); partial credit will be awarded if it passes only some of them. I will not debug your program or try to figure out why it doesn’t work — partial credit only comes from passing test cases. Any other way of assigning partial credit would, in my opinion, be unfair: based more on my debugging ability than the qualities of the program. Because of this, I require you to design your program before you write code, and I strongly urge you to implement your program in stages, so that you always have a partially working version. If you use a development environment other than g++, then I suggest that you periodically move your code to a machine that has g++ to compile and test it (again, I do not endorse the approach of using another compiler, I am merely suggesting prudent practice). Of course, I am more than happy to meet with you about your program before or after the due date.
Program Grading. Generally speaking, adherence to coding standards will be worth 15% and program correctness (in other words, does it work?) 85%. However, depending on the specific nature of each assignment, the exact percentages (and any other aspects’ weights) may change. One example of this would be an assignment including a significant written portion.
If you believe that you have a disability and would like academic accommodations, please contact Disability Support Services at (425) 352-5307, TDD (425) 352-5303, FAX (425) 352-5455 or at rlundborg@uwb.edu. In most cases, you will need to provide documentation of your disability as part of the review process. More information is available at the DRS web site.
Unless you are specifically involved in a group activity, you are expected to do your work on your own. If you get stuck, you may discuss the problem with other students, provided that you don’t copy code from them. Programming assignments must be developed and written up independently. You may always discuss any problem with me. You are expected to subscribe to the highest standards of honesty. Failure to do this constitutes plagiarism. Plagiarism includes copying assignments in part or in total, debugging computer programs for others, verbal dissemination of algorithms and results, or using solutions from other students, solution sets, other textbooks, etc. without crediting these sources by name. Plagiarism will not be tolerated in this class, any more than it would be in the “real world”. Any student guilty of plagiarism will be subject to disciplinary action. Please believe me, neither you nor I want to go through an academic misconduct hearing.
I strongly encourage you to come to class. You will be held responsible for all material covered in class, regardless of its presence (or lack thereof) in the textbook or web site. Additionally, a portion of your grade depends on participation in in-class activities, such as laboratory exercises.
If you have problems with anything in the course, please come and see me during office hours, make an appointment to see me at some other time, or send email. I want to make you a success in this course. If you have trouble with the assignments, see me before they are due. If you fall behind, it will be difficult to catch up.
| Date | Topics | Reading | Assignment |
| 9/29 | Welcome; Linux, development tools, & C++; software engineering principles | Carrano, Ch. 1, App. A | Program 1 assigned |
| 10/4 | Recursion; Recurrence relations & induction proofs | Carrano, Ch. 2, App. D; Rosen, Ch. 5 | Program 1 peer design review |
| 10/6 | Recursion as a problem solving technique | Carrano, Ch. 5 | Program 2 assigned; Written HW 1 assigned |
| 10/11 | Abstraction & OOP in C++ | Carrano, Ch. 3 | Program 1 due |
| 10/13 | Linked list implementation & memory management | Carrano, Ch. 4 | Program 2 peer design review; Written HW 1 due |
| 10/18 | Stacks: implementation and applications | Carrano, Ch. 6 | Program 3 assigned |
| 10/20 | Queues: implementation and applications | Carrano, Ch. 7 | Program 2 due |
| 10/25 | C++ objects, classes, and OO design | Carrano, Ch. 8 | Program 3 peer design review |
| 10/27 | Algorithm analysis | Carrano, § 9.1; Rosen, Ch. 3 | Written HW 2 assigned |
| 11/1 | Midterm review |
| Program 3 due |
| 11/3 | Midterm |
|
|
| 11/8 | Sorting | Carrano, § 9.2 | Program 4 assigned; Written HW 2 due |
| 11/10 | Sorting, cont’d | Carrano, § 9.2 |
|
| 11/15 | Propositional & predicate logic | Rosen, Ch. 1 | Program 4 peer design review; Written HW 3 assigned |
| 11/17 | Logic, cont’d | Rosen, Ch. 1 |
|
| 11/22 | Trees | Carrano, Ch. 10 | Program 4 due; Program 5 assigned; Written HW 3 due |
| 11/24 | Thanksgiving |
|
|
| 11/29 | Trees, cont’d | Carrano, Ch. 10 | Program 5 peer design review |
| 12/1 | Mathematical foundations | Rosen, Ch. 2 | Written HW 4 assigned |
| 12/6 | Math foundations, cont’d | Rosen, Ch. 2 | Program 5 due; Written HW 4 due |
| 12/8 | Course wrap-up |
|
|
| 12/13 | Final |
|
|
“If builders built buildings the way programmers wrote programs, then the first woodpecker to come along would destroy civilization.”
“If cars had followed the same developmental path as computers, a Rolls Royce would cost $100, get a million miles per gallon, and explode once a year, killing everyone inside.”
The two quotes above vividly describe the contrast between the typical practice of “programming” and that of other engineering disciplines. What is the difference? Historically, programming was not practiced as an engineering discipline. Practitioners took pride in their ability to hack out solutions. Oftimes, the more elegant solutions were, the harder they were to understand. “If it was hard to write, it should be hard to understand!” was the hacker’s motto.
Much has changed in the last couple decades, and one of those changes has been the upgrading of Computer Science education to match that of other engineering subjects. Thus, programming becomes Software Engineering (SE), and Software Engineers spend considerable time and effort on activities other than programming. At first blush, this may seem a waste of time. However, nobody would think that of the time spent by a civil engineer designing a building, or an electrical engineer designing a computer. In those other fields, there is a big distinction made between design and construction, with the latter often not considered engineering per se. The same has been increasingly true of software engineering, with software design being engineering and programming becoming coding.
The reasons for this are typically couched in terms of dollars, because the largest consumers of software engineers have been corporations, and it is most convenient for them to convert everything into units of money. However, almost all of the arguments made in favor of SE for the corporate environment also apply elsewhere.
The key to to understanding the advantage of the “design first” approach is to consider the entire software life cycle. When one writes code without designing it ahead of time (and therefore without any design documents produced), one is making (at least) all of the following assumptions:
If any of these assumptions are violated, then a design is necessary before any code is written (except perhaps for some prototyping, though there should still be informal designs done for those):
“A physician, a civil engineer, and a computer scientist were arguing
about what was the oldest profession in the world. The physician
remarked, ‘Well, in the Bible, it says that God created Eve from a
rib taken out of Adam. This clearly required surgery, and so I can
rightly claim that mine is the oldest profession in the world.’ The
civil engineer interrupted, and said, ‘But even earlier in the book
of Genesis, it states that God created the order of the heavens and
the earth out of chaos. This was the first and certainly the most
spectacular application of civil engineering. Therefore, fair doctor,
you are wrong: mine is the oldest profession in the world.’ The
computer scientist leaned back in her chair, smiled, and then said
confidently, ‘Ah, but who do you think created the chaos?’ ”
—
Grady
Booch,
Object-Oriented
Analysis
and
Design
This involves two parts: determination of the desired system functionality (specification) and the actual design. The former involves major interaction with the end-users; the latter brings to bear CS knowledge (theory, algorithms, practice) and software engineering technique. We go to this trouble for one simple reason: software systems are the most complex objects routinely constructed by people. A thorough, careful design and development process is the only practical way to manage this complexity. As Grady Booch says, “We observe that this inherent complexity derives from four elements: the complexity of the problem domain, the difficulty of managing the development process, the flexibility possible through software, and the problems of characterizing the behavior of discrete systems.”
Your documentation should be written so that someone else could take your specification and design the program, or your design and understand how your program works (including be able to modify your code).
For this class, you must write a problem specification and a program design. These will be used in the peer design review in class, and then handed in to receive credit. The process for conducting a peer design review will be covered in class; below I present a description of what your documentation should contain. Note that, as you read the Carrano textbook, this will seem very much like the denigrated waterfall software development method. This mostly reflects the fact that I am asking you to design first and check your design in class; it doesn’t mean that you won’t be iterating back and forth among analysis, design, implementation, and test. In fact, I strongly suggest that you at least take an incremental approach to implementation, so that you always have working code that does something.
The specification makes the problem statement precise and detailed. There should be nothing ambiguous or unknown left after the specification. Your specification should not just be a regurgitation of the assignment statement; they are purposely left vague and incomplete so as to require you to go through a process of refining precisely what the program should do. Your specification should reflect the results of this phase of your homework, and your grade for the homework will be, in part, determined by the specification. Divide your specification into the following sections:
The program design document is a complete and unambiguous description of how the program will work. It is language-independent, and includes a description of the overall structure of your code (classes and objects, calling and called functions and their interfaces). This should be the result of your own design process performed prior to the start of coding, rather than something done after you’ve written the program. I expect two main parts to your design: structure charts and simple class diagrams.
A structure chart graphically displays the hierarchical algorithmic structure of a system. If we were taking a pure object-oriented approach in this course, then we would dispense with structure charts. In that case, our systems’ basic organizing principle wouldn’t be a hierarchy of function calls, so structure charts wouldn’t be useful. However, in this course, we are merely using classes and objects to encapsulate abstract data types, and so our programs are mainly hierarchical in nature. The figure below presents a simple structure chart.
You can think of a structure chart as a map of your program. It shows how the program is broken into (sub)procedures, which functions call which, and the data they pass back and forth. Each function in your program should be represented in the chart by a rectangle with the function name inside (if the function is a method of some class, then use the C++ notation className::functionName). Lines connect calling procedures to called ones, with arrows indicating the direction of the call. If a procedure is recursive (calls itself), there is no need to indicate this in the structure chart. These lines are annotated to indicate parameters passed and values returned as follows:
You use structure charts in your design by starting with the entire problem to solve — this is the top box of your structure chart. Break this problem into major subproblems, and write down how you could solve the entire problem if you could solve the subproblems. This gives you enough information to add the subproblems to the chart as procedures, with properly annotated calls. Repeat this process for each subproblem until you’ve reached problems that you can solve directly. The resulting structure chart and notes is your structured design. Your design documentation should include both structure charts and the pseudocode you wrote during the above decomposition process.
Class diagrams define the static structure of an object-oriented system (systems with a number of interacting objects will also have a dynamic, run-time structure, but we will leave this to CSS343 or later). The figure below shows two versions of a simplified UML (Unified Modeling Language) icon for a class: one with detailed information (left) and one without (right). You should only draw one of these in any one diagram; for this course, that will always be the one on the left. A class icon is a rectangle with the class name inside (an icon for an object has the name underlined, so don’t underline the class name). The detailed view is broken into three parts:
As you might guess, UML supports more complex specifications for individual classes, as well as ways of specifying relationships among classes. We will incorporate these into our documentation as the class progresses (so, you have something to look forward to).
You are expected to adhere to certain basic principles of good design:
Coding standards means writing code that is easily understood and including comments that clearly document its function. Code clarity is aided by consistent and useful indentation, identifiers with descriptive names and naming conventions, and the use of special language constructs, such as const and typedef, which you will learn this quarter. More precisely, our course coding standards are:
C++ STL include files should be included like #include <vector>, rather than #include <vector.h>. Similarly, C includes should be as #include <cmath>, not #include <math.h>. It is acceptable to use the directive using namespace std;.
You are also expected to avoid global variables (and you are required to justify their use if you do need to use them) and will not be permitted to use gotos in this class.