Data Structures and Algorithms

Sarah Lawrence College
Spring 2020


Course Description

In this course, we will study a variety of data structures and algorithms that are important for the design of sophisticated computer programs, along with techniques for managing program complexity. We will use Java, a strongly typed, object-oriented programming language, throughout the course. Topics covered will include types and polymorphism, arrays, linked lists, stacks, queues, priority queues, heaps, dictionaries, balanced trees, and graphs, as well as several important algorithms for sorting, searching, and manipulating structured data. We will also study some mathematical techniques for analyzing the efficiency of algorithms. The central theme tying all of these topics together is the idea of abstraction, and the related notions of information hiding and encapsulation, which we will emphasize throughout the course. Weekly lab sessions will reinforce the concepts covered in class through extensive hands-on practice at the computer.

Intermediate. Students should have at least one semester of programming experience in an object-oriented language such as Python, Java, or C++.

Instructor

Prof. Jim Marshall
Office: Ilchman Science Center 100
Phone: 2673 (from off campus: 914-395-2673)
Email: j + my last name + @sarahlawrence.edu

Class Meeting Time

Textbook

OR
Big Java: Early Objects, 7th edition
by Cay Horstmann
  Big Java: Early Objects, 5th edition
by Cay Horstmann

Lab Sessions

We will have lab sessions on Thursdays from 9:30-10:55am in Ilchman Science Center 104. The purpose of the labs is to give you more time for hands-on practice with Java, in order to reinforce the concepts covered in class that week. New material will usually not be introduced during lab. At the beginning of each lab, I will hand out a set of programming exercises for you to work on individually, or with a partner. If you work with a partner, you both should collaborate equally on writing, testing, and debugging your code as a team. You must also take turns typing at the keyboard (this is very important). The lab exercises will typically be due as part of your homework assignment for the following week.

Attendance

On-time attendance is required and expected for all class meetings and lab sessions. Given the fast-paced, cumulative nature of the course material, students who miss class risk quickly falling behind, and catching up is difficult. Although I realize that missing class sometimes cannot be avoided, you may receive reduced course credit if you miss more than 2 classes or 1 lab session, for any reason. If you are unable to attend class or lab due to illness, please contact me about it as soon as possible. If you must miss class for any other reason, please let me know well in advance. No student will be admitted to the course after the add/drop period ends.

Email

I will often send out announcements to the class through email, so you are required to check your Sarah Lawrence email account at least once per day. I will use your @gm.slc.edu address because it is reliable and easy to remember. You should also check the course web pages frequently for code examples discussed in class, and for the homework assignments. I will be happy to answer your questions by email and will try to respond as quickly as possible to messages that pertain to the course.

Homework Assignments

Good Programming Style

Your programs will be graded on both functionality and style. As expert programmers know, programming is about more than just getting your code to run correctly on a computer. It is a highly creative activity akin to an art form, which relies as much on a sense of aesthetics and style as on technical mastery of the programming language. Programs should be written primarily for other programmers to read and understand, and only incidentally for machines to execute. Thus it is very important for you to develop a clear and consistent programming style, making good use of comments, white space, and well-chosen variable names. Your code should follow these general stylistic guidelines:

Homework Grading Scale

Homework grades are based on both functionality and style, according to the following scale. Be aware that even if your code works correctly, it could still get a B due to stylistic problems. In order to get an A, your code must work completely correctly, be well-organized and easy to read, and conform to the stylistic guidelines given above.

A Work of excellent quality that clearly meets or exceeds all of the expectations of the assignment. All programs work correctly on all of the input data, and are well-written, exhibiting good programming style. A job well done.
B Work of good quality that meets most of the expectations of the assignment in a satisfactory way. Programs work correctly or mostly correctly for most of the input data. Some programs may have minor stylistic problems.
C Work of subpar quality that falls short of expectations. Some programs have serious deficiencies, and work incorrectly for a significant portion of the input data. Nevertheless, the work shows some degree of effort and understanding.
D Work of poor quality that exhibits many severe deficiencies, reflecting minimal effort and understanding. Programs crash or work incorrectly for most or all of the input data.

Conference Work

Projects will be due the last week of the semester. During that week, everyone will give a short presentation to the class on their conference work. You will also be required to turn in a short written project report. However, if you choose to present your project at the SLC Science/Math Poster Session, which will be held in May (more details will be provided later), you do not have to turn in a project writeup. There are three options available for your conference work:

  1. Your own project idea. If you already have a clear idea of what you would like to do, that's great. I am open to almost any computer science topic, although preferably one related to the course material.

  2. A programming project. This would involve developing a sizable program over the course of the semester to perform some task. Your program would be expected to incorporate at least some of the data structures covered in class. There are many possibilities here: games, simulators, database applications, web applications, graphics, etc. Your project could be a stand-alone system, or could make use of Java's standard libraries or other third-party libraries. The project goal would be a working program, with separate well-written documentation, that you would demo for the class.

  3. A research paper. This option would involve researching some topic related to computer science in depth, by developing a bibliography of books, articles, web sites, etc. and doing extensive background reading. The project goal would be a traditional 15-20 page, well-written conference paper on the topic. If you prefer, you could present your work in the form of a web site instead of (or in addition to) a paper. In this case, the same standards for good writing would apply to your web site.

Getting Help

At times you may find some of the course material to be quite daunting. But don't be discouraged! If you find it difficult, most likely so does the rest of the class. This is just a normal part of the process of learning to program. You are strongly encouraged to come see me as soon as possible whenever you are having difficulty with the material. If you are confused about something, don't stay that way! Staying confused will only make things worse later. Come talk to me as soon as possible so that we can clear up the problem. There is no point in staring at the computer screen for hours trying to figure out why your program won't work, when just a few minutes is usually all it takes to track down the problem together. I'll be more than happy to schedule an appointment. Ask me about it in class, email me, or leave a message on my voicemail. You can also try to catch me on the fly, though I can't always guarantee that I'll have time to meet with you right then.

Tutoring Hours

Our lab assistants Sarah Dennis and Rachel Williams will be available this semester for informal help and tutoring with Java programming, according to the following schedule. This service is available on a walk-in basis in Science 104 (our computer lab), with no appointment necessary:

For the remainder of Spring 2020: To attend an online tutoring session, go to the Mathematics Resource Center page in MySLC.

How to Succeed in This Course

Academic Honesty

The highest level of academic integrity is expected of every student. You are strongly encouraged to discuss ideas and approaches to solving problems, on a general level, with your fellow classmates, but you are not allowed to share your program files or solutions with others. You may, however, share code with your lab or homework partner if you are working together on an assignment. The code you hand in must be exclusively your own work, with the following permitted exceptions: code provided in class by me, code from the textbook, and code worked on with a partner. Effective learning is compromised when this is not the case.

When in doubt, credit the people or sources from whom you got help. This also goes for any help obtained via the internet. If you are ever unsure about what constitutes acceptable collaboration, just ask. Here are some example scenarios of acceptable and unacceptable collaboration. You are also responsible for carefully reading the College's official Policy on Academic Integrity in your Student Handbook. Failure to abide by these rules is considered plagiarism, and will result in severe penalties, including possible failure in the course. Please do not put me, yourself, or anyone else in this unpleasant situation!