COMPSCI 330 Design and Analysis of Algorithms

COMPSCI 330 Design and Analysis of Algorithms

COMPSCI 330 Design and Analysis of Algorithms Midterm 1 Review Basic Algorithm Design Techniques Divide and conquer Dynamic Programming Greedy

Analyzing running time Design algorithm Proof of correctness Common Theme: To solve a large, complicated problem, break it into many smaller sub-problems. How to know the right technique?

In exam: it will be fairly obvious. In reality: you need experience. Worst case can try all three. Divide and conquer Use when you can partition problems into unrelated subproblems. Key step: How to merge the solutions. Analysis: Use recursion trees for running time (or guess and do

induction) Usually use induction to prove correctness. Dynamic Programming Use if all subproblems are highly related, and there are not many subproblems you need to solve. Define a table for your subproblems. Consider all possibilities in the last step, write the recursion function for the table. Usually use induction to prove correctness

(correctness is often straightforward and you only need to go through the formalities) Try implement the basic algorithms we covered in class. Greedy Use when you can choose an obvious action to reduce the problem size. Proof is crucial --- you will lose many points if you just give a greedy algorithm, even if its correct.

Analysis: Try to find counterexamples If you cannot find counterexamples, try prove the correctness by proof by contradiction Try to argue OPTIMAL must look like your solution. Dynamic Programming and Greedy Both require treating the problem as making a sequence of decisions.

A greedy problem can often be solved using DP as well, but the DP algorithm might be slower. Once you tweak a greedy problem (by adding weights/costs etc.) often the original greedy algorithm fails and you need to do DP. Get used to finding counter-examples if you succeed, it means the algorithm is wrong; if you fail, it often gives intuition for proof. Recursions

(a) (You will not see this kind of problem as it is difficult, but just wanted to use it as an example) Recursions (b) Dynamic Programming Alice is playing a game where she controls the in-game character

to catch pancakes. The character moves on a stage of length n. The character's location can be described by a number x in {1,,n}. Let xt be the position of the character at time t. At each time step, Alice can move the character to the left (xt+1=xt-1), right (xt+1=xt+1) or do nothing (xt+1=xt). Alice already knows the game very well, so she knows a sequence of pairs (ti; pi) - This means at time ti there will be a pancake at location pi. The character starts at location 1 at time 0, and the game goes until time m.

Please design an algorithm to find out how many pancakes Alice can get. Example n = 5, m = 5 Pancakes ((1; 1); (2; 2); (3; 4); (3; 5); (4; 3); (4; 4); (5; 2)), Optimal solution: 4 Can get (1,1), (2,2), (4, 3) and (5,2) simultaneously

Greedy After scheduling for classrooms, let's schedule meeting rooms. Suppose there are n groups of people requesting for meeting rooms at the same time, and there are currently m rooms available. Group i has ni people, and room j has cj capacity. For group i, they are satisfied with any meeting room j whose capacity cj is at least ni, the number of people in the group.

Design an algorithm that tries to find a meeting room for as many groups as possible. Exam Format is very similar to the practice exam It would be quite obvious what technique you should use. There will be an algorithm design question for divide and conquer but it is not difficult. Problems are not necessarily sorted in level of

difficulty.

Recently Viewed Presentations

  • Phytophthora ramorum: Educate to Detect (PRED) University of

    Phytophthora ramorum: Educate to Detect (PRED) University of

    Most of the research with mefenoxam has targeted the prevention of foliar infections, while most research with phosphorous acid has focused on preventing trunk cankers. Slide 80. This presentation was originally developed in October 2004 by Jennifer Parke, Susan Frankel,...
  • La Función Del Tutor

    La Función Del Tutor

    Ideas de investigación Tus PUNs y DENs Temas relacionados con cuestiones debidas a reuniones clínicas, conversaciones con compañeros, etc La revisión por pares consiste en la evaluación de los méritos o errores de una persona realizada por otras que ocupan...
  • Edmodo's mission is to connect all learners with the people ...

    Edmodo's mission is to connect all learners with the people ...

    Edmodo is designed to get students excited about learning as teachers easily create a blended learning experience. Connect. Teachers are at the center of a powerful network that connects them to students, parents, administrators and publishers.
  • Triple Beam Balance

    Triple Beam Balance

    Triple Beam Balance Used to accurately measure the mass of objects Single Buret Clamp Holds one buret during a titration or a test tube that is being heated for long periods of time Volumetric Flask Used to perform solution dilutions...
  • Kapsch Template - ITSVA

    Kapsch Template - ITSVA

    Good afternoon. Chris asked Kapsch to make a presentation about DSRC. In light of the bevy of activity related to the future of V2X communication, it is timely to take this opportunity to not only discuss DSRC but also talk...
  • NEEP 541 - University of Wisconsin-Madison

    NEEP 541 - University of Wisconsin-Madison

    NEEP 541 - Diffusion Fall 2003 Jake Blanchard Outline Diffusion of point defects Mechanisms Vacancy Interstitial Etc. Diffusion of Defects Defect motion is the key to many aspects of radiation damage The motion allows clustering, leading to larger defects that...
  • Introduction to Printmaking Intaglio

    Introduction to Printmaking Intaglio

    This technique is also widely used on textiles, including T-shirts. Robert Rauschenberg andAndy Warhol are examples of artists that used silkscreen. Robert Rauschenberg, Retroactive I, Oil and Silk Screen on Canvas, 1964. Andy Warhol, Marilyn, Silk Screen, 1967.
  • Foot and Ankle

    Foot and Ankle

    The lower leg is comprised of 2 bones (Tibia, Fibula) Forming the foot and ankle mortise of 28 bones . Each Toe Has. Each foot has. Phalanges (phalynx) 1-5. Great Toe (first digit) Digits 2-5. Digits 2-5 have Distal, Middle,...