Computer Science 172
Introduction to Algorithms and Data Structures

Dr. Stephen Bloch
office 113A Alumnæ Hall
phone 877-4483
Web page
Class Web page
office hours 11:00 AM-2:00 PM Mondays,
3:00-4:00 PM Tuesdays & Thursdays,
10:00 AM-1:00 PM Wednesdays

August 23, 2006

1  Who Should Take This Course

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.

2  What You can Expect to Get from This Course

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:

2.1  Java language goals

By the end of this course, you should

2.2  Object-oriented programming goals

By the end of this course, you should

2.3  Algorithm and data structures goals

By the end of this course, you should

3  Texts

This semester we'll use two textbooks:

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..

4  Topics

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.

5  Program standards

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.

6  Grading

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:

Programming homework

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.

Lab exercises

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.

Final exam

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.

Log or diary

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.

Brownie points
This is my purely subjective impression of how seriously you're taking this course. Did you ask and answer good questions in class? Did you help your classmates learn (without stepping over the line into "doing their work for them")? When you were confused, did you come to my office and ask me for help? Did you attend class and pay attention? Did you take the opportunity to learn new things and challenge yourself, or did you do the minimum to get by?

7  Ethics

The Adelphi University Code of Ethics applies to this course; look it up on the Web at .

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.

8  Schedule

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!

Last modified: Wednesday, August 23rd, 2006 1:12:10pm