EXAM 1 Flashcards
HW questions and topics chapter 1-6
Door in a wall You are facing a wall that stretches infinitely in both direc-
tions. There is a door in the wall, but you know neither how far away nor in
which direction. You can see the door only when you are right next to it. De-
sign an algorithm that enables you to reach the door by walking at most O(n)
steps where n is the (unknown to you) number of steps between your initial
position and the door. [Par95]
Let n be the number of steps from your starting position to the door. Then in order to reach the door in at most n steps, then we can walk “i” steps in each direction, doubling i each time we walk in a new direction.
Let k be the smallest integer such that 2^k >= n
in each round i, with step length d_i = 2^i for (i= 1, 2, …k-1), you walk d_i steps in one direction, then walk d_i steps back to the starting point, giving us 2d_i total steps for this round.
Total steps in rounds before finding the door:
total_before_round <= 2(1 + 2 + 4 +…+ 2^k-1) = 2(2^k-1) =
In the last round you walk out 2^k steps till you find the door so the total steps are:
total steps <= 2^k + 2(2^k - 1) = 3(2^k) - 2.
Since 2^k is at most 2n (because 2^(k-1) < n < 2^k)
The total number of steps is at most:
3(2n) -2 = 6n-2.
Gadget testing A firm wants to determine the highest floor of its n-story
headquarters from which a gadget can fall without breaking. The firm has two
identical gadgets to experiment with. If one of them gets broken, it cannot be
repaired, and the experiment will have to be completed with the remaining
gadget. Design an algorithm in the best efficiency class you can to solve this
problem.
Section 3.2: Sequential Search and Brute-Force String Matching
- Skipping phase
- Sequential phas
We solve this problem wiht 2 phases:
Odd pie fight There are n ≥ 3 people positioned on a field (Euclidean plane)
so that each has a unique nearest neighbor. Each person has a cream pie. At a
signal, everybody hurls his or her pie at the nearest neighbor. Assuming that
n is odd and that nobody can miss his or her target, true or false: There always
remains at least one person not hit by a pie
represent the situation by constructing a directed graph where each person is a vertex and each vertex has a single outgoing edge pointing to its unique nearest neighbor. This gives exactly
𝑛
n edges (one per person). Now, suppose for contradiction that every person is hit by a pie—this means every vertex has at least one incoming edge. Since there are
𝑛
n edges total, every vertex would then have exactly one incoming edge. In such a case, the graph decomposes into a collection of disjoint cycles.
A key observation is that, under the condition of unique nearest neighbors in the Euclidean plane, the only possible cycle is a 2-cycle (i.e., two people being each other’s nearest neighbor). But if every cycle is a 2-cycle, then the total number of vertices (people) must be even, as each 2-cycle accounts for exactly 2 people. This contradicts the assumption that
𝑛
n is odd.
Thus, our initial supposition (that every person is hit) must be false. There must be at least one person with indegree 0, meaning at least one person is not hit by any pie
Outline an algorithm to determine whether a connected graph represented
by its adjacency matrix has an Eulerian circuit. What is the efficiency class of
your algorithm?
Section 3.4 Brute Force and Exhaustive Search
Consider the partition problem: given n positive integers, partition them into
two disjoint subsets with the same sum of their elements. (Of course, the prob-
lem does not always have a solution.) Design an exhaustive-search algorithm
for this problem. Try to minimize the number of subsets the algorithm needs
to generate.
Section 3.4 Brute Force and Exhaustive Search
Consider the clique problem: given a graph G and a positive integer k, deter-
mine whether the graph contains a clique of size k, i.e., a complete subgraph
of k vertices. Design an exhaustive-search algorithm for this problem
Section 3.4 Brute Force and Exhaustive Search
Eight-queens problem Consider the classic puzzle of placing eight queens on
an 8 × 8 chessboard so that no two queens are in the same row or in the same
column or on the same diagonal. How many different positions are there so
that
a. no two queens are on the same square?
b. no two queens are in the same row?
c. no two queens are in the same row or in the same column?
Also estimate how long it would take to find all the solutions to the problem by
exhaustive search based on each of these approaches on a computer capable
of checking 10 billion positions per second.
Section 3.4 Brute Force and Exhaustive Search
If we define sparse graphs as graphs for which |E| ∈ O(|V |), which implemen-
tation of DFS will have a better time efficiency for such graphs, the one that
uses the adjacency matrix or the one that uses the adjacency lists?
Section 3.5 Depth-First Search and Breadth-First Search
Three Jugs Sim´ eon Denis Poisson (1781–1840), a famous French mathemati-
cian and physicist, is said to have become interested in mathematics after
encountering some version of the following old puzzle. Given an 8-pint jug
full of water and two empty jugs of 5- and 3-pint capacity, get exactly 4 pints
of water in one of the jugs by completely filling up and/or emptying jugs into
others. Solve this puzzle by using breadth-first search.
Apply insertion sort to sort the list E, X, A, M, P, L, E in alphabetical order.
Let A[0..n− 1] be an array of n sortable elements. (For simplicity, you may
assume that all the elements are distinct.) A pair (A[i], A[j]) is called an
inversion if i < j and A[i] > A[j].
a. What arrays of size n have the largest number of inversions and what is this
number? Answer the same questions for the smallest number of inversions.
b. Show that the average-case number of key comparisons in insertion sort is
given by the formula
n2
12. Cavg(n) ≈
4.
Show that 3n + 5lg n is Ω(n). Is 3n + 5lgn in O(n)? Justify your answers.
- Climbing stairs: Find the number of different ways to climb an n stair staircase if each step is either 1 stair or two stairs. For example, a 3-stair staircase can be climbed three ways: 1-1-1, 1-2, and 2-1. Give the complete recurrence relation. No need to solve the recurrence relation.
- Prove that lg (n!) = Θ (n lg n).
For a given positive integer n, give the formula for the number of bits required to represent n in binary. Then prove that the formula is correct.
We discussed the code to find the maximum element of an array (from the book/ppt). Now assume that the basic operation is the update of maxval (assignment). On an average, what is the time efficiency of the number of times the basic operation is executed? (Note that this is one example of an algorithm where the best case, worst case and average number of times are all different, for the basic operation.) You may refer to any online material for this problem but again you may not copy the whole answer or even part of the answer. (Again, read and understand the explanation, close it and then write in your own words.) And always cite the source that you referred.
- Recall the problem of toggling locked doors from Homework 1: Locker doors: There are n lockers in a hallway, numbered sequentially from 1 to n. Initially, all the locker doors are closed. You make n passes by the lockers, each time starting with locker #1. On the ith pass, i = 1, 2, …, n, you toggle the door of every ith locker: if the door is closed, you open it; if it is open, you close it. For eg, when i=3, we will toggle every third door. Determine the asymptotic order of growth for the total number of times all the doors are toggled in the locker doors puzzle in terms of n.
- Write pseudocode for iterative binary search. Give the best case, worst case and average case analysis for your algorithm. For the average case analysis, you may refer to any source online. But you must cite the source and you may not copy whole or part from any source. (Just read the explanation, close it and then write in your own words.)
(a) Write pseudocode for an iterative algorithm that returns the second highest element in an array of n integers. (b) Then use loop invariants to prove the correctness of your algorithm.
Study the bubble sort algorithm and then write your own code for it. (Again, please cite your source and do not copy any part of the code.) What is the best case and worst-case time efficiency of the algorithm? If we only consider the number of swaps, what will the best case and worst-case time efficiency? Justify your answer.
Define loop invariants for bubble sort
Given an array A[0]….A[n-1] of n integers, give the pseudocode to turn this array into a max heap. (You may not use an extra array.) Then justify that turning an array into a heap by your algorithm, takes linear time in the worst case. What is be the best-case running time of your algorithm? Justify your answers.
Frying hamburgers There are n hamburgers to be fried on a small grill that
can hold only two hamburgers at a time. Each hamburger must be fried
on both sides, frying one side of a hamburger takes 1 minute, regardless of
whether one or two hamburgers are on the grill. Consider the
following recursive algorithm for executing this task in the minimum amount
of time. If n ≤ 2, fry the hamburger or the two hamburgers together on each
side. If n > 2, fry any two hamburgers together on each side and then apply
the same procedure recursively to the remaining n − 2 hamburgers.
a. Set up and solve the recurrence for the time this algorithm needs
to fry n hamburgers.
Outline an algorithm to print a topological sort of a digraph or detect that the graph has a cycle. What will be the time and space complexity of your algorithm?
