August 23, 2006
This course is the second half of Adelphi's first-year programming sequence for computer science majors and minors. It assumes you have taken the first half, CSC 171, or the equivalent, partly or entirely in Java. If your first programming class was at another school, or you don't know any Java, talk to me and we'll work it out. If you've never taken a programming course at all, you should take either CSC 160 ("A First Course in Computer Programming") or CSC 171 first; talk to me to choose between those.
If you want to learn how to use a computer (for word processing, spreadsheets, databases, Web browsing, email, etc.) and perhaps create your own Web page, but not write full computer programs yourself, you should probably take CSC 170, "Introduction to Computers and Their Applications", instead.
This is a 4-credit course, meeting for 2.5 hours of lecture and 2.5 hours of lab every week; according to New York State standards, you should therefore budget an additional 5 hours per week for homework and reading. I'm not kidding.
Obviously, you'll learn some more Java language features and become more fluent in the ones you already know. More importantly, you'll gain experience at converting an English-language problem description into an object-oriented design (what classes will you need, what fields and methods should each class provide, etc.) and then into a complete, working Java program. Finally, since the title of the course is "Introduction to Algorithms and Data Structures", you'll learn the meanings of these two words, and gain hands-on experience with a number of the most common algorithms and data structures.
So that's three broad goals: learn more Java, learn more OOP, and learn about algorithms and data structures. Of these, I consider the Java material the least important, since it'll change with each new version of Java and doesn't help you program in other languages. What you learn about OOP, algorithms, and data structures is more valuable because it'll still be true ten or twenty years from now, no matter what language you're writing in.
Let's get a bit more specific:
By the end of this course, you should
be comfortable using a program development environment (like BlueJ or Eclipse) to carry out a design-code-test-debug cycle
Know the Java syntax for defining and using classes, methods, and variables (instance, parameter, and local), and for the declaration, assignment, "if", "return", "while", "for", "do...while", "switch", "break", and "continue"
Know the Java syntax for defining, initializing, and using one-dimensional and two-dimensional arrays (both rectangular and "ragged")
Know how and when to "cast" an object to a different type
Be able to parse algebraic expressions in Java and ordinary algebra by hand, recognize which operator governs which sub-expressions, and infer types and values of expressions
Be able to perform input and output involving GUI, console, file, and network
Be able to trace the execution of a program by hand, in particular the values of variables at different times and in different function invocations
Internalize habits of clear coding: good choices of names for variables, methods, and classes; indentation and blank space; commenting; named constants; code re-use and factoring to avoid duplicate code
Design and implement graphical user interfaces, including coordinate-based drawing, GUI components, event-handling, and layout managers, organizing such programs using the model/view/controller pattern
Know standard coding patterns for common low-level tasks such as swapping the values of two variables, choosing among several alternatives, searching a list or array for a specified element, and combining selected elements of a list or array
Understand limits on the precision and range of numbers stored in a computer; choose appropriately among "int", "double", "long", "BigInteger", etc. for a given task.
Be able to define new classes from old ones using both inheritance and composition, and know when to use which
Be able to throw, catch, and define exceptions
Use Java packages correctly and appropriately
Use inner classes both for information-hiding and to effectively "pass functions as parameters"
Use standard Java Collection classes and choose the right one for a particular application
By the end of this course, you should
Be able to read a problem specification, abstract away inessential details, and identify important types, relationships, and operations
Be able to plan the development of a complex program as an incremental sequence of testable versions
Design methods and classes to be easily re-used and subclassed without modification, and enhanced without breaking what already works. (For example, each function should do one coherent task; avoid mixing computation and I/O in the same function.)
Be familiar with the notion of Design Patterns, and with specific patterns such as read-only fields, singleton types, adapters, decorators, initialize-on-demand, factory methods, mixins, wrapper classes, skeletal implementations, safe enumerations, etc.
Follow step-by-step recipes for designing methods, classes, and groups of related classes
Choose and use appropriate test cases at every level of a program; test-driven development, bottom-up testing and debugging
By the end of this course, you should
for each of several common data structures (e.g. lists, stacks, queues, sets, binary and N-ary trees, dictionaries, priority queues, heaps), be able to implement the data structure with its most important operations, and discuss the advantages and disadvantages of this data structure
for each of several common searching and sorting algorithms (e.g. linear search, binary search, insertion sort, selection sort, quick sort, merge sort, heap sort, tree sort), be able to implement the algorithm, simulate it on paper, and discuss its efficiency as a function of problem size
understand big-O notation for algorithm efficiency; be able to put exponential, linear, logarithmic, quadratic, and other similar efficiency classes in their correct order
This semester we'll use two textbooks:
Java Concepts, 4th edition, by Cay Horstmann. Most of the reading assignments, and some of the homework, will be from this book. Technically, this is sold as a first-semester Java programming book, but I like its approach, so we'll go through the early chapters quickly and spend more time on the later chapters, which most first-semester courses don't get to.
Watts Humphrey's Introduction to the Personal Software Process. Using exercises in this book, you'll study your own programming style and learn to predict how long you'll take to accomplish a specified programming task, as well as to budget your time so you finish each program without staying up until 3 AM the night before it's due. I won't give specific reading assignments in this book, but expect you to finish it on your own by the end of the semester. Each homework assignment you turn in should be accompanied by various work logs, described in the book (more details below under "Program Standards").
The reading assignments are an important part of the course. If you're going to pay $50 or more for a textbook, you might as well get your money's worth by reading it. We'll go through almost all of the Horstmann book and the Humphrey book, so make time in your weekly schedule for at least fifty pages a week.
You are responsible for everything in the reading assignments, whether or not I discuss it in a lecture. You are also responsible for checking my class Web page and Blackboard at least once a week or so for assignments, corrections to assignments, solutions to assignments, etc..
The students in this class studied CS1 with different instructors, in different languages, at different colleges, covering different topics in different orders, so we'll take the first few weeks to get everyone caught up to what their classmates have already learned. We'll review the notions of "data type", "variable", "method", "class", and "field" (aka "instance variable"). We'll discuss how to call a method, declare and assign variables, write classes and methods, do simple text input and output, display graphics, write Boolean expressions, conditionals, and loops, and use arrays and ArrayLists for storing large numbers of similar data. This will be a lot of reading -- 300 pages in less than a month -- but much of it will be review.
In late September we'll slow down a bit and discuss software-engineering issues: how to design a class, and testing and debugging. We'll discuss how to effectively use Java's polymorphism and inheritance capabilities, which some but not all of you have used. We'll apply these techniques to interactive graphical user interfaces, files, Internet connections, and linked lists. This should take us through October.
In November, we'll slow down still more to discuss recursion, sorting and searching algorithms, and a number of important data structures with their associated algorithms: lists, stacks, queues, sets, maps, hash tables, trees, priority queues, and heaps, which will take us through the end of the semester.
What distinguises a "good program" from a "bad program"? Obviously, a good program has to work correctly and reliably -- a difficult goal in itself, as we'll see. But this is far from enough. In practice, very few programs are written once, used for a while, and discarded: much more often, a program is used until the need for it changes, the program is modified (often by a different programmer) to handle the new requirements, the modified program is used for a while, and the cycle repeats. Thus a "good program" must be not only correct the first time around, but structured in such a way that it can easily be modified to accomodate likely changes in requirements. To get across the point of modifiability, I may occasionally change the assignment slightly on the day that it's due. So whenever you get an assignment, you should immediately start thinking "how is Dr. Bloch likely to change this at the last minute?" and prepare for such a change. If implementing the change takes you an hour or more, you didn't design the program well for modifiability.
Another thing Real Programmers have to deal with is working in teams. Realistic programs are often too big to be written by one person in a reasonable time, so I want you to learn a technique called Pair Programming. It doesn't mean "you write part of the program and I'll write another part," although that's a technique you'll need to learn eventually too; it means two people working together on all of the program, typically using one workstation, taking turns with one typing and the other looking over the first one's shoulder. We'll discuss Pair Programming early in the semester, and I'll point you to some good articles about it.
There are other criteria for a "good" program, in addition to correctness and modifiability: fault-tolerance, efficiency, user-friendliness, etc. We'll start addressing all three of these criteria this semester, although there are more advanced courses in each.
Now for some practicalities.
To make it easier for me to grade your programs,
every program must contain, in the first few lines,
a comment indicating the name(s)
of the student(s) working on it, the course number (CSC 172),
and which assignment it is.
Programs not containing
this information, clearly visible, will get a zero.
If you're turning in homework by e-mail, please put this same
information in the Subject: line as well, so it's easier for me to
file my e-mail correctly.
A program that hasn't been adequately tested is worthless. I expect you to choose, and write down, a good selection of test cases (along with the "correct" result of each one) for every function before you write its body. (One common way to do this in Java is with the JUnit package, which we'll discuss in lab.) Every program must be accompanied by a session log showing how the program works on test cases. (I'll show you how to get a session log using BlueJ.) Programs with inadequate or poorly-chosen test cases will lose points.
Every program must be adequately and accurately commented. Ideally, most of your code should be so easy to read that it doesn't need comments, but if there are non-obvious restrictions on the use of a particular variable or function, or non-obvious tricks in your algorithm, explain these.
Having done my share of programming, I know that sometimes you hit a brick wall and cannot get the thing to work for love or money. If this happens, turn in the program together with a description of how the program fails, what you've tried in your attempts to fix it, and how those attempts didn't succeed. You won't get full credit, but if I'm convinced that you're working on it diligently, you'll get some partial credit. Note that "how the program fails" does not mean saying "I got an error message": you need to tell me which error message you got, when you saw it, and what you think the error message means. Similarly, if the program fails by producing wrong answers, you need to tell me when it produces wrong answers (are they all wrong, or just in a few cases?), how they are wrong (e.g. are all the numbers consistently higher than you expected, are they the negatives of the correct answers, or are they all over the place with no apparent pattern?), and your speculations on how such an error might have arisen. I'm requiring all this not because I'm mean and horrible, but because by the time you've written all this down, you may have enough information to actually fix the problem, which is much better than turning it in incomplete.
I also expect you to keep track of the time you spend on various aspects of programming, how many and what kinds of defects you encounter, etc. For each assignment, I'll tell you which tracking information is required. The easiest way to turn in this information is through a collection of on-line PSP forms, which I'll show you how to use. Indeed, I recommend that while you're programming, you have a Web browser running the forms in the background, so you can easily record each defect and each block of time before you forget about it. Failure to turn in this tracking information will lower your grade for that assignment.
My most important job this semester is to help you learn to program well. A less important, less fun part of my job is to assign you a letter grade at the end of the semester, which somehow (despite being only a single letter) is supposed to indicate what you've learned and accomplished in fourteen weeks. But Adelphi and the State of New York require it, so here goes....
Your grade will be computed from several sources:
There will be 4-5 major programming assignments, to be turned in by e-mail, graded in detail and returned to you by e-mail. Within a week after I've returned the graded assignment, you may turn in a "second chance" version. Your original grade will be averaged together with 90% of the "second chance" grade, so if you've only made a small improvement, or if you got at least an 90% the first time around, resubmitting won't help your grade. Note also that the last assignment will be too close to the end of the semester to allow for a "second chance".
A major programming assignment turned in with a time stamp after midnight on the due date is late, and will receive partial credit depending on how late it is. Anything turned in after midnight, Thursday, Dec. 14 will be ignored so that I have time to finish grading homework before the final exam on the 19th.
There will be 28 lab sessions. In many of these sessions, I'll give you a small programming exercise, short enough that I think you can finish it during the lab. You'll either show these to me in lab, or turn them in to me by e-mail before midnight on the same day.
There may be a few brief (15-20-minute) quizzes, to be done on paper; I'll grade them and try to get them back to you at the next class meeting. They cannot be made up; if you're not there the day of a quiz, you have a zero on it.
There will be a two-hour final exam from 10:30-12:30 on Tuesday, Dec 19. It may include material from the whole semester, but will concentrate on the material discussed in November and December. The final exam must be taken at the scheduled time, unless arranged in advance or prevented by a documented medical or family emergency. If you have three or more exams scheduled on the same date, or a religious holiday that conflicts with an exam or assignment due date, please notify me in writing well in advance in order to receive due consideration.
I want you to keep a log or diary throughout the semester, and turn it in to me whenever you turn in a program. (A plain text file, or Word document, or Web page -- whatever format is comfortable for you, as long as I can read it. If you prefer paper, turn in a scan or photocopy so you can keep using it while I read and grade it.) Jot down difficulties you encounter with Java, with programs, with my lectures, and with programming partners. I particularly want to see your individual impressions of how Pair Programming is working: what did each partner bring to the project, what did each partner learn from the project, how did the partners work together in practice, etc. And I want to see how you think about and analyze problems.
The Adelphi University Code of Ethics applies to this course; look it up on
the Web at http://academics.adelphi.edu/policies/ethics.php .
Most homework assignments in this course involve writing, testing, and debugging a program. For many of these assignments, you are encouraged to work in teams of two students, switching teams from one assignment to the next; for other assignments, I may ask you to work individually.
It's hard to define what constitutes "cheating" in this sort of course. Students are encouraged to help one another with mechanical and linguistic difficulties ("how do I save this file?", "how do you declare a static instance variable?", etc.), regardless of whether they're on the same team, but designing, coding, testing, and debugging should be done by team members. It's remarkably easy for a professor to notice when three different teams have turned in nearly-identical programs; if that happens, I'll grade it once and divide the credit among the three, so the best any of them can hope for is 33%.
All work on the final exam must be entirely the work of the one person whose name is at the top of the page. If I have evidence that one student copied from another on an exam, both students will be penalized; see above.
This class meets every Tuesday and Thursday from 10:50 AM-12:05 PM (lecture, in Levermore 314) and every Tuesday and Thursday from 1:40-2:55 PM (lab, in Science 227). Our final exam will be from 10:30 AM-12:30 PM, in Levermore 314, on Tuesday, Dec. 19. If you have a problem with these scheduled dates and times, let me know at least two weeks in advance so we can make suitable arrangements.
All dates in the schedule are tentative, except those fixed by the University; if some topic listed here as taking one lecture in fact takes two lectures to cover adequately, or vice versa, the schedule will shift.
In the column marked "Reading", all page numbers are in the Horstmann book unless stated otherwise. Remember, I also expect you to read through the Humphrey book by the end of the semester.
I expect you to have read the reading assignments before the lecture that deals with that topic. This way I can concentrate my time on answering questions and clarifying subtle or difficult points in the textbook, rather than on reading the textbook to you, which will bore both of us. Please read ahead!
When I say "read" above, I mean an active process, involving not only the textbook but pencil, scratch paper, and a notebook for writing down key points. Finally, and perhaps most importantly, you'll need a computer for trying out the new ideas you find in your reading. Just as you cannot learn to drive a car or to cook just by reading about it, you cannot learn about programming just by reading about it. In short, every time you read about a new programming idea, try it!