Transcript Overviewx
Overview of the course Course homepage and discussion board • sign up at https://piazza.com/purdue/spring2014/cs58000/ • It is recommended to ask questions on the Board instead of directly Emailing the teaching staffs. Grading Grading will be done as follows: • biweekly homework: 20% • midterm: 40% • final: 40% • class and piazza participation & bonus problem: adjust borderline scores Homework Policy • Written homeworks are due at the start of class on their due date. • If you do not know the answer of question, you will receive 15% of the grade for the problem if you admit it up-front by writing “I don’t know how to solve this problem” and nothing else. If your solution is wrong, you get a score of 0 for that problem. • You are encouraged to work in groups of 2 or 3. On all assignments each person should hand-in their own writeup. That is, collaboration should be limited to talking about the problems, so that your writeup is written entirely by you alone, in your own words. Homework Policy • We will not accept late submission. To offset this strict policy, • we will drop the lowest homework grade in the end so that the occasional absence won’t hurt you. • each individual student has a single 48 hours pass. This pass can be used to extend the deadline for one homework by 48 hours. • We prefer that you type up your solutions (preferably using LaTeX). You may neatly hand-write your solutions, but if we have trouble reading them you will be required to type up future solutions. • If you find a solution from any other source, you must rewrite entirely using your own words and cite properly. • The TA rules when it comes to grading homework; their decisions are final. However, they will be available to listen to your explanations. Recommend Textbook for reading • Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein (hereafter referred to as "CLRS"). • Algorithm Design by J. Kleinberg and E. Tardos (hereafter refererred as "KT"). What is an algorithm? • Any well defined computational procedure that takes some value, of set of values, as input and produces some value, or set of values, as output for a well defined computation problem. Example Input:integer 𝑛 Output: then 𝑛-th Fibonacci number What is the 𝑛-th Fibonacci number? Definition of Fibonacci number. 𝐹0 = 0, 𝐹1 = 1, 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛 Alg 1. Function f(n) If n=0: return 1 If n =1: return 1 Return f(n-1)+f(n-2) Things we care about an algorithm • Performance • Running time • Space • Correctness Running time of the algorithm Function f(n) If n=0: return 1 If n =1: return 1 Return f(n-1)+f(n-2) Why is this a bad running time? Current State of Arts Moore’s law • Moore's law: the computing power doubles approximately every two years. Algorithm 2. Function f(n) Create an array 𝐴 0 … 𝑛 A[0] =1, A[1] =1 For (i= 2..n) A[i] = A[i-1]+A[i-2] Return A[n] • Correctness? Running time? What will be covered in this course? • Data Structure • Algorithm Design Techniques • Algorithm Analysis Techniques Data structures: We assume you already know what is a binary tree, head, and linked list. • Treap • Binomial heap • Union find • hasing Design Techniques • Greedy algorithm • Dynamic programming • Divide and Conquer • FFT • Network Flow • Linear Programming • Randomized Algorithms • DFS and BFSReduction Tools for analyzing algorithms • Asymptotic Analysis • Amortized Analysis • Probabilistic Analysis Intractability and Complexity Theory • Complexity class such as NP, coNP, RP, • Reduction