CS 4850    Spring 2014

Mathematical Foundations for the Information Age

M W F     1:25pm-2:15pm     Gates Hall G01

Announcements        Concepts        Exams        Homework       Course Staff        Office Hours

Announcements

• For the purpose of this course, if G=(V,E) is a graph, then a subgraph G'=(V',E') of G is a graph, in which V' is a subset of V and E' consists of all those edges in E that have both endpoints in V'. On the other hand, if we ask 'Does the graph contain a cycle on 4 vertices?', then we mean a subset consisting of 4 vertices that has the appropriate edges (regardless of whether it has any edges that we wouldn't need).
• HWs should be typed (Latex, Word etc.) and submitted on CMS.
• HWs are available on CMS and due on Wednesday midnight the week after they are released.
• Returned homework not picked up in class can be obtained from Gates 216.

Prerequisite

Material covered in CS 2800: Discrete Structures is a prerequisite for the course.

Regrade requests will be considered if:
- they are handed to Prof. Hopcroft, Mevlana or Daniel within one week of the time that the given homework or exam is returned to the class.
- the answer was falsely graded as incorrect. So, in particular, we will not accept requests for higher partial credit.
- they come with a written explanation, stapled onto the assignment, of why the given answer was right.

Concepts: The course will cover mathematical foundation of modeling and searching of the WWW and other complex networks, discovering trends, data mining, and making recommendations based on user behavior. Topics will include large graphs, random structures, phase transitions, spectral methods, data in high dimensions, Chernoff bounds, generating functions, second order methods.

Textbook: Mathematics for the Information Age by Ravi Kannan and John Hopcroft. The online version of the book can be accessed here. There are many different versions of the book online which may have different numbers for the chapter questions. Please refer to this version for correct HW questions.

Exams:

The midterms will be in-class (at the class time and location).

• First midterm Feb 26
• Second midterm March 24
• Final Wednesday May 14 2:00-4:30 Upson Hall B17

For a tutoring session with one of our TAs, you can contact je236@cornell* or tsm78@cornell* and arrange a session. The session will focus on the course material and HWs.

Homework:  Questions for the HWs are from Kannan/Hopcroft textbook (see above). Students are encouraged to work together but each must submit his own HW (written in his own words). The only requirement is that you understand everything you turn in. You must show all your work to receive substantial credit. These include all the relevant part of your code for the coding questions and the assumptions you made/parameters you used that were not specified in the question text.   You are expected to type your solutions (i.e. no handwriting) and electronically submit to CMS.

HW 1: 2.1 2.7 2.8 2.10 2.11 2.12, due Wednesday 01/29

HW 2: 2.19, 2.20, 2.25, 2.33, 2.38, and 2.42 due Wednesday 02/05

HW 3: 2.49, 2.56, 2.57, 2.60, 2.64, and 3.2 due Wednesday 02/12

HW 4: 3.7, 3.8, 3.10, and 3.13 due Friday 02/21

HW 5: 3.21, 3.28 and 3.42; Extra Credit 3.19, 3.20, and 3.43 due Friday 02/28

In 3.19 you do not need to give the second moment arguement that technically is required.

HW 6: 4.4, 4.5, 4.7, 4.9 due Friday 03/07

HW 7: 4.10, 4.13, 4.15, 4.18 and 4.31 due Wednesday 3/12

HW 8: 4.35, 4.36, 5.2, 5.4, and 5.6 due Wednesday 3/19

HW 9 5.25, 5.29, 5.30, 5.33, and 5.51due Wednesday 3/26

HW 10 6.4, 6.5, 6.13, 6.14, 6.20, and 6.21due Wednesday April 9

HW 11 6.22, 6.24, 6.25, 6.27, 6.28, 6.33 due Wednesday April 16

HW 12 10.1, 10.5, 10.11, and 10.15 due Wednesday April 23

HW 14 7.7, 7.8, 7.20, 7.25, 9.1 due Wednesday May 7

Course Staff:
Professor:
John Hopcroft -- jeh@cs.cornell*
PhD TAs::
Daniel Freund-- df365@cornell*, Mevlana C. Gemici-- mevlana@cs.cornell*
Akilesh Potti-- avp39@cornell*, Chris Liu-- cl587@cornell*, Horace Pan-- hp264@cornell*, Jung Hyun Eun-- je236@cornell*, Jane Yu-- jy429@cornell*, Toshihiro Noguchi-- tn229@cornell*, Timothy Murray-- tsm78@cornell*, Wenhai Yang-- wy83@cornell*, Xue Wang-- xw92@cornell*, Xiaoyue Guo-- xg55@cornell*, Yanbin Feng-- yf225@cornell*

Office Hours

John Hopcroft -- Monday 2:30pm-3:30pm, Tuesday 11:00am-12:00pm, Friday 11:00am-12:00pm, Gates 426
Mevlana Gemici -- Tuesday 1:00pm-2:00pm, Gates G11
Akilesh Potti -- Saturday 2:00pm-3:00pm, Gates G13
Chris Liu -- Monday 3:30pm-4:30pm, Gates G19
Jane Yu -- Thursday 1:30pm-2:30pm, Gates G13
Jung Hyun Eun -- Thursday 4:30pm-5:30pm, Gates G15
Tim Murray -- Thursday 3:00pm-4:00pm, Gates G17
Wenhai Yang -- Sunday 3:00pm-4:00pm, Gates G13
Horace Pan -- Saturday 3:00pm-4:00pm, Gates G19
Xue Wang -- Friday 3:00pm-4:00pm, Gates G15
Xiaoyue Guo -- Thursday 1:00pm-2:00pm, Upson 328B Bay C
Yanbin Feng -- Friday 2:20pm-3:20pm, Gates G13

Mailing List:

Please email your questions regarding the course material to Daniel Freund: df365@cornell*. We will do our best to answer them in our own time.