CISC 320 Midterm 2

Reccurence Vocab

T(N): Total number of operations for input size N.

a: Number of recursive calls (subproblems), a >=1

b: Factor by which the input size is divided; b> 1

d: Exponent representing the extra work outside recursion, d >= 0

Example:

Here, a=5, b=3, and d=2.

a = b^d

o (n^dlogn)

a < b^d

O (n^d)

a > b^d

n^log_ba

Deriving Reccurence Relations From Function

def f(n):
    if n <= 1:
        return
    f(n // 2)
    f(n // 2)
    for i in range(n):
        print(i)

Answer:

Reccurnece Relation Formula

T(N) = aT/(n/b) + f(n)

Graph

A collection of vertices (V) connected by edges (E).

Directed vs. Undirected Graph

Directed edges have a specific direction; undirected edges allow travel in both directions.

Adjacency List

Stores each vertex's neighbors. Space: O(V+E)

Adjacency Matrix

A V x V matrix indicating whether edges exist. Space: O(V²); edge lookup: O(1)

Breadth-First Search (BFS)

Explores vertices level by level using a queue. Finds shortest paths in unweighted graphs.

Depth-First Search (DFS)

Explores as deeply as possible before backtracking. Uses recursion or a stack.

BFS and DFS Runtime

Both take O(V+E) time using adjacency lists.

BFS vs. DFS

BFS uses a queue and explores by level; DFS uses a stack or recursion and explores by depth.

BFS Shortest Path

BFS finds the shortest path by number of edges in an unweighted graph.

Connected Component

A maximal group of vertices where every pair is connected by a path in an undirected graph.

Bipartite Graph

A graph whose vertices can be divided into two sets with no edges within either set. Can be tested using BFS two-coloring.

Cycle Detection

Finding a path that returns to its starting vertex. DFS can detect cycles.

Topological Sort

A linear ordering of vertices in a DAG where every directed edge u → v places before u.

Directed Acyclic Graph (DAG)

A directed graph containing no directed cycles.

DFS Edge Classification

Tree edges discover new vertices; back edges lead to ancestors; forward edges lead to descendants; cross edges connect other DFS branches (in directed graphs).

DFS Entry and Exit Times

Entry time records when DFS discovers a vertex; exit time records when DFS finishes exploring it.

Articulation Vertex

A vertex whose removal increases the number of connected components in an undirected graph.

BFS and DFS Traversal Order

BFS visits vertices by distance from the start; DFS visits deeply before backtracking. Exact order depends on neighbor ordering.

Adjacency list edge lookup

O(deg(v))

Topological sort runtime

O (V + E)

Adjacency matrix edge lookup

O(1)

Connected components runtime

O (V + E)

Weighted Graph

graph in which each edge has a numerical weight representing cost, distance, or another quantity.

Minimum Spanning Tree (MST)

A spanning tree that connects every vertex in a connected, undirected, weighted graph with the minimum possible total edge weight.

Prim's Algorithm

A greedy algorithm that constructs an MST by starting at one vertex and repeatedly adding the minimum-weight edge connecting the current tree to a vertex outside it.

Kruskal's Algorithm

A greedy algorithm that constructs an MST by considering edges in increasing order of weight and adding them unless they create a cycle.

Union-Find (Disjoint Set)

A data structure that maintains disjoint sets using Find to identify a set and Union to combine two sets. Used in Kruskal's algorithm to detect cycles.

Dijkstra's Algorithm

An algorithm that finds the shortest paths from a single source vertex to every reachable vertex in a weighted graph with nonnegative edge weights.

Edge Relaxation

The process of updating the shortest known distance to a vertex when a shorter path is discovered through another vertex.

Maximum Flow

The greatest amount of flow that can travel from a source to a sink in a network without violating edge capacities or flow conservation.

MST vs. Shortest-Path Tree

An MST minimizes the total weight of all selected edges, while a shortest-path tree minimizes the distance from a particular source to every other reachable vertex.

Is an MST path always a shortest path?

No. An MST minimizes the total weight of the tree, not the shortest distance between individual vertices.

How many edges does an MST contain?

An MST always contains V-1 edges, where V is the number of vertices.

When is an MST guaranteed to be unique?

When every edge has a distinct weight, the MST is guaranteed to be unique.

Can a graph have multiple MSTs?

Yes. Different spanning trees can have the same minimum total weight, especially when edges have equal weights.

Maximum Spanning Tree

A spanning tree that connects every vertex while maximizing the total sum of its edge weights.

Adding a Constant to Every Edge Weight

Adding the same constant to every edge does not change which spanning trees are minimum because every spanning tree contains exactly V-1 edges. However, shortest paths may change.

Cut Property

For any cut in a connected weighted graph, a minimum-weight edge crossing that cut belongs to at least one MST.

Cycle Property

If an edge is strictly heavier than every other edge in a cycle, that edge cannot belong to any MST.

Augmenting Path

A path from the source to the sink in a residual graph along which additional flow can be sent.

Max-Flow Min-Cut Theorem

The maximum possible flow from a source to a sink equals the minimum capacity of any cut separating the source from the sink.

Prim's Algo Runtime (binary heap + adjacency list)

O(E log V)

Prim's (adjacency matrix)

O(V²)

Backtracking

A recursive search algorithm that builds a solution one step at a time and returns to earlier decisions to explore alternative choices.

Pruning

Eliminating branches of a search tree that cannot lead to a valid or better solution, reducing unnecessary computation.

State-Space Tree

A tree representing possible decisions, where each node is a partial solution and each branch represents a choice.

Exhaustive Search vs. Backtracking

Exhaustive search considers all possible solutions, while backtracking can avoid exploring branches that cannot produce valid solutions.

construct_candidates()

A function in Skiena's backtracking framework that generates the possible choices for extending the current partial solution.

Permutations vs. Subsets

Permutations are arrangements where order matters (n! possibilities). Subsets are selections where order does not matter 2ⁿ possibilities.

Heuristic Algorithm

An algorithm that uses practical strategies to find good solutions efficiently without necessarily guaranteeing an optimal solution.

Local Search

An optimization method that starts with a candidate solution and repeatedly explores neighboring solutions to improve its quality.

Hill Climbing

A local search algorithm that repeatedly moves to a better neighboring solution until no improving move is available.

Local Optimum vs. Global Optimum

A local optimum is best among nearby solutions, while a global optimum is the best across the entire search space.

Simulated Annealing

A randomized optimization algorithm that sometimes accepts worse solutions to escape local optima, gradually reducing this behavior as temperature decreases.

Cooling Schedule

A rule controlling how temperature decreases during simulated annealing, making the algorithm less likely to accept worse solutions over time

How many subsets and permutations exist for n distinct elements?

Subsets = 2ⁿ; permutations = n!. For n=4, there are 16 subsets and 24 permutations.

How does backtracking solve the N-Queens problem?

Place queens one row at a time, rejecting placements that share a column or diagonal with previously placed queens. Backtrack when no valid placement remains.

Why can simulated annealing escape local optima while hill climbing cannot?

Simulated annealing can accept worse moves, allowing it to escape local optima. Standard hill climbing only accepts improving moves.

Generate subset choices

O(2ⁿ)

Generate permutation choices

O(n!)

Backtracking

Often exponetial or factorial

Binary search tree exploration (depth n) runtime

O(2ⁿ)

Brute-force TSP runtime

O(n!) tours

Simulated annealing runtime

Depends on iterations and move cost

Dynamic Programming (DP)

An algorithmic technique that solves overlapping subproblems once and stores their answers to avoid repeated calculations.

Optimal Substructure

A property where an optimal solution can be constructed from optimal solutions to smaller subproblems.

Overlapping Subproblems

When the same smaller problems are solved repeatedly during computation.

Memoization vs. Tabulation

Memoization uses top-down recursion and caching; tabulation uses bottom-up table filling.

Dynamic Programming vs. Greedy

DP evaluates multiple choices using stored results, while greedy chooses the locally best option at each step.

Recurrence Relation

An equation that defines a problem's solution using solutions to smaller subproblems.

Dynamic Programming vs. Divide and Conquer

DP reuses overlapping subproblems, while divide and conquer typically solves independent subproblems.

Base Case

The simplest subproblem with an already-known answer.

Edit Distance

The minimum number of insertions, deletions, and substitutions needed to transform one string into another.

Longest Common Subsequence (LCS)

The longest sequence appearing in two strings in the same order, but not necessarily consecutively.

Longest Increasing Subsequence (LIS)

The longest subsequence of numbers in strictly increasing order.

Partition Problem

Dividing a sequence or set into groups to satisfy an objective, such as balancing their sums.

Fibonacci Runtime — Recursive vs. DP

Naive recursion: O(2ⁿ). Dynamic programming: O(n).

Edit Distance and LCS Runtime

Both take O(mn) time for strings of lengths m and n.

Longest Increasing Subsequence Runtime

Basic DP: O(n²). Optimized algorithm: O(n log n).

Edit Distance

Find the edit distance between "cat" and "cut". Answer: 1 substitution.

Practice — LCS

Find the LCS length of "ABCD" and "ACBD". Answer: 3.

Practice — LIS

Find the LIS length of [3,1,4,2,5]. Answer: 3.

DP Runtime

An algorithm fills an n x n table with O(n) work per cell. Runtime:O(n³).

Recursion

A function that calls itself to solve smaller versions of a problem.

Recursive Base Case vs. Recursive Case

The base case stops recursion; the recursive case calls the function on a smaller problem.

When Master Theorem Cannot Be Used

When the recurrence doesn't satisfy its required form or assumptions, such as unequal subproblem sizes.

Direct Proof

Start with known facts and logically derive the conclusion.

Proof by Contradiction

Assume the statement is false and show that this leads to a contradiction.

Proof by Contrapositive

To Prove P → Q, prove ~Q→~P

Proof by Induction

Prove a base case, then show that if the statement holds for k, it also holds for k+1

Inductive Hypothesis

The assumption that the statement is true for k, used to prove it for k+1

Loop Invariant

A property that remains true before and after every iteration and helps prove algorithm correctness.

Walk vs. Trail vs. Path

A walk can repeat vertices and edges; a trail cannot repeat edges; a path cannot repeat vertices.