CSE 373, Summer 2018: Exams

Final Exam

The final will take place on Friday, August 17 in class.

You are allowed to bring one 8x11 inches piece of paper for notes. You may use both front and back sides and it may be handwritten or typed.

Topics covered

  • Sorting:
    • Properties of sorts: stable and in-place
    • Quadratic sorts: insertion sort, selection sort.
    • Faster sorts: merge sort, quick sort.
    • Understand the runtimes of all of the above (in the best and worst case).
  • Graphs:
    • Graph definitions:
      • Directed vs undirected
      • Weighted vs unweighted
      • Walks vs paths vs cycles
      • Self-loops and parallel edges
      • Simple vs non-simple graphs (e.g. multigraphs)
      • Trees, DAGs
    • Graph representations:
      • Adjacency list
      • Adjacency matrix
      • Pros and cons of each
    • Graph algorithms:
      • Graph traversals: BFS and DFS
      • Single-source shortest-path algorithms: Dijkstra's algorithm
      • Topological sorts
      • MST algorithms: Prim and Kruskal
      • Disjoint sets
      • All-pairs shortest paths: Floyd-Warshall Algorithm
  • Dynamic Programming
    • The difference between top-down dynamic programming (memoization), and bottom-up dynamic programming.
    • What are subproblems, and how do we re-use them?
    • Given a definition of subproblems, be able to come up with a recurrence equation for them, including base cases.
    • Given a recurrence relation about subproblems, figure out the order that subproblems need to be solved in.
    • Given a recurrence relation and an ordering of subproblems, be able to write a bottom-up dynamic program.
  • General skills:
    • How to construct different test cases.
    • Reading and mentally running code/pseudocode (to help find the runtime, to help debug, etc...).
    • Given a scenario, determine whether one data structure would be a better fit then another (and explain why).
    • How to use data structures and algorithms we've studied to help us solve novel problems.
  • Algorithm Application:
    For any of the algorithms, make sure you understand:
    • In what situations is this algorithm useful? What kind of data does this algorithm operate on? Is there certain states or types of data that are better suited for this algorithm?
    • What are the pros and cons of using this algorithm vs other choices? Consider runtime and memory usage.

The following topics will NOT be covered in the midterm:

  • Java generics and Java interfaces.
  • Java syntax.

This exam will mostly cover material from after the midterm. The only pre-midterm material that may be tested in-depth is complexity analysis since it applies to all algorithms.

Practice material

This Quarter's Solutions

As said in lecture, these exams will not correlate 100% with the focus and concepts that will be tested in this quarter's exam. Review the topics list, use your best judgement, and ask when deciding whether it would helpful or not to study a given problem.

A few additional notes:

  • Some exams refer to the "union-find" data structure and "up-trees". The "union-find" data structure is the same thing as the "disjoint set" data structure we studied in class. An "up-tree" is the name for each tree contained within the disjoint set.
  • You may want to look at some of the practice midterms, especially if you're looking for more practice on topics like heaps or using the tree method. (This quarter, we both topics after the midterm; other quarters covered them before the midterm.)
  • This quarter we covered dynamic programming instead of P vs NP. The practice finals do not have practice problems for these types of questions, so be sure to do the final review homework since it has a detailed dynamic programming question to practice.

Here are some practice finals from CSE 332. Some, but not all, of the material should overlap with our course.

In particular, CSE 332 spends some time covering topics like parallelism and concurrency that we do not. Feel free to ignore any questions that mention "parallelism", "concurrency", "work and span", and the "ForkJoin" framework.

Midterm

The midterm will take place on Friday, July 20 in class.

You are allowed to bring one 8x11 INCH :) piece of paper for notes. You may use both front and back sides and it may be handwritten or typed.

Topics covered

You are responsible for understanding the following topics:

  • ADTs and data structures:
    • The difference between an ADT and a data structure.
    • Stacks, queues, lists, dictionaries: common implementations, runtimes, and when to use them.
    • Iterators: what they are, how to implement basic ones (e.g. for array lists and linked lists).
  • Asymptotic analysis:
    • Big-O, Big-Omega, and Big-Theta.
    • Finding c and n0 to show that one function is in Big-O, big-Omega, or Big-Theta of another.
    • Modeling runtime of a piece of code as a function possibly including a summation or a recurrence.
    • Understand the difference between best-case, average-case, and worst-case runtime.
  • Trees:
    • How to implement and manipulate trees including binary search trees and AVL trees.
    • Runtimes for tree operations.
    • Performing AVL rotations when inserting values.
  • Hash tables:
    • Closed vs open addressing.
    • Collision resolution: separate chaining, linear probing, quadratic probing, double hashing.
    • Basics of good hash function design.
    • Load factor.
    • Runtimes (best, average, and worst-case).
  • Heaps:
    • How to implement heaps: insert, peekMin, and deleteMin
    • Tree and array representation of binary heaps (we will use 0 based indexing, unlike the book)
    • Runtime of heap operations
    • Floyd's build heap, and why it is faster than building a heap by repeated insertion
    • Heapsort
  • Testing
    • How to construct different test cases.
    • Reading and evaluating code to debug
  • Design Decisions
    • Given a problem description, which ADT(s) can solve it?
    • What are the pros and cons of different implementatinos of the same ADT?
    • Given a task and a set of possible implementations, argue for a particular implementation as most suitable for the task. What assumptions are you making?

The following topics will NOT be covered in the midterm:

  • Java generics and Java interfaces.
  • JUnit.
  • Java syntax.

Practice material

Here are some exams and past material from past quarters from CSE 373. Keep in mind that some of these midterms may ask questions that we do not plan on asking in our midterm. If a problem does not obviously map to any topic listed under "Topics Covered" above, then you can ignore it. If you are unsure, just ask on Piazza or someone on the course staff.

Here are some practice problems from CSE 332. Most of the material should overlap with our course.