HW Assignment 1 Solution

We will strictly enforce the following rules, ask questions now if something is unclear.




Guidelines. Students may discuss problems in the assignment. In fact, discussions are encouraged across HW/MP groups. However, each group must write down the answers independently. If discussions are held, one should also note down the people involved in the discussion (this will help especially if multiple groups make identical mistakes). For the written part of the solution, submit as a SINGLE TYPESET PDF (either from latex or converted from a word editing software). You may use scanned hand drawn gures. See course website for the rules on late submissions.




In your submission, name your PDF le as NETID.pdf where NETID is your actual netid. For a group with two people, use NETID1 NETID2.pdf as the name. We do not allow more than two people to form a submission group for this course. To make it exible, we will not use the \group" function on Sakai. Any member of a group can submit. If we receive more than one submission from a group, we will only grade the one with a later timestamp.













Problem 1 [6 points]. Provide examples of three robots and/or automation devices in existence before the year 1900AD, with pictures and brief description of their purposes (you may use your favorite search engine).







Problem 2 [4 points]. Which of the objects on the








right are convex? They are: a soccer, a net, a dice, a








boomerang. Ignore small features such as shallow grooves
(a)
(b)
(c)
(d)
on a soccer ball.














Problem 3 [10 points]. In class, we use P(S) to denote the powerset of a set S. Let Pn(S) be de ned as Pn(S) = P(Pn 1(S)) for n 1 and P1(S) = P(S). What is P(?) and P2(?) in which

is the empty set? What is jPn(?)j? Given set S with jSj = k. What is jPn(S)j?.



Problem 4 [10 points]. Recall that a group is a set G with a binary operation satisfying the following group axioms:




Closedness: 8a; b 2 G, a b 2 G.



Associativity: (a b) c = a (b c).



Existence of an identity element: 9e 2 G s.t. 8a 2 G, a e = e a = a.



Existence of inverses: 8a 2 G; 9b 2 G s.t. a b = b a = e.



Using the group axioms, prove if G is a group then:




G has a unique identity element.



For each a 2 G, a has a unique inverse.



For each step in your proof, you should explain which group axiom is applied.




explanation will not receive full credits.




Problem 5 [15 points]. See the gure on the right for a two link




robot arm. The two arm segments only rotate in the xy-plane. The




rst (shorter) and second (longer) arm segments have lengths 0:5m and 0:8m, respectively. The motor that moves the rst segment has a 10 bit absolute wheel encoder (recall that the absolute encoder




discussed in class uses 3 bits). The motor between the rst and the second arm segments uses a 15 bits absolute wheel encoder. Theoretically, what is the maximum position uncertainty at the tip of the second segment?




Page 1 c Jingjin Yu Rutgers University
CS 460/560 HW Assignment 1 Due date: 1:00am










Problem 6 [10 points]. Suppose that you have a 10-sided fair dice (e.g., a dodecahedron). What is the expected number of tosses needed to get all 10 sides? What if it is an n-sided dice? Show your work.




Problem 7 [10 points]. Determine whether the following functions are injective, surjective, and bijective. Provide brief justi cations for your answer. If a function is not bijective, modify either the domain or the co-domain (but not both) to make the function bijective.




1. f : [ 2 ; 2 ] ! [0; 1]; x 7!cos x.




f : R ! R; x 7!ex.



Problem 8 [15 points]. Each pair of the spaces given below are homeomorphic. Provide a continuous bijective map to establish this. Justify your answer (showing how you derived your function is su cient).




The interval ( 1; 1) and the real line R. As a hint, consider rst mapping ( 1; 1) to the circle x2 + (y 1)2 = 1 with its north pole removed. Then map this circle to the real line by projecting from the north pole onto the x axis.



The circle f(x; y) j x2 + y2 = 1g and the square f(x; y) j k(x; y)k1 = 1g. k k1 refers to the in nity norm.



Problem 9 [10 points]. Consider the space X formed by chaining two circles together. More formally, we may describe the two circles in three dimensions as




C1: x2 + y2 = 1; z = 0.



C2: (x 1)2 + z2 = 1; y = 0.



Following the de nition of topological manifolds covered in class, determine whether X is a manifold and if so, its dimension.




Problem 10 [10 points]. Using the sampling procedure covered in class and python (or any other way you see t), generate N samples for the cumulative distribution function

(x) = 2
+


2


q














1 e
:
1


sign(x)




2x2
























sign(x) is the sign of x, e.g., sign( 1:6) =
1, sign(5:3) = 1, and sign(0) = 0. Discard any sample
if jxj 5. Plot a histogram of your data from
5 to 5
with 0:2 increments (i.e., you should have
50 bins). Do this for N = 50; 100; 200, and 500. You should submit four gures. Note that you can easily do histograms in python using matplotlib (Hint: it can be slightly tricky to compute x from the CDF; but you don’t really need to).




Problem * [5 bonus points]. Prove that Gray code used in an absolute encoder is always possible to construct for n bits with n 1. That is, it is always possible to order binary numbers from 0 to 2n 1 on a circle such that two neighbors di er at at most one bit.
















Page 2 c Jingjin Yu Rutgers University