CSCI 136 :: Fall 2020

Data Structures & Advanced Programming

Home | Schedule | Labs | Handouts | Links | CS@Williams

Midterm Exam Material

The exam may include anything we covered in assigned lecture videos or in lab up to and including Sorting. The lecture videos often correspond to (supplementary) readings from Java Structures (Chapters 1-7 and Chapter 9). You may wish to review some of these chapters if there are concepts that were unclear or where you would like to practice. However, we will not be including any questions on material that was not discussed in the assigned lecture videos or assigned labs.

Key Course Topics

The following non-exhaustive list may be helpful to recall some of the key topics we have covered:

• Java syntax, compilation, and debugging, as covered in our programming assignments
• Classes (both concrete and abstract), interfaces, and the roles that concrete classes, abstract classes, and interfaces play in program design
• Information hiding (abstraction as a concept):
  • Why it is good
  • familiarity with the Java language features that support these ideas
• Extending classes with inheritance
• Generic classes (e.g., Vector<E>, Association<K,V>, SinglyLinkedList<E>, etc.) and their use
• Pre-conditions, post-conditions, and assertions
• The meaning of static (and non-static) as applied to variables and methods
• Vector, its implementation in the structure5 package, and its methods
• Complexity: Big O definition:
  • Determining the asymptotic behavior of mathematical functions
  • Determining the time and space complexity for a given algorithm/piece of code.
  • Worst and best case analysis (and why they might differ).
• Recursion and induction
• Sorting:
  • A working understanding of the Bubble sort, selection sort, insertion sort, merge sort, and quicksort algorithms
  • The benefits/trade-offs of using Comparator classes and the Comparable interface
• Linked lists (Singly, Doubly, and Circularly linked lists):
  • Note In the Linked List lab, we modified the standard doubly linked list implementation by adding ``dummy nodes’’. You should be familiar with the standard implementation as described in class and in the textbook (i.e., lists without dummy nodes).

Some Strategies for Studying

There are many ways to approach studying, and ultimately, there is no one strategy that is works "best" for everyone. Our hope is that you will use this page decide the best way for you to prepare. Below we have listed some resources that are available to you.

• Work through the sample exam (which includes some questions from previous semesters) that we've posted to the schedule page.
• It is representative of the style of the questions that we would ask, even if the distribution of some of the topics doesn't match the emphasis we've placed on them this semester.
• Compare your solutions against the sample solutions we've posted after you've thought through the questions.
• For more in-depth discussion of specific questions, watch the sample exam video that we've posted to the course webpage.
• Review any videos on the schedule page where the material wasn't clear before conference. If you still have questions, please ask us!
• Review the code that we've posted on the schedule page. It is often heavily commented and related to one of the recent topics.
• Review the labs that you've completed.
• If you want more practice, the textbook has questions at the end of each chapter. The solutions to select questions are given in the back of the book.