Course information

Instructor: Ben Allen (please call me Ben)

Credit hours: 4

Meeting time: Class meets on Zoom from 6:30 to 9:20 on Tuesdays and Thursdays

Class is structured as follows:

• About 1 hour lecture (6:30 to 7:30)
• About 30 minutes lab (7:30 to 8:00)
• About 30 minutes lecture (8:00  to 8:30)
• About 1 hour lab (8:30 to 9:20)

It is likely that some days lectures / question and answer will run over; in this case, I will aim to have a shorter lecture and longer lab session the following class.

Attendance: Attendance during course time is VERY STRONGLY SUGGESTED unless you have a very good reason (work conflicts, you’re on another continent and class meets in the middle of the night for you). In my experience, especially with this course, the only way to succeed is to work at it every day.

Lecture videos: All lecture videos will be posted to the course Canvas site.

Course overview

Data Structures and Algorithms introduces students to effective strategies for developing efficient methods of solving problems, techniques (both experimental and mathematical) for analyzing algorithm efficiency, and gives students an opportunity to develop an intuition for which strategies are effective in different contexts.

 

We will use object-oriented programming as a tool for developing and understanding algorithms. This course is intended for students who are comfortable programming in Java (or a similar language). It is absolutely not intended for students without experience doing object-oriented programming.

 

Core topics include:

• Abstraction – learning programming techniques to separate data structure interfaces from their implementations.
• Practical implementation of fundamental data structures (linked lists, hash tables, binary search trees, heaps)
• Canonical sorting and searching algorithms
• Graph traversal algorithms

 

Although we will use the Java programming language (or a small subset of the Java programming language) to implement data structures and algorithms, this is not primarily a class about Java. The concepts you learn in this class will be used throughout your career as a computer scientist, regardless of what languages you work in or tools you use.

 

Student Learning Outcomes

Official Peralta Community College District SLOs for this course:

 

After successfully completing this course, students will be able to:

1. Use object-oriented program design
2. Learn abstract data structures, analyze the complexity of algorithms, and design and implement efficient code.
3. Describe the most commonly used algorithms for sorting and searching, including balanced search trees and hash tables, minimum spanning trees, and shortest paths.
4. Describe the basic string operations, including sorting, searching, regular expression, and string compression.

 Classroom Learning Objectives: To achieve the SLOs, students will engage in activities that encourage them to do the following:

1. Analyze and solve complex problems by breaking down into smaller modules using object-oriented techniques.
2. Analyze the complexity of algorithms, and design and implement efficient code.
3. Understand the most commonly used algorithms for sorting, searching, graph traversals, and string manipulations.
4. Write code using good coding practices

 

Communication, office hours, Discord

My formal office hours this semester are from 9:00 AM to 1:00 PM on Fridays. I will be holding office hours on the class Discord server in the #office-hours channel.

This is the invite link to the Discord.

If you do not already have Discord installed on your computer or mobile device, you can get it here.

I will frequently be on the Discord outside my office hour times – it’s where I coordinate with the TAs – but my scheduled office hours are the only time I can guarantee that I will be online and available.

The Discord will be open 24/7. Feel free to hang out there to discuss assignments and class material, but please keep discussions in the class channels more or less on topic -- it's not helpful to your classmates if the class channels are filled up with talk about videogames, movies, and memes.

There are a couple of channels available for off-topic conversation:

• #social, for general discussion
• #pets, for pictures and discussion related to adorable animals

 

Regardless of the channel you're in, please keep your conversations friendly and inclusive. I will be very annoyed indeed if students on the Discord (or in other class forums) use language or behavior that alienates or excludes your fellow classmates. VERY. ANNOYED. INDEED.

 

Email

I will also be available via email at benjaminallen@peralta.edu. I will aim to respond to emails within 24 hours of the time they are sent. For emails sent over the weekend, I will aim to respond by the following Monday.

 

Required text

Algorithms, Robert Sedgewick and Kevin Wayne - 4th edition (2011)

The supplementary book site contains many resources that I strongly recommend you explore. Most notably, it contains the libraries used in many of the assignments, and also complete lectures by the author of the textbook.

I will be referring to the 4th edition in my course materials. I recognize that most students have cost concerns, and you are welcome to buy an earlier edition, but I can't make any guarantees about how well it will match the material I'm covering. 

Do note that the structure of the class follows along very closely with the structure of Sedgewick's book. It is absolutely necessary to acquire a copy to be successful in the class.

(Strongly) Recommended text

I will refer extensively to The Algorithm Design Manual by Steven Skiena. I very strongly recommend picking up a copy of this book, both because it will be helpful for the class – I’ll be using it as a source for many of the assignments – and because it will be helpful in your career as a computer scientist. It’s relatively comprehensive and, unlike many computer science texts, it’s actually fun to read. There are very few textbooks that I keep on my desk while doing my own projects. This is one of them.

