CSE 531Algorithm Analysis and DesignHung Q. NgoSUNY at BuffaloPlace: 209 NortonTime: Tue and Thu : 11:00–12:20Hung Q. Ngo (SUNY at Buffalo) CSE 531 1 / 22Who should take this course?Anyone who is eithera computer science/engineering studentinterested in getting to know the most fundamental area ofComputer Scienceorforced to take it because it’s required and/or all other courseswere filled upThe catches aredata structures (CSE250 or equivalent)some formal calculus/analysis courseand a course which requires formal proofs (Discrete Math.)... not crucial if you’re motivated enough, though.Hung Q. Ngo (SUNY at Buffalo) CSE 531 3 / 22Who should teach this course?Hmm ...Hung Q. Ngo (SUNY at Buffalo) CSE 531 4 / 22Teaching StaffInstructor:Hung Q. NgoTeaching Assistants:Thanh-Nhan Nguyen: recitation section [temporarily assigned]R1 (R1 Mon 8:00-8:50 214 Norton)Yang Wang: recitation sectionR2 (Wed 9:00-9:50 103 Talbert)Hung Q. Ngo (SUNY at Buffalo) CSE 531 5 / 22When/Where to Talk to Me?Algorithm (Your First Algorithm)1: Course blog http://ubcse531.wordpress.com/2: email ([email protected])3: office hours - 238 Bell Hall, 9:30-10:30 Tue & Thu4: sneak in whenever the door is opened5: goto 1Hung Q. Ngo (SUNY at Buffalo) CSE 531 6 / 22What is the course about?Have fun learning!Grasp a few essential ideas of algorithm analysis and designasymptotic notations and analysisfundamental algorithm design methods: divide and conquer,greedy, dynamic programming, linear programming, network flowthe notions of NP-Completeness, approximation algorithms, andpossibly randomized algorithmsGain substantial problem solving skills in designing algorithms andin solving discrete mathematics problemsHung Q. Ngo (SUNY at Buffalo) CSE 531 7 / 22Course MaterialsRequired textbookCormen, Leiserson, Rivest, Stein, Introduction to Algorithms (2e), MITPress.Online Materialshttp://www.cse.buffalo.edu/˜hungngo/classes/2007/Fall-531Recommended referencesKnuth’s Classic three volume The Art of Computer Programming.Kleinberg and Tardos, Algorithm Design, Addison Wesley.Garey and Johnson, Computers and Intractability: A Guide to theTheory of NP-Completeness, W. H. Freeman Company.Hung Q. Ngo (SUNY at Buffalo) CSE 531 8 / 22Work LoadHeavy! So, start early!Approx. 30 pages of dense reading per week6 written homework assignments (to be done individually)1 midterm exam (in class, closed book/notes)1 final exam (in class, closed book/notes)Hung Q. Ngo (SUNY at Buffalo) CSE 531 9 / 22Grading Policy6 assignments: 5% each1 midterm exam: 30%1 final exam: 40%Note:Assignments are due at the beginning of the lecture on the duedate1 day late (24 hours): 20% (of max score) reductioneach extra date: 40% moreIncomplete grade and make-up exams: not given, except inprovably extraordinary circumstancesHung Q. Ngo (SUNY at Buffalo) CSE 531 10 / 22Academic HonestyAbsolutely no tolerance on plagiarismPlease do the assignments individually on your own. Do notdiscuss with classmates.0 on the particular assignment/exam for first attemptFail the course on the second plus report to department andschoolConsult the University Code of Conduct for detailsIn summary, I will take plagiarism very seriouslyHung Q. Ngo (SUNY at Buffalo) CSE 531 11 / 22About partial creditsAlgorithm (Your second algorithm)Input: your write-up of a solution to a homework/exam problem1: if the write-up contains non-sense (e.g., returned by Google!) then2: You’ll get zero points3: else if you admit you do not know how to solve the problem then4: You’ll get 1/4 of the total credit5: else6: Proceed with normal grading7: end ifThe point is ... to reward intellectual honesty!Hung Q. Ngo (SUNY at Buffalo) CSE 531 12 / 22No Lame Excuses, Please!I have to go home early, please let me take the final on Dec 01.I had a fight with my girlfriendI’ve studied hard, I understood the material very well, ... but I got aC. Please consider giving me A-I think I deserve a better score, please give me some work to donext semester to improve the scoreHung Q. Ngo (SUNY at Buffalo) CSE 531 13 / 22How to do well in this course?Ask questions in classThe only stupid question is the question you don’t askSuggestions are always welcomeAttend lecturesDo homework/reading assignments early!At least, skim through reading assignments before lecturesPrint out lecture notes before attending lecturesWe, the TAs and I, are here to help. Don’t hesitate to ask.Hung Q. Ngo (SUNY at Buffalo) CSE 531 14 / 22A few motivating examplesExample (Fibonacci numbers)Write an algorithm to calculate the nth Fibonacci number, given nF0= 0F1= 1Fn= Fn−1+ Fn−2, n ≥ 2Example (Primality testing)Given a natural number n, returnYES if it is a prime numberNO otherwise(Agrawal, Kayal, Saxena – 2002)Hung Q. Ngo (SUNY at Buffalo) CSE 531 16 / 22A few motivating examplesExample (Shortest Path)Devise an algorithm to find a shortest path from a source (e.g. yourcomputer) to a destination (e.g. www.nfl.com) in the InternetExample (Steiner Tree)Given a set of cities, find an algorithm to assist in building a highwaysystem connecting all these cities, so that that total length of highwaysis minimized.Hung Q. Ngo (SUNY at Buffalo) CSE 531 17 / 22Aha - Algorithms!Algorithm (FibA)Input: non-negative integer n.1: if n ≤ 1 then2: return n3: else4: return (FibA(n − 1) + FibA(n − 2))5: end ifHung Q. Ngo (SUNY at Buffalo) CSE 531 18 / 22Aha - Algorithms!Algorithm (FibB)Input: non-negative integer n.1: if n ≤ 1 then2: return n;3: else4: a ← 0; b ← 1;5: for i from 1 to n − 1 do6: temp ← a; a ← b;7: b ← temp + a;8: end for9: return b;10: end ifQuestionWhat are the pros and cons of FibA and FibB?Hung Q. Ngo (SUNY at Buffalo) CSE 531 19 / 22Analyzing Algorithmsmean of “roughly predicting” the resources requiredResources:How fast: time complexityMemory requirement: space complexityOthers: communication bandwidth, hardware costs, ...Need a specific machine model: Turing machine, RAM, parallelcomputers, quantum computers, DNA computers, ...We’re mostly concerned with time complexity: a rough estimate ofrunning time wrt the input sizeWe will be very informal until NP-completeness is discussedHung Q. Ngo (SUNY at Buffalo) CSE 531 20 / 22Approaches for Designing AlgorithmsAsk someoneHack around ’til it worksBrute forceIncrementalDivide and conquerGreedyDynamic programmingFormulate the problem as something we already known how tosolve (e.g, network flow, linear/non-linear programming, etc.)A stroke of