LFD Book Forum  

Go Back   LFD Book Forum > Course Discussions > Online LFD course > Homework 3

Thread Tools Display Modes
Old 07-13-2018, 03:16 PM
skbaek90 skbaek90 is offline
Junior Member
Join Date: Jul 2018
Posts: 1
Default *ANSWER* Q9 (fairly long, not complete)

First, my understanding of the problem's background.

Dr. Yaser has mentioned in previous threads that there are no systematic way of doing this problem, but that placing the points on the perimeter of a circle is a good start.

From what I understand, this ensures that if you can't shatter k points on the perimeter of a circle with a triangle, then you can't shatter the k points with a triangle no matter how you place them and thus k is the break point.

Now, my reasoning about why 7 is correct. To shatter 7 points, you either shatter the 7 points into

Case 1: 0 & 7
Case 2: 1 & 6
Case 3: 2 & 5
Case 4: 3 & 4
... and so forth, where, let's say, the number on the left represents the number of +1's and the right the number of -1's.

You are basically separating the 7 points by connecting 3 points on the circle (thereby forming a triangle). Case 1 ~ 4 is easily handled because for Case 3, for example, you just pick 2 points as vertices of the triangle and pick somewhere on the circle that is NOT a point, thus including the 2 points and excluding the rest, the 5 points.

Case 5 ~ 8 is where I am stuck, but I feel like it still has to do with the fact that Case 5: 4 & 3, where we can shatter using a triangle (3 vertices) and that number 3 is included in Case 5.

Also, if you think about why 9 is not the correct answer, when you try to shatter 9, it breaks down into the following cases:

Case 1) 0 & 9
Case 2) 1 & 8
Case 3) 2 & 7
Case 4) 3 & 6
Case 5) 4 & 5
and so on..

If you look at case 5, you have to define the region for 4 points, or 5 points using only a triangle (which only has 3 vertices). Therefore, it's not possible to shatter 9 points.

This is my understanding of the answer, although not complete. Please correct me if I'm wrong.
Reply With Quote

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

All times are GMT -7. The time now is 05:39 PM.

Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
The contents of this forum are to be used ONLY by readers of the Learning From Data book by Yaser S. Abu-Mostafa, Malik Magdon-Ismail, and Hsuan-Tien Lin, and participants in the Learning From Data MOOC by Yaser S. Abu-Mostafa. No part of these contents is to be communicated or made accessible to ANY other person or entity.