Description of Course Goals and Curriculum
COS 226 is a prerequisite course for the Computer Science major and for the certificate. This course will teach you about the most common known algorithms for sorting, binary search, substring search, pattern matching in a text and other algorithms related to graph theory such as shortest path, minimum spanning tree, cycle identification etc. This class will not ask you to come up with your own algorithms, expect from during the midterm and the final exam, in which case the algorithms you will come up with will be modifications of algorithms you have studied in class. You will however be expected to analyze algorithms in terms of the running time vs memory tradeof. The class also teaches some of the most important data structures such as symbol table, hash table, sets, queue, stack. You will also analyze them in terms of which one is the most appropriate for a given task considering running time and memory. The goals of the class in an increasing scale can be summarized as:
- Know how the algorithm/data structure works and be able to trace it on a given set of data
- Analyze the properties of the algorithm and compare them with other algorithms
- Implement the algorithms in the assignments
- Modify/combine algorithms to come up with new algorithms to be used for some specific task.
Learning From Classroom Instruction
Lecture
Attending lecture is important because understanding how the algorithms work is way easier through an oral description than through a written one. The demos during lecture, which trace the algorithm, are also very important to understand what the algorithm actually does. Again, tracing an algorithm through the pictures in the book is harder. The lectures are very clear, mostly the professor reads from the slides, so they do not require anything extra other than paying attention. It could be helpful to print the slides to follow them on paper and to take notes if you are finding it hard to concentrate. To check for the students’ attendance the lectures also have little quizzes that you answer through an iClicker. Although this is ungraded, do try to think about the question, because this -however small- interaction with the material being learned will enhance you understanding of the material. Preparation for lecture beforehand is not necessary.
Precept
In precept you do exercises that relate to the algorithms/data structures just learned (mostly tracing) and to the assignment. To make the most of the precept read the assignment beforehand and make sure you have at least a superficial understanding of the steps of an algorithm. The exercises will then deepen your understanding of it. It is important to engage actively with the exercises rather than waiting for the answer by the preceptor/other student, because you will both understand and memorize better.
Learning For and From Assignments
Assignments
You will spend most of the time for this course doing the assignments, which take approximately 10-12 hours. In the assignment you implement the algorithms/data structures you have learned about in lecture. You are in a good shape to start the assignment after you have a clear understanding of how the algorithm/data structure works after the lecture and precept. You can receive a lot of help doing the assignments from lab TA-s and office hours of preceptors, however it will be more helpful if you do not over-rely on these resources. Before starting the assignment you will (and should) have a plan in mind about how you are going to proceed. If you are not
entirely sure about whether your idea will work, expose your idea to a preceptor in office hours. It has happened to me that after 2 hours of writing code based on an idea that was not well thought-through in the beginning, I realized that the idea would not work once I reached one of the functions we had to write.
Your code will most certainly contain bugs and some of them are quite interesting as to try to identify and resolve them by yourself rather than immediately seek help. If you find that you are taking a long time to identify the bug then definitely seek help, as it might just be a typing mistake to which your eyes have gotten too accustomed to be able to identify it.
Exams
There is a midterm and final exam for the class. The final will focus on the second half of the course. The exams contain these types of questions:
- tracing algorithms for a set of data – or variations of tracing such as determining what was the initial data fed into the algorithms, what data is missing in the trace etc.
- questions about the running time/memory analysis of algorithms and data structures in the form of True or False questions or single answer questions
- questions about the assignments – mostly about running time and memory – so make sure you reread the assignment descriptions and your assignment before the exams
- reduction question – you will be asked to use an algorithm for a certain task to perform the task of another algorithm, usually by modifying the data input you give to the algorithm
- algorithm design – you will design an algorithm for a given task by combining or modifying the algorithms you have already studied
Reading the book may not be necessary for the assignments, however it is necessary if you want to have a deeper understanding of the algorithms, learn how to analyze them and do well in the exams. It would thus be ideal to allocate about 1.5 – 2 hours a week to reading the book. Then before the exam reread the parts of the book that are more analytical: the ones that discuss the properties of the algorithm rather than how the algorithm works. Put down in your cheat-sheet the running time and memory usage for each algorithm/data structure.
The last two types of exercises – reduction and algorithm design – are the hardest ones in the exam. The class does not prepare you directly for these types of questions. If you want to prepare yourself throughout the course for these types of exercises then a good method is to do the highest level exercises from the study guide that the course provides. Otherwise, if you are preparing before the exam, use the exercises from the past exams. It is important to spend a long time thinking about the exercises to come up with your own answers rather than looking at the solutions as soon as you encounter hardship – this is the only way to develop your own strategies about how to approach these more creative exercises.
Blackboard exercises
This class also has 2-3 Blackboard exercises per lecture due every Sunday night. These exercises mostly ask you to do algorithm tracing (yes there is a lot of that in this class). You have 3 trials and only the best score counts. To save yourself time, it is better to do the exercises carefully and slowly once rather then do them quickly 3 times. Besides doing them carefully also double check before you submit: one typo will cost you all of the points of the exercise!
External Resources
In case you miss lecture then some YouTube videos with demos of algorithm-tracing can help if you find it hard to follow the “demos” with pictures in the book.
What Students Should Know About This Course For Purposes Of Course Selection
This course is a prerequisite for the computer science major and certificate. To take it you either need COS126 or to be comfortable programming in Java. COS126 also gives an introduction to data structures such as stack, queue and symbol table. This class will explain all of the data structures from the beginning, presupposing no knowledge, but some familiarity with stack, queue and symbol tables would be useful.
If you are debating between taking this class or COS 217 first, my suggestion is that it is easier to continue programming in Java after you have just learned it in COS126. Moreover it is easier to switch to programming in C in COS217 once you know Java very well, because the languages will not get muddled in your head. However, as the COS website will state, any order is feasible and does not presuppose knowledge from the other course.
The course will take about 10 hours for the assignment and 3 hours for Blackboard exercises. Time can vary a lot among students but I have found this to be the average time after talking to other students.