Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS170 Problem Set 1
Most homeworks will be handed out on Tuesdays, and be due by 4 pm Friday of the following week (10 days later) to Jenny Gonzalez in 387 Soda Hall, or to the CS 170 box in 283 Soda. This first assignment, which covers administrative matters and prerequisites from Ma55 (or CS 70) and CS 61B, is an exception.
Please write your name, your student ID number, your section number, and the name of your TA in all of your homeworks. Also, your answers should be written legibly. The descriptions of your algorithms and proofs should be as clear as possible. (This does not mean they should be long, it usually means the opposite.) They should contain enough details to convince a reader that you have all the necessary ideas for a solution.
And something else. Your homework should be your own work. We encourage you to help each other learn the material by discussing the work before you do each assignment. On the other hand, you should never read another student’s solution or partial solution, nor have it in your possession, either electronically or on paper. It is a matter of intellectual honesty to (a) write your homework strictly by yourself, and (b) acknowledge in it any ideas you got from others (including classmates and books and papers in the literature).
There are many other administrative details that you need to know about the class. Be sure to read the Course Overview, linked from the class homepage:
http://http.cs.berkeley.edu/∼jrs/cs170
All future homeworks, solutions, class notes, grades, and other announcements will be posted in the home page.
Reading: The textbook for the class is Introduction to Algorithms by Cormen, Leiserson, and Rivest (hereafter CLR). It is a good reference book, extremely comprehensive and extensive (often too extensive). From Copy Central (2483 Hearst), you can obtain the very lecture notes the instructors will be lecturing from, which cover the material according to our own style and spirit. The Web page tells you which sections of CLR and the lecture notes to read each class.
1. CLR Problem 2.2 (Note: CLR has a confusing way of numbering their problems. They have exercises after each section, numbered as chapternum.sectionnum-num, and problems at the end of the chapter, numbered chapternum.num. In this and the next instances we are talking about the latter kind. We will often also assign the former.)
2. Order the following functions into a list such that if f comes before g in the list then f = O(g): √ n, loglog n n, 32 n , log(n log n ), (1 + √ 5/2)n , log(n!), 23 n , n log2 7 , (log n) log n , 2 n , n log log n , (1 − √ 5/2)n , n 3/(log n) 4 , n!, 3n 2 , log n, 2n 3 ,
3. CLR Problem 3.1ab.
4. Give an algorithm that, given n integers in the range 1 to k, preprocesses the input and then answers queries of the sort: “How many of the n integers fall in the range [a, · · · , b]?” in O(1) time. Your algorithm should use O(n+k) preprocessing time. What data structure are you using?
5. Prove by induction that 6|(3k + 4k + 5) for k ≥ 1. Note: you have to use induction.
6. CLR exercise 7.5-4.