Updated 11/5 2:10 p.m.

Information about Quizzes – CS 3100, DSA 2 - Fall 2023

Goals

Quizzes are designed to assess your understanding of course concepts and your fluency with the vocabulary introduced. Ideally you will have learned all content necessary to successfully complete each quiz through a combination of lecture and your effort on related homeworks (programming and written).

Collaboration and Resources You Can Use

• You must complete quizzes entirely on your own.
• Do not discuss the contents of a quiz with anyone outside the course staff until the day after the quiz. Some students may be taking the quiz later in the day, after you take it.
• The quiz is closed-book and closed-notes. You cannot access a computing device, or a smart-phone, smart-watch, etc.

You will be asked to pledge on each quiz that you’ve observed these directives.

Format and Delivery

• Quizzes will be given in-person in class.
• You will write your answers on paper. Please bring a pencil with dark lead or a pen.
• If more than one quiz is being given, you will get a separately stapled set of pages for each quiz.
• The normal time to take both quizzes will be 75 minutes.
• We will design each quiz to take about 30-35 minutes. You can divide up your time between the two quizzes in whatever way works best for you.
• Question types: Each quiz will be a mixture of question types. There will be some short-answer, possibly some true/false or multiple choice. There may be a simple proof (or questions about a proof you’re given on the quiz or one we’ve studied). You may be asked to come up with an algorithm for a relatively simple problem, which you can describe in words or pseudocode.

Quiz Guides

Quiz 1: Graphs and Asymptotics

Here is what you’ll be expected to do on the quiz:

• Intuitively understand the definitions of \(O\), \(\Omega\), \(\Theta\), \(o\), \(\omega\) and how they relate to evaluating the running time of algorithms
• Be able to demonstrate asymptotic bounds of functions
• Understand the definition of a graph and definitions of various properties of graphs including:
  • Directed Graph
  • Undirected Graph
  • Weighted Graph
  • Node degree (including in-degree and out-degree)
  • Path
  • Cycle
  • Simple Path
  • Connected Graph
  • Cyclic Graph
  • Topological sort
  • Strongly Connected Component
  • Bipartite
• Be able to reason about the tradeoffs between using an adjacency list representation of a graph vs. an adjacency matrix representation
• Understand the following algorithms/traversals to the extent that you could step through them manually and reason about hypothetical changes to them:
  • Breadth-First Search (BFS)
  • Depth-First Search (DFS)
  • Dijkstra’s Algorithm

Here are some vague hypothetical questions that could be asked:

• Show that \(f(n)\in O(g(n))\)
• If \(f(n)\) and \(g(n)\) represent the worst case running time of two different algorithms, what does \(f(n)\in \Omega(g(n))\) tell us about how many operations they’ll do for large inputs?
• Suppose we did a DFS on the given graph starting from node \(0\), what type of edge is \((3,4)\)? Is it a tree edge, back edge, forward edge, or cross edge?
• Is it possible to run DFS on an acyclic graph and find cross edges? If so, then give and example graph and start node. If not, argue why.
• Suppose we did a BFS on the given graph starting from node \(5\), which node would be the last one removed from the queue?
• Suppose we had a graph were all edge weights were positive and unique. Could our implementation of Dijkstra’s algorithm from class ever add the same node to the priority queue twice?
• Suppose we had a graph with \(n\) nodes and \(2\) strongly connected components. What is the maximum number of edges in this graph?

Quiz 2: Divide and Conquer

Here is what you’ll be expected to do on the quiz:

• Reason about the divide and conquer algorithms discussed in class
  • Mergesort
  • Karatsuba
  • Closest Pair of Points
  • Strassen’s
• Provide a recurrence relation to express the running time of a divide and conquer algorithm
• Solve recurrence relations using the Master Theorem and the Tree method. (We will give you the cases and text of the Master Theorem, so you don’t need to memorize it.)

Quiz 3: Greedy

• Greedy Algorithms (general topics)
  • Terminology: optimization problems, feasible solutions, objective function, optimal solutions, etc.
  • Greedy choice property (greedy choice): what this means, and what it is for each algorithm we studied
  • Why Dijkstra’s shortest path is a greedy algorithm
  • Possible questions about how to prove a greedy algorithm correct using an exchange argument (but not a full proof on a challenging problem)
• Coin changing
  • The greedy algorithm
  • Understand overall structure of its proof of correctness for a given coin-set. (For a given range, what do we try to show?)
  • What might make the greedy fail?
• Interval Scheduling Problems (AKA Activity Selection)
  • Greedy approach for this, TBD and proof of correctness using exchange argument
  • Know how optimal substructure applies to this
• Prim’s MST algorithm
  • The overall strategy, use of priority-queue, updating info about connections to nodes that might be selected next, differences between this and Dijkstra’s shortest path algorithm
  • Why decrease-key operation affects our time-complexity
  • But there will be no questions about the details on how indirect heaps are implemented
  • Overall time-complexity for Prim’s
