CSE 143 Midterm Exam Topics, 5/5/06

The midterm exam will be held in class on Monday, May 8. The exam is open book and open notes. It will consist of a mix of questions: some short answer, some longer; some involving reading code and analyzing what it does, some involving writing code, maybe some asking for answers to questions that don't have any specific coding involved. You are responsible for topics covered in lecture, sections, and on the homework assignments. The list of topics below is a reminder of what we have covered but might not exhaustively list everything.

When studying for the exam, spend time working problems. While it is important to review notes and other materials, there is a difference between being able to recognize something or follow an existing solution and being able to solve new problems. You need practice working problems - just "going over" the notes is likely not to be enough. Also, don't spend effort memorizing large chunks of code. It is unlikely that you would be asked to reproduce code that you've seen, particularly on an open book test. Instead, you will be asked to solve problems related to ones you've done before or seen as examples. You should know how to analyze a problem, understand how to organize a solution (using diagrams can help), and then work out the code from those ideas. You should know algorithms like binary search at the level of being able to diagram a solution - if you can do that, you should be able to work out coding details as needed.

You also should not spend time memorizing reference material, for instance the names and details about all the methods in an ArrayList or SortedMap. You should know the common operations and be able to use them, but brief reference material will be provided on the exam where needed so you won't have to remember, for example, the order of the parameters or exact names of all the methods in a large class.

Topics

• Basic data structures. Know the following data structures and their operations, and how to use them to solve problems
  • Lists (create, add, delete, search - contains & indexOf, size, isEmpty, etc.)
  • Stacks (create, push, pop, top [access top element without deleting], size, isEmpty)
  • Queues (create, enqueue, dequeue, isEmpty, size, etc.)
  • Maps (create, put, get, contains, size, keySet, etc.)
• Arrays and simple, non-circular linked lists
  • Know how to implement basic operations: create, insert, delete, search, etc.
  • Be able to use these to implement linear data structures like lists, stacks, queues, others
  • Be able to solve other problems using arrays and linked lists
• Classes. Know how to create a well-written Java class, including defining constructors and methods; public vs private for methods and instance variables; proper use of instance variables vs. local variables in methods; using private static final variables for symbolic constants; comments, including simple JavaDoc conventions for public methods.
• Interfaces and implementations. Know the difference between an interface like List and an implementation like ArrayList; know when it is appropriate to use interface or implementation names when declaring variables and parameters, etc.
• Generics. Understand how to create and use instances of interfaces and classes with generic parameters, i.e., things like List<String>, ArrayList<String>, maps, and other generic types.
• Iterators. Know how to use the iterator method to get an iterator from a collection, and how to use hasNext/next to sequentially process the items in the collection.
• Recursion
  • Be able to trace (hand simulate) code that uses recursion (as well as code that does not use recursion).
  • Be able to write recursive algorithms and programs to solve problems or manipulate data structures similar to ones we've seen this quarter.
• Complexity
  • Know the differences between basic complexity classes (constant O(1), logarithmic O(log n), linear O(n), ...), which ones are faster than others, etc.
  • Be able to look at simple algorithms or methods and determine the problem size (parameter magnitude, size of data structure, etc.), and the complexity as a function of that size
  • Be able to discuss implementation tradeoffs in terms of complexity (i.e., if searching needs to be fast for a specific application, would you use an array-based or linked-list-based list and why?)
  • Know what it means if you are, for example, asked to write an algorithm that takes linear time, and be able to do it
• Sorting and searching: know the basic ideas behind sequential vs. binary search; simple O(n²) sorts like insertion sort vs. divide-and-conquer O(n log n) algorithms like mergesort.
• Inheritance
  • Understand what it means for one class to extend another
  • Know the basic terminology: superclasses, subclasses, etc., and be able to answer questions that use these terms
  • Be able to trace (hand simulate) code that involves inheritance and method overriding