CSE 101 Winter 2002 Design and Analysis of Algorithms Instructor Email Telephone Office Hours Office Andrew B Kahng http vlsicad ucsd edu abk ucsd edu 858 822 4884 office 858 353 0550 cell MW noon 2pm TuTh 8 30 9 30pm 3802 AP M Class webpage http vlsicad ucsd edu courses cse101 Goals of Course Introduction to design and analysis of algorithms Problem solving Classic Problems Sorting Path Finding String Matching Arithmetic Tools Recurrence Relations Some Counting Techniques Reduction Probabilistic Analysis NP Completeness Frameworks Divide and Conquer Greed Dynamic Programming Branch andBound Heuristics Classic dilemmas Ordering of material We ll see a reasonable choice Execution or Innovation More emphasis on latter Scope Very broad may feel like drinking from a firehose but the material is coherent You need to keep up and I assume you are keeping up notes extra questions readings HW Course Logistics Textbook Cormen et al 2nd edition 2001 Lecture Room likely to change Center 101 Discussion 3 sections have been added Wed 09 05 A 09 55 A WLH 2204 76 seats Fri 10 10 A 11 00 A CSB 002 120 seats Wed 11 15 A 12 05 P CENTR 212 146 seats May develop material that is not covered in lecture e g solution of recurrence relations structure of induction proofs etc Four TAs Joe Drish Victor Gidofalvi Eric Hall Cynthia Sheng Homework 6 assignments with 7 10 day lead times First assignment posted on Thursday January 10 check website Hard due dates solutions posted on the web zero credit if late THERE WILL BE IN CLASS QUIZZES 2 3 EC Problems Grading 40 HW AND QUIZZES do not violate academic conduct rules 25 in class midterm Feb 7 35 final March 22 7pm Course Behavior Basic Courtesy Cell phones and other distractions must be turned OFF Range of abilities This is a required course Everyone should learn something from it If you are bored or know material already realize that not everyone else may be in the same position Introduction to Lecture Assigned reading Chapters 1 4 background asymptotic growth rates recurrences Chapters 6 7 heapsort quicksort This week Criteria for algorithms correctness efficiency and some example analyses Asymptotic growth of functions Big O notation Examples of recurrences A Sorting Excursion Lower Bounds worst and average case Practical issues Simple methods Closing the Gap Heapsort and D Q Framework Mergesort Quicksort Example of Randomized Analysis Next week Selection The D Q Framework Introduction What Is This Course About An algorithm is a method for solving a problem on a computer Problem Given fraction m n reduce to lowest terms An algorithm must be effective In particular give correct answer halt Problem Given undirected graph G V E and vertices s t V is there a path in G from s to t State an algorithm for this problem Other problem examples Given a set of points in the plane find the closest pair Given a set of points in the plane find the shortest tour that visits each point exactly once Traveling Salesman Problem Undirected s t Connectivity s G V E t A1 BFS DFS from s t A2 Take a random walk in G starting at s Is this an algorithm Does it halt A3 Take a random walk in G for 5n3 steps starting at s n V return NO iff we don t visit t Is this an algorithm Does it almost always return the correct answer Do A3 A1 differ in terms of resources used A3 trades time for space is memoryless A3 probabilistic effectiveness Course Overview Themes Problem solving Spirit of Computing real world necessity Examples of real world necessity DNA Sequencing Evolutionary Trees edit distance Steiner trees Finding homologues evolutionary significance string match Conformational Analysis min energy state Autonomous Robots Vehicles managing smart highways collision avoidance path planning Logistics scheduling resource allocation Design of VLSI circuits placement routing partitioning floorplanning clock distribution logic synthesis Course Overview cont What buys more hardware or software FFT Quicksort etc Throwing hardware at a problem is usually not the right answer Patterns of problem solving e g Polya How to Solve It Tools Counting Recurrence Relations Data Structures Problem Solving Patterns Ideas Problem classes and solution classes Lower bounds reductions What do you think this means Intractability and reducibility approximation Course Overview cont Frameworks Paradigms Divide and Conquer D Q searching sorting recurrences Greed Minimum spanning tree coin changing Huffman codes Dynamic Programming matrix chain product shortest path string processing Backtrack and Branch and Bound N queens game tree search and planning Heuristics simulated annealing evolutionary algorithms Other geometry intractability approximation randomization What is a Problem A problem is defined by i input domain e g all ordered pairs of positive integers ii output specification e g equivalent fraction in lowest terms A problem with the input specified is a problem instance e g reduce 343 56 to lowest terms Types of Problems Decision Y N answer Computation How many acyclic s t paths in G Construction more than one answer Construct exhibit an s t path in G Any s t path vs shortest s t path vs Optimization set of all alternatives cost function Determine the shortest s t path in G Correct Algorithm for each input an output is produced that meets specifications Problem Solving First Example Tower of Hanoi Rules i One disk moves at a time and ii Never put a larger disk onto a smaller disk If you move one disk second when will all 64 disks be moved A more useful question What is the minimum moves needed to transfer a stack of n disks Why more useful Assumes optimal strategy Define Notation For a stack of n disks call this number T n Look At Small Cases T0 0 T1 1 T2 3 Problem Solving First Example cont Can we reduce to a known problem Tn 2 Tn 1 1 n 0 Why Shift n 1 move largest disk shift again Why inequality 2Tn 1 1 suffices but maybe can do better Why does the lower bound LB Tn 2 Tn 1 1 hold Must move largest disk sometime at this instant have n 1 on single peg Tn 2Tn 1 1 T0 0 What is a general closed form solution for Tn T 0 1 3 7 15 31 63 Problem Solving First Example cont Looks like Tn 2n 1 let s guess this answer and try to prove it Claim Tn 2n 1 Proof induction T0 0 20 1 holds basis Tn 2Tn 1 1 2 2n 1 1 1 2n 1 I H Is there an easier way to see the result Exercise Consider Un Tn 1 Note the pattern of steps that we followed Question What Makes One Algorithm Better or Worse Than Another Efficiency with respect to