Data Structures and Algorithms

Sarah Lawrence College
Spring 2022


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

Big Java: Early Objects, 5th Edition
by Cay Horstmann

Lab Sessions

Each Wednesday morning from 9:30-10:55am we will have a lab session in Ilchman Science Center 104. The lab sessions are mandatory. The purpose of the labs is to give you time for hands-on, structured practice with Java, and the opportunity to ask questions and receive individualized help. New material will usually not be introduced during lab. At the beginning of each lab session, 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 should be sure to collaborate equally on writing, testing, and debugging your code as a team. The lab exercises will typically be due the following week as part of your homework assignment.

Attendance Policy

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 can be difficult. At the beginning of each class, I will pass around an attendance sheet, which you should make sure to sign. If you arrive late and forget to sign the sheet, you will most likely be counted as absent that day. Although I realize that missing class sometimes cannot be avoided, your cumulative attendance record will influence your final course grade, and missing more than 3 classes or 1 lab session will put your grade in serious jeopardy. If you are unable to attend class or lab, please contact me about it as soon as possible. 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 evaluated 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 Evaluation Scale

Homework assignments are evaluated on both the functionality and style of your code, according to the following rubric. To receive a ☆, your code must not only work perfectly, it must also be logically well-organized and easy to read (see the above stylistic guidelines).

Work of excellent quality that clearly meets or exceeds all of the assignment expectations. All programs work correctly on all of the input data, and are written in a clear, easy-to-read style.
✓+ Work of very good quality that meets most of the assignment expectations. Programs work correctly or mostly correctly for most of the input data, though some programs may have a few minor deficiencies or stylistic problems.
Work of satisfactory quality that meets some of the assignment expectations and reflects a good effort overall, despite some deficiencies. Some programs work correctly or mostly correctly for most of the input data, but may have significant stylistic problems or other shortcomings.
✓− Work of subpar quality that falls short of assignment expectations and needs improvement. 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.
Work of poor quality that exhibits severe problems, reflecting minimal effort or understanding. Many 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. 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 Java 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 contact 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. Contact 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 code won't work, when just a few minutes is often all it takes to track down the problem together. I'll also be happy to answer questions over email or schedule a meeting with you on Zoom if that is more convenient.

How to Succeed in This Course

Accommodations

If you have a disability that may interfere with your ability to participate in the activities, coursework, or assessment of the objectives of this course, or any of your other courses, you may be entitled to reasonable accommodations. Please contact Polly Waldman, Associate Dean of Studies and Disabilities Services located in Westlands 116. You may also call Disability Services at 914-395-2235 or email pwaldman at sarahlawrence.edu. Under the Americans with Disabilities Act and Section 504 of the Vocational Rehabilitation Act of 1973, all students, with or without disabilities, are entitled to equal access to the programs and activities of Sarah Lawrence College and the College will make reasonable accommodations when appropriate and necessary.

Collaboration Policy

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, code, or solutions with others, or to make use of another student's code or solutions obtained via email, the Internet, or any other means of communication. I can almost always tell when two different programs derive from the same original source code, even if cosmetic changes have been made to it. The code you hand in must have been written by you from scratch, with the following permitted exceptions: code provided in class by me, code from the textbook, or code developed together with a partner if you are collaborating on a lab or project with my knowledge. In this case, you and your partner may freely exchange code developed as a team, and are jointly responsible for the work submitted. Under no circumstances may you hand in work under your own name that was done by someone other than yourself or your partner.

In all cases, if you make use of any code that was written by someone else in your assignment, including your partner, you must clearly acknowledge this in your code. This also goes for any help obtained via the Internet. When in doubt, credit the people or sources from whom you got help. If you are ever unsure about what constitutes acceptable collaboration, just ask. You are also responsible for carefully reading the College's official Policy on Academic Integrity in your SLC 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!