CS 201: Exam 1 Info
Table of Contents
Notes sheet
You are permitted one 8.5 x 11 handwritten notes sheet (both sides) for use as a reference during the exam.
How to study
Lots of research has shown that reading over material isn't a very good way to prepare for exams. The best thing to do is to practice. Reading how to swing a baseball bat or how to cross-country ski might give you some good ideas on how to get better the next time you try it, but it's not even close to just getting out there and swinging a bat or skiing in the Arb.
How can you practice? The textbook has a fantastic set of self-test exercises, that appear throughout the readings. The answers to the self-test exercises are at the end of the chapter. Practice these under test conditions and see how you do.
Additionally, at the end of every chapter is a set of exercises. Even though the solutions to those are not available, just trying to do them can be incredibly useful. The ones that involve programming you can put into the computer to see if they work. Otherwise, you can work with other students to see if you think you've got the right answers. Even if you don't know for sure if you've got the right answer, just practicing with these exercises can be helpful.
Finally, make sure to do all of your practicing on paper, not at a keyboard, so as to simulate the exam conditions.
Exam content
Listed below is the material that I have in mind that you should know for the exam. It's what's in my head when creating it. That said, this isn't a contract. I may have inadvertently left something off this list that ends up on an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.
Students should be able to…
Java programming
Be able to Write Java code to solve specified problems. Specific examples may be:
- Take input from a user and do something with it
- Appropriately use loops and conditionals ("if")
- Write object-oriented Java code. Appropriately use classes, objects, methods, parameters, instance variables, and constructors. Use static when appropriate.
- Use inheritance. Appropriately use interfaces, abstract classes, and subclasses.
- Be able to work with arrays, in a similar fashion to how we've done with the ArrayBag, or in other contexts.
- Use generics appropriately, both in constructing objects as well as in creating a class.
Be able to correctly predict output from Java code that uses any of the above features.
Be able to predict the output of linked node-style code, or be able to write appropriate code that makes use of chains of nodes.
Computational complexity
- Calculate the big-O complexity associated with an provided algorithm.
- For two functions \(f(n)\) and \(g(n)\), indicate and justify from the definition whether or not \(f(n)\) is \(O(g(n))\).
Java implementations of ADTs
- Be able to justify when arrays (or ArrayLists) are appropriate vs. linked lists for a particular implementation. Be able to do this quantitatively with big-O descriptions.
- Stack, Queue, Deque: Be able to construct Java code to implement a stack using an array, ArrayList, or linked chain of nodes (also known as a linked list). In the case of a queue, be able to appropriately handle problems that occur with a queue in an array.
- Bag, Set, Stack, Queue, Deque: show familiarity with these ADTs, what their operations are, and what they are used for.
Usage of ADTs
- Be able to define what an ADT is, and how it distinguishes from an abstract class or an interface in Java.
- Be able to use a bag, set, stack, queue, or deque to solve a specified problem. One particular example where we did this was in using stacks to evaluate Lisp expressions.