Russell-2024-review-guide-midterm.pdf

CS310 Fall 2024 Midterm Exam Study Guide Prof. Russell ONLY This document describes info on how to study for your upcoming exam. The exam will spend some time testing your knowledge of definitions and terminology, as well as your ability to look at code samples and show...

CS310 Fall 2024 Midterm Exam Study Guide Prof. Russell ONLY This document describes info on how to study for your upcoming exam. The exam will spend some time testing your knowledge of definitions and terminology, as well as your ability to look at code samples and show understanding of what happens, and write small code samples that achieve a simple effect. The test might include True/False, multiple-choices, short answer questions, and coding questions (Java 9 or higher). The non-coding portion will check theory and definitions, but it may also involve code reading and test concepts by asking questions such as "which option matches the status of the array/list at the end of the code?" or "what is printed by running the following code?". You must be comfortable coding and reading code on paper! What to bring: Required: A photo ID, preferably your GMU ID. If you do not have a GMU ID, or your GMU ID is damaged so that the name or picture can’t be read, or you only have a “virtual” GMU ID, you can use another form of photo ID. Driver’s license, learner’s permit, state ID card, or passport are all acceptable. If anyone does not have a photo ID at the time of the exam, we will take a picture of that person and the exam will not be graded until a photo ID is shown (so don’t skip the exam because you forgot your ID at home). Required: One side of an 8.5"x11" sheet of paper with hand-written notes (you will submit this with the exam). If you choose not to bring notes, you must bring a blank sheet for scratch paper. How to prepare: Use this document to help identify where you are strong and where you need more practice. Redo the Examples/Exercises/Warm-ups questions. Practice with exercises from the relevant sections of the textbook. Make up your own problems! Reading List Notes and Quick References Big-O: o Chapter 5: Algorithm Analysis o Section 5.3: You do not need to prove the theorems, but you need to understand them. Lists: o Section 6.1-6.3, 6.5: General Lists o Chapter 15: Dynamic Array / Array List o Chapter 17: Linked List Stacks / Queues / Priority Queues: o Section 6.6: Stack/Queue Concepts o Chapter 16.1-16.3: Stack/Queue Implementation o Section 6.9: Priority Queues 1  Hashing: o Section 20.1-20.2: Hashing Basics and Hash Functions o Section 20.5: Separate Chaining o Section 20.3-20.4: Open Addressing o Section 20.6-20.7: Comparisons and Applications Trees: o Section 18.1: Tree Basics, Binary Trees o Section 7.1-7.3: Recursion o Section 18.3-18.4: Tree Recursions, Tree Traversals How to Use This Document Here is the correct usage of this study guide: (1) self-identify what you do and do not know, (2) research in your notes, textbook, and other provided materials what you need to learn/re-learn and any details you have forgotten, and (3) judge your own answers to the questions, using the answers to other similar questions from the warm-ups, participation sheets, programming assignments, textbook exercises, etc. Can you have the answers to all these questions? Unfortunately, it would defeat the purpose of this document to provide answers to the questions presented here. Preparing for an exam is more than just re-answering questions you've already seen, it is also the process of learning and understanding the material presented so far this semester. This is not aided by giving you more of the things you already have! You already have a large bank of questions (with answers) provided in the course material already. This study guide provides you with different type of tool to help you learn and understand the material. It shows you questions you already know how to do (from the participation sheets, warm-ups, programming assignments, textbook exercises, etc.) but it shows them in such a way that you can identify what you do and do not know the answer to. This is where the learning process comes into play; if you follow the process outlined above (identify, research, judge), you will be much better prepared for the exam than someone who only reworks problems with an answer-key nearby. So, this is just a different type of tool for studying, this tool wouldn't work if you had the answer key, and therefore we don't provide one. Use this tool correctly, and it will certainly help you prepare for the exam, but no one is forcing you to use it! You can always focus on the worked examples from the other course material if you think that will be better for your personal learning style. Sample Questions for Review These questions are intended to be answered by hand, on paper, without reference to any notes or to the Internet. There are many more questions than the ones listed here which might be on the exam. This is also NOT a replacement of slides and textbook. For questions that say "write code" assume you need to write complete and valid Java 9 code. These questions are arranged by topic, and roughly ordered by difficulty within a given topic. It is suggested that as a “first pass” you simply read through the questions and mark (for each topic) the “easiest” question you think you couldn’t answer, to get a general sense of your comfort for each topic. 2 Big-O 1. What are the two types of complexity we discussed in class for assessing algorithms? Give an example of trading off one for the other using a data structure discussed in CS310. 2. Explain time/space complexity using a real-life example (like the time complexity examples we did in class). 3. Convert the following functions to Big-O: 10n + O(lg(n)), 0.25n! + 2n, 1+2+3, 5 log(n), log(n^2) + 100 4. For all the code you write for other problems in this review, compute (a) the function which describes the time your function will take to run and (b) the Big-O of the function. Make sure to state what your variables mean (e.g. "what is n?"). 5. If I stated that the big-O of a method was O(1) and that it also contained a loop, describe that loop. 6. What's the difference between "best case", "worst case", and "average case" Big-O? 7. Explain the formal definition of Big-O: T(n) is O(F(n)) if there are positive constants c and n0 such that, when n >= n0, T(n)