Transforming a relation to 3NF
I think this is better choice when student can choose multiple Major at a time.

STUDENT (StuID, StuName)
MAJOR (StuID, Major)


You Second Try will be a better choice when student can choose only one Major at a time

STUDENT (StuID, StuName, MajorID)
MAJOR (MajorID, Major)


Now one more step, I can think of here is, as Major  value is some fixed set of variable(limited in number), This will gives the option to add new Major and student can choose more than one Major at a time.

Student (StuID, StuName)
Major (StuID, MajorID)
MajorLookup (MajorID, Major)