1CSE 101, Winter 2002Design and Analysis of AlgorithmsInstructor: Andrew B. Kahng, http://vlsicad.ucsd.eduEmail: [email protected]: 858-822-4884 office, 858-353-0550 cellOffice Hours: MW noon-2pm, TuTh 8:30-9:30pm Office: 3802 AP&MClass 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-and-Bound, 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., 2ndedition (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 notviolate 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 positionIntroduction 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 FrameworkIntroduction: 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”)2Undirected s-t Connectivity• A1: BFS, DFS from s.• 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 5n3steps 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.G = (V,E)stt’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, randomizationWhat 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 specificationsProblem-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