Report

CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/ iClicker frequency: CA Learning goals • Mathematics lies at the core of all computer science • It it used to develop fast algorithms that solve complex problems • This course is the first step Learning goals Logistics http://cseweb.ucsd.edu/classes/wi15/cse20-a/ About this class: grading • Final: 40% • March 16th • Midterms (best out of two): 30% • Midterm 1: February 2nd • Midterm 2: March 2nd • Homework: 20% • Online quizzes: 5% • Class participation (Clicker): 5% About this class: attendance • This class is interactive – you read the material at home, we discuss it in class. You need an iClicker. Register it on TED. • Discussion sections: highly recommended. That is the place to understand the material in a slower pace, see more examples, ask more questions. • Office hours: highly recommended. This is your one-on- one time to ask questions and make sure you understand everything. About this class: HW • Homeworks are in groups of 3-4 students • Submitted online via TED, by Monday 2pm (before class) • Collaboration is allowed only within groups, no other collaboration / discussion is allowed • Need help? Come to discussion sections and office hours About this class: online quizzes • Basic questions about definitions from required reading • Should take no more than 10 mins • Due before each W/F class • Online on TED About this class: Academic integrity • You are working on a homework question with your group members and are stuck on a question. You run into a friend who solved the problem already and shows you her solution. You look at it, but put it away before continuing the group conversation. Is this cheating? Yes B. No A. About this class: Academic integrity • You form a group to work on a homework assignment. There are three group members and three questions. You split up the work so that each student gets one question. After you work on your individual questions for a while, you get together as a group and proofread the solutions, then hand them in. Is this cheating? Yes B. No A. About this class: Academic integrity • You’re working on a homework question and run across a definition you don’t understand. You Google the term and, ‘lo and behold, the first hit is a full solution to the homework question. You avoid reading the solution and close the browser. You keep working on the solution and hand in the assignment, without mentioning the Google search since you didn’t use the result. Is this cheating? Yes B. No A. About this class: Algorithms! Multiply 17 x 142. What did we do? Is there another way? The RPM Algorithm Write the factors in two columns. Repeatedly double the LEFT and halve the right. (Truncate fractions, i.e. toss remainders) Cross out the LEFT values where the RIGHT values are even. Add the remaining LEFT values together. A needle in a haystack • You’re working in lab and realize your phone is no longer in your pocket. You turned off the ringer as you came into the room so you know you had it with you. How do you find it? Cutting a cake For N=6 how many pieces? How about for N=600? Two algorithms Alg1(real a, pos int n) x 1.0 for i between 1 and n : x x * a return x Alg2(real a, pos int n) x 1.0 i n while i>0 : if i is odd : x x * a i i/2 if i > 0: a a * a return x Are they correct? Compute the same thing? Which one is better? Two algorithms Alg1(real a, pos int n) x 1.0 for i between 1 and n : x x * a return x Are they correct? A. B. C. D. Only Alg1 is correct Only Alg2 is correct Both correct Both incorrect Alg2(real a, pos int n) x 1.0 i n while i>0 : if i is odd : x x * a i i/2 if i > 0: a a * a return x Two algorithms Alg1(real a, pos int n) x 1.0 for i between 1 and n : x x * a return x Are they the same algorithm? A. Yes B. No Alg2(real a, pos int n) x 1.0 i n while i>0 : if i is odd : x x * a i i/2 if i > 0: a a * a return x Two algorithms Alg1(real a, pos int n) x 1.0 for i between 1 and n : x x * a return x Do they compute the same function? A. Yes B. No Alg2(real a, pos int n) x 1.0 i n while i>0 : if i is odd : x x * a i i/2 if i > 0: a a * a return x Two algorithms Alg1(real a, pos int n) x 1.0 for i between 1 and n : x x * a return x Which one is better? A. B. C. D. Alg1 Alg2 Both the same Depends on the inputs Alg2(real a, pos int n) x 1.0 i n while i>0 : if i is odd : x x * a i i/2 if i > 0: a a * a return x What’s an algorithm? A. A step by step process B. Any way of solving complex problems C. Computer code D. Math An algorithm? • Definition: a step-by-step process • Each basic step is simple • Together they can compute very complicated things • What properties do we care about? A. It should have the correct format (“compile”) B. It should always terminate C. It should give the correct answer D. All of the above For next class • Get the book: Jenkyns, Stephenson and read sections 1.1, 1.2 • HW1 is due Monday Jan 12 5pm • Ask any questions you have about the course, expectations, requirements either in person or via TED • Make note of important dates.