Course: COS226
Instructor: Rusinkiewicz
F 2015

Description of Course Goals and Curriculum

This course surveys the most important algorithms and data structures in use on computers today. Particular emphasis is given to algorithms for sorting, searching, and string processing. Fundamental algorithms in a number of other areas are covered as well, including geometric algorithms, graph algorithms, and some numerical algorithms. The course will concentrate on developing implementations, understanding their performance characteristics, and estimating their potential effectiveness in applications.

COS 226 is a survey course covering the most fundamental and important algorithms and data structures. Because of this, the material and assignments remain at approximately the same difficulty throughout. The initial focus is on sorting algorithms, then progresses to searching, and ends with string processing. The course includes additional discussion on regular expressions, data compression, and reduction.

Emphasis is placed both on understanding how the implementation of an algorithm or data structure works and on using them as tools in your code. The programming assignments help you develop the problem solving skills needed to employ them beyond their most straightforward applications, whereas the exercises and exams highlight the nitty­ gritty details of mechanics and performance. Both are essential to succeed in the course and for a deep understanding of the concepts taught.

The primary challenge in this course is concretizing the algorithms from the abstract way they’re taught. It can be difficult to look at the Java implementation of a given algorithm or structure and get a feel for how and why it works. The demos and examples are crucial, but it’s easy to memorize the steps needed to carry it out or a list of potential applications without truly grasping the algorithm. Taking advantage of all the resources in the class will allow you to fully learn the algorithms and develop the problem solving skills needed to make you both a better student in this class and a better programmer overall.

Learning From Classroom Instruction

Although the lectures are comprehensive, it is important to engage with the material outside of class time in order to understand the concepts introduced. Sometimes the implementations or derivations of performance characteristics are glossed over, but reading through the lecture slides beforehand allows you to learn these denser aspects at your own pace. However, the slides are modified slightly from semester to semester, and they are not always updated soon enough before the actual lecture. In such cases, the old version of the slides is sufficient for previewing the material since the fundamental details of the algorithm or data structure will not have changed. An alternate or supplementary strategy is to review the lecture slides afterwards to ensure you completely understand any math or sample code covered.

Another option is to read the textbook. The course website provides the sections of the book corresponding to a given lecture, but the lecture slides tend to be more helpful than the readings. The material is condensed on the slides in such a way that the most important information is highlighted without losing any essential context. Moreover, the book and lectures are written by the same people, so neither offers a new perspective on the other. Thus, the readings are generally only helpful when a specific point on the slides is unclear and you want to refer to a more thorough explanation.

During the lecture itself, most students will find that it is not necessary to take notes. Everything important is contained within the lecture slides, and devoting time to writing down what the professor says can detract from your ability to follow along. It can be helpful, however, to either have the lecture slides pulled up on your laptop or to have a printed copy accessible during class time. This way, you can annotate as needed and look back at previous slides if part of the lecture is too fast­ paced.

If you are participating in flipped lecture instead of traditional, it is absolutely essential to watch the videos prior to coming to class. The brief instruction in the beginning of class is meant to review concepts, not introduce them for the first time, and you will be unable to fully engage with the problems if you lack that knowledge. To maximize the benefit you get from the flipped option, it’s important to follow up with problems that you didn’t understand or didn’t have time to get to during class. Salon is a great resource to view others’ solutions and to ask any questions you might have. Note that flipped lecture requires extra time on your part compared to traditional lecture, and it is geared towards people who learn much better through doing problems than listening or reading. You will still have the opportunity for guided practice under the traditional option through precepts, so you should only select flipped lecture if you are prepared to consistently devote the extra time.

Although precepts are optional for flipped lecture students, it is useful for both flipped and traditional students to attend. The most essential concepts are reviewed, and the class goes through practice problems similar in style to the exam questions. The main difference between the problem­-solving sessions in precept and flipped lecture is that much more structure is present in the former. The class is given a set amount of time to work alone or together on each problem, and then the preceptor goes over the solution. While some problems are gone over as a class in flipped lecture, the students are generally just left to work at their own pace and ask questions as needed.

Precept is also very useful for the help it provides on that week’s assignment. Often, practice problems will be presented that help you work up to the challenges you will face in the assignment and get you thinking in the right direction. The preceptor may also go over the instructions themselves, explaining them in a slightly different way from the online description, and warn you against common pitfalls. Overall, precept is a great resource to reinforce what was learned in lecture and to prepare you for the upcoming assignment.

Learning For and From Assignments

The programming assignments are the most time ­consuming aspect of the course and challenge you to use what you’ve learned in a meaningful application. A common mistake students make is diving right in without taking the time to thoroughly read and understand the assignment. It’s easy to misunderstand the details of an algorithm or the steps you’re supposed to take and end up sinking several hours into code that doesn’t do exactly what it’s supposed to or reach the performance requirements. Instead, make sure you read not only the assignment page but the checklist as well, particularly the frequently asked questions section.

It’s also very important to start early every time. Even if you think you know exactly how to do the assignment, an unexpected bug or performance flaw can easily tack on an extra couple hours to the time you need to complete it. If you run into difficulty, Piazza is an excellent resource to consult. You will often find that your question has already been asked or answered, and if not, you can add it to see if other students or the instructor can help you out. For more immediate help, office hours and lab TA sessions are offered regularly throughout the week so you can ask your questions or show your code in ­person.

Other than with the first assignment, you always have the option to work with a partner. The collaboration can be valuable because it allows you bounce ideas off each other in the event you get stuck, but be careful who you choose to work with. It’s best to find someone who has around the same programming ability as you and works at a similar pace. Otherwise, one of you may become overly reliant on the other, which is disadvantageous to both. Even when you and your partner are evenly matched, be sure that you completely understand all the insights and ideas your partner brings to the table. Similarly, you should take care to thoroughly explain anything that your partner doesn’t understand.

While the programming assignments are excellent for applying a given algorithm or data structure, do not rely on them to inform all your learning for the course. Often the assignment will only address one or some of the key concepts introduced that week, but it’s still just as important to be familiar with the others. For this reason, you should keep up with the lectures as described in the previous section, reviewing or previewing as necessary in addition to attending class. Furthermore, the assignments only address application, not mechanics or implementation. The precept practice problems and Blackboard exercises will both help supplement this knowledge.

The exams are quite different from the assignments in that they do focus on mechanics and implementation with much less application. The single best way to prepare is to do the practice exams provided on the course website and ensure you understand the solution of anything you get wrong. Very similar types of questions tend to be asked from semester to semester, so doing enough practice tests is sufficient to completely prepare you for all but the two challenge questions. These questions are generally design­ based, and while old exams will help you practice this type of insightful thinking, you need problem solving skills and a strong understanding of the tools at your disposal to do well on this portion. Study the lecture slides and demos to make sure you know how and why each algorithm works.

External Resources

This course is largely self contained, and the most useful resources are available within its framework. However, since the book and lectures are written by the same people, sometimes you may wish to gain a different perspective or read an alternate explanation of a particular algorithm or data structure. In such cases, it can be useful to google the topic at hand.

What Students Should Know About This Course For Purposes Of Course Selection

The programming assignments are a step up in difficulty from COS 126, so this course may not be a good option if you struggled in its predecessor. However, this course teaches you all you need to know for most coding internships. As such, much of what you learn will also be useful for the technical portions of interviews. If you are at all interested in software engineering, this course is the foundation for coding for a wide variety of advanced applications.

Algorithms and Data Structures

Add a Strategy or Tip