• Kruskal’s MST Algorithm
  • The strategy and algorithm, how to find next edge to add to solution, use of sorting
  • The need and use of set operations Union and Find in Kruskal’s algorithm, but no questions on the implementation of the Find/Union data structure
  • Time complexity for Kruskal’s with Find/Union and its optimizations
• Huffman coding
  • Know the problem, prefix-free codes, the optimization function
  • How the greedy choice produces a smaller subproblem and lets us create a larger tree, step by step
  • You won’t be asked to re-create the exchange argument proof for this, but you might be asked some specific questions about how we did it and why

Topics that will not be covered on Quiz 3 include:

• No questions on how indirect heaps are implemented, but you should know why it’s important for Prim’s
• No questions on proving Prim’s or Kruskal’s is correct
• No questions on how the Find/Union data structure is implemented, but you should know why it’s important for Kruskal’s

Quiz 4: Dynamic Programming

• For any algorithm studied in this unit, know…
  • Optimal substructure property for the problem the algorithm solves
  • Time and space complexity for the algorithm
• Dynamic Programming (general topics)
  • Good for overlapping subproblems. Good when we can’t guarantee we find best solution by solving just one subproblem.
  • Finds solutions to smallest subproblems first
  • Two implementation approaches: top-down with memoization, and bottom-up
  • Compare and contrast DP and Greedy approaches in general: what’s similar/shared, how different, when is one more appropriate
  • For each algorithm we studied, know…
    • The recursive structure of the solution in terms of its subproblems
    • How to build the table from small solutions to the overall solution
    • How to recover the values that led to the optimal solution from the table
• Log Cutting Problem
  • Bottom-up dynamic programm (DP) solution
• Matrix Chain Multiplication Problem
  • What value are we optimizing, and why the order that you multiply pairs matters
  • Bottom-up dynamic programm (DP) solution, storing values for a range of given size along diagonals in the table
• LCS Problem
  • Definition of the LCS problem
  • The cases for the recursive subproblems to be solved
  • This is one example where the slides show you both a top-down and bottom-up solution
• Seam Carving
  • How minimum seam values are stored in the m x n table, and recursive definition used to build this from bottom up
  • How to find minimum cost seam
  • No questions on details of updating the table when removing a seam!
• Coin changing
  • Know its advantages compared to the greedy solution
  • Know the recursive structure of the solution
  • No questions on a bottom-up solution for this problem

Topics that will not be covered on Quiz 4 include:

• For seam carving, no questions on details of updating the table when removing a seam!
• No questions on Seinfeld episodes or on the relative cuteness of baby ducks
• Nothing on the gerrymandering or string edit algorithms done “for fun” on the last part of the last day of this unit

The following section last updated on 12/4 at 9:55 pm

Quiz 5: Reductions and Intro to ML

Network Flow Problems and Analysis

• Understand the definition of a flow network and the max flow problem
• Be able to convert between a flow network and a residual graph
• Know the definition of and be able to find an augmenting path
• Understand the Ford-Fulkerson algorithm to a sufficient degree to be able to run it by hand.
• Understand the time-complexity for Ford-Fulkerson and why it’s correct
• Edmunds-Karp algorithm: how it differs from F-F, when it might be more efficient
• Max-Flow Min-Cut Theorem
  • Minimum Cut, definition of a cut, etc.
  • What the Max-Flow Min-Cut Theorem states, how cuts and augmenting paths are part of that proof

Reductions

• Edge-disjoint paths and vertex-disjoint paths
• Definition of a reduction
• Bi-partite matching
• Reductions to network flow and relationship between bi-partite matching problems and network flow.
• Reduction of Element Uniqueness to Closest Pair of Points
• The MaxIndSet and VertexCover problems and reductions between them
• Understand how to use reductions to apply a worst-case-lower-bound from one problem to another
• Given two problems, describe a reduction. This will at the same level as the problem in PS5.
• NP Complete Topics (at a high level)
  • The definition of the set of problems P, and the definition of the set of problems NP
  • What makes a problem NP Complete? (belongs to NP, and any other problem in NP can be reduced to it in polynomial time)
  • The meaning of the open question Does P=NP?
  • What does it mean if we find a polynomial solution to a problem in NP Complete?
  • What does it mean if we prove an exponential lower-bound to a problem in NP?

Machine Learning

There could be a small number of general questions on high-level concepts on these topics:

• What is unsupervised learning and clustering?
• What is supervised learning and classification?
• The basic concepts that define reinforcement learning
• Questions that show you understand how the k-means clustering algorithm works
• Questions that show you understand how the k-nearest neighbor classification algorithm works
• There will not be questions on PA3 or the single-link clustering algorithm
• There will not be questions related to the last two questions on PS5.