Introduction to Analysis of Algorithms Final Exam Information and Practice
CS4820/5820 Fall 2021
Rooms, Time, and Review for Final
“Due” December 16 2021
Copyright By PowCoder代写 加微信 powcoder
Final Exam is Thursday, December 16th 7pm in Statler 185 (possibly moved to Barton) and online.
A google form will be posted on Tuesday morning, where you can indicate whether you want to take the exam online. Not filling in the form by Tuesday midnight means you are taking the exam in-person.
We’ll have review sessions by TAs on the 10th and the 14th. Times and locations will be announced on Ed.
Solutions to the practice questions will be released on Monday, Dec 13, but you can use office hours to discuss solution with the TAs any time before the prelim.
Guidelines for the Final
The final is cumulative, covering all topics from the beginning of the course. It will be closed book and closed notes.
In particular, the topics include
From Prelim 1: (To review material, see the review packets from the prelim and homeworks 1-5. New practice questions are included below.)
– Stable matching from Chapter 1.
– Greedy algorithms from Chapter 4, including unweighted interval scheduling
(and the greedy-stays-ahead proof technique), scheduling to minimize lateness (and the exchange-argument proof technique), minimum spanning tree (Kruskal, Prim).
– Dynamic programming from Chapter 6, including weighted interval scheduling, knapsack, segmented least squares, sequence alignment (a.k.a. edit distance), Bellman-Ford shortest path algorithm.
– Divide and conquer from Chapter 5, including integer multiplication, quickselect (see also randomized algorithms), finding the closest pair of points in the plane.
– Randomized Algorithms from Section 13, including expected linear-time median finding, finding the closest pair of points in the plane (using randomization and hashing)
From Prelim 2: (To review material, see the review packets from the prelim and homeworks 6-9. New practice questions are included below.)
– Network flows from Chapter 7, including the Ford-Fulkerson max flow algorithm, equivalence of max flows and min cuts, and network flow applications.
– NP-completeness from Chapter 8, including reductions and the problems SAT, Independent Set, Vertex Cover, Hamiltonian Path/Cycle, TSP, Subset Sum, and problems from the homeworks/exams.
Since Prelim 2: (see summary and review questions below, as well as homeworks 10.)
– Computability: Turing Machines, the non-decidability of the halting problem, reductions to show problems are undecidable, Rice’s Theorem.
– Approximation Algorithms from Chapter 11 and the notes posted, including the greedy knapsack 2-approximation algorithm (see notes on the web site), arbi- trarily good approximation for the knapsack problem, simple 2-approximation algorithm for unweighted vertex cover and linear programming rounding 2- approximation algorithm for weighted vertex cover.
Similar to the prelim exams, you will not be tested on sections in the afore-mentioned chapters if we did not discuss them in lecture (the course outline (linked from canvas) shows which sections we did cover). Some topics we covered briefly, such as hashing, and you will not be tested on such topics.
Post-Prelim 2 Topics
The questions on computability will test your understanding of Turing Machines, and your ability to decide which problems are computable, and which are not. Topics you need to know about:
Turing Machine definition, equivalence of different models (e.g. multiple and single tapes, two-way and one-way infinite tapes),
definition of recursive and recursively enumerable sets,
definition of decidability, showing a problem is decidable,
the Halting Problem, and empty-string-acceptance problem,
proving a problem is undecidable by reduction from an undecidable problem (e.g. the Halting Problem) or using Rice’s Theorem.
The questions on approximation algorithms will test your ability to do the following:
showing an algorithm may give a solution that is much worse than optimum (we gave examples of this for knapsack and vertex cover on November 29 and December 3)
analyze greedy methods that give a good approximation algorithm: such as knapsack (see handout), unweighted vertex cover (lecture December 3)
use of dynamic programming to get an arbitrarily good approximation for knapsakc (Section 11.8)
use linear programming and rounding, (Section 11.6) How to study
Here are a couple of recommendations on how to review:
Read the lecture notes or book chapter on a specific topic, and take notes to sum- marize the key concepts. Go take a walk, and try to tell yourself (or a friend) the problem, algorithm, and analysis that you just read from memory.
Try solving all the homework and exam problems again without looking at the solu- tions, including your own solutions.
Review the comments the TAs left for your solutions, and the solutions posted on canvas.
Review the rubric for the homework/exam problems. These are brief summaries of what you need to solve the problem; familiarizing yourself with them helps to get a good understanding of what it is your answer should include and how to allocate your time when writing your answers.
Practice Questions on Approximation Algorithms
1. Consider the Move-It-Quik truck problem: items arrive one at-a-time and the truck weight capacity is K pounds. The loading site only has room for one truck to be loaded at a time. Rather than planning which items should go in which truck in
advance, the movers just load one item at a time in whatever order they find items to pack, disregarding their weight, until the next item wouldn’t fit. Then, they move on to the next truck.
Consider the pseudocode for a greedy truck-loading :
Truck Loading:
c K is the capacity remaining for the current truck m 1 is the number of trucks used so far.
While there is an item i with weight wi left to load:
If c ‘ wi:
// The item fits; load item i on the current truck Set c c wi
// The item won’t fit; send off the current truck // and get a new one to load item i
Set m 1
Set c K wi
Return m as the total number of trucks used.
Suppose at the end of one of these moving jobs, n items with weights w1, w2, . . . , wn
are packed up in that order.
(a) Prove that the number of trucks used by this algorithm, m, is at most a factor of 2 larger than the minimum number possible for taking the n items. That is, if OP T denotes that minimum number of trucks possible by carefully ordering the n items, show that m & 2OPT. Solution: First, we upper-bound how well the optimal packing OPT can get. We know that the optimal solution cannot pack trucks beyond their weight capacity. Let W CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com