Additional text for the curious

Introduction to Algorithms by Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. This book, generally known as CLRS after the initials of its authors, is far and away the most comprehensive and rigorous text for algorithms and data structures. You will without a doubt use it in your future computer science classes. However, it will be a slog if you don't have a solid mathematical foundation (particularly in statistics and discrete math)

Required software

We will use IntelliJ Idea for this class. Use the free community edition – basically the only reason to pay for IntelliJ is if you are a large corporation.

If you already have extensive experience with another Java IDE, or if you’re experienced with developing Java programs from the command line, it is perfectly fine for you to continue using your preferred environment. However, I won’t be able to provide extensive technical support for anything but IntelliJ or the command line.

 

Some assignments will require knowing how to navigate a Unix system. A reference will be provided.

Assignments and grading

Homework:

There are four types of assignment in this class:

1. Minor projects (these are given in standard, non-bold text in the planned course schedule below). These are problem sets and relatively smaller programs, meant to demonstrate your understanding of particular algorithms.
2. Major projects (in bold text below). These are larger programming problems meant to demonstrate your ability to reason about what algorithms to use to implement meaningful programs. Each of these is worth about twice as much as the minor projects.
3. Design documents. These are submitted before implementing certain major projects, and are intended to be used to verify that your proposed strategy for solving the problem will work. You may work on design documents in teams of two. These are worth relatively few points, but are necessary for completing major projects.
4. Études (sorry for the pretentious name). There’s only a couple of these: they’re short exercises meant to demonstrate your ability to use the Java language.

About 2/3rds of the total points in this class comes from the major projects.

Note that there are no tests or quizzes in this class.

 

Late assignment policy:

Projects turned in on time get a 2% on-time bonus. Projects turned in within three days of the due date get full credit. Projects turned in more than three days after the due date but less than a week after the due date get a 10% penalty. Projects turned in more than a week late get a 20% penalty. Projects turned in more than two weeks late will receive no credit.

 

Note that this is somewhat tighter than my standard late policy. This is because, even more than in other CS classes, everything in this class builds off of the material before it. Falling behind is a terrible idea.

 

Late design documents will not be accepted. Late problems sets will only be accepted before I give the answers in class, which will generally be about a week after they’re assigned.

 

I will be grading assignments in the order in which they arrive, and so if you turn them in late do not expect timely feedback.

 

Extensions:

That said: Our students come from varied backgrounds and can have widely varying situations and necessities. And, needless to say, we are currently experiencing a global pandemic. If you have any unforeseen or extenuating circumstances that arise during the course and that may prevent you from completing course material in a timely fashion, please reach out to me so that we can discuss your situation. If you need an extension on a one of the major assignments, PLEASE ASK WELL IN ADVANCE. I won't respond to requests for extensions the night before the assignment is due. (I'm not kidding here -- I'll just ignore them.)

 

Accommodations

 

If you are a student with a disability, please let me know about your needed accommodations immediately. If you are a new student and need evaluation or verification of your needed accommodations, please contact BCC’s Programs and Services for Students with Disabilities.

 

 

Academic dishonesty and cheating

 

Please carefully read these policies and contact me if something is unclear.

 

• It is reasonable (and a good idea) to discuss your ideas with your classmates. CS class study groups are where startups and worker-owned code co-ops are born.
• It is NOT reasonable to directly copy solutions from your classmates. In fact, I recommend that you avoid looking directly at each others’ code, in order to avoid accidentally setting off the plagiarism detector. Talk about how your code works, think up strategies to improve your code, but don’t show your code.
• If you must use a short snippet of code from the internet – one or two lines at most – include a comment indicating where you got it from and how it works. I reserve the right to ask questions to make sure you understand the code you’ve used.
• That said, I don’t recommend using stackoverflow (and other similar question-and-answer sites) as references. Generally the answers they give to questions are geared toward the need of working professional programmers, and involve portions of the Java language that we will not cover in this class.
• If you directly copy someone else’s code, the penalties will be severe. You will receive at minimum an F on the assignment.
• It is a very bad idea to copy someone else’s code and then make small tweaks to make it seem like original work. To make this type of plagiarism very difficult to do, I will be using a plagiarism detector based on the algorithm discussed in this paper by CS professor Alex Aiken (formerly at UC Berkeley, now at Stanford).
• If you are considering copying work from other students or the Internet, please read that paper (it’s actually super interesting) and revise your program to evade the plagiarism-detection methods it uses.

 

Here is a week-by-week schedule for the class. Details will likely change over the course of the semester.