MA 240, Winter 2002, Instructor:  Jeffrey Horn

CLASS ANNOUNCEMENTS (Wednesday, April 17, 2002)

• General Announcements (for all students)
• What IS New:
  • Added HW 6, below.  Due next Wed., last Wed. of class this semester!
  • QUIZ 1 added (Central Park tour), take-home, due Wed. April 17, 2002  (link below)

• What Was New
  • HW5 assigned (see below).  Due Wednesday, April 10, 2002
  • HW 4 assigned (see below).  Due date extended to Tuesday, April 2, 2002 (put in my mailbox in the dept. office)
  • Friday class cancelled (really, postponed).  I could not find someone to conduct a Maple V tutorial, so I'll do one, most likely, at another time, after break.  Go and re-charge!  Don't forget HW3 is due on Wed. after break. (March 13)
  • HW 3 assigned (see below).  
  • HW 2 is finally on the web!  Even though it is past due.  But since I have not turned out solution yet, you can still turn it in with small penalty.  Hurry!
  • HW 1 assigned (see below)
  • Welcome to MA 240!  The main news this first week is that I am gone all week to a conference, so you are "on your own"!  (not entirely).  Here's the deal:
    1. Monday, Jan.14, Dr. Andy Poe (veteran MA 240 instructor) will handout the syllabus (which is also on-line, see link below) and answer any questions about the general nature of the course.  read the syllabus and this web page.  Check out the textbook (get it!) and visit the text book's web site. You may leave early if you don't have any questions.  (BTW, I checked everyone's pre-req.s, and everybody who was enrolled in the course as of last week, met the pre-req.s, as I interpret them!)
    2. Wed., Jan. 16.  Watch "The Proof", a NOVA special on proving Fermat's last Theorem.  Normally I save this for the middle of the semester, but...it is very motivating (for some!) so let's try it a the beginning.  Go to here for details of this assignment.
    3. Finish watching "The Proof" (it is an hour long), and hopefully someone from ACS will be there in our classroom (NSF 1209) to help everyone install "Maple 5" on their ThinkPads.  So bring your laptops!  I'll try to keep you updated as I coordinate this from afar.
    4. I will have full internet access in the "Computer Science Castle", and I will check my email every evening.  So send me questions!  (jhorn@nmu.edu)  Also, our WebCT page might be working any day now and you can start discussions there which we can all read.
    5. You can start reading CH 1 (sections 1.1 and 1.2) to prepare for lectures on LOGIC next week.  this is a good idea as the book has very clear explanations and nice illustrations.

   

CONTENTS:

• Administrativa
• Lecture Notes
• Homeworks
• Tests and Quizes

ADMINISTRATIVA

•  
  • Syllabus
  • The textbook's web site
  • Jobs and Internships

LECTURE NOTES

•  Week of Jan. 14  (first week!)
  • Introduction, Syllabus, Policies (attendance, etc.)
  • Overview of course, topics
  • Movie:  The Proof
  • Readings:  Chapter 1, sections 1.1 and 1.2

HOMEWORKS
 

• HOMEWORK 1:    Propositional Logic
  • From the text, Rosen, pp. 11--13:
    • #4, a,f;    #8 a,b,c,d,e,f (all);   #22  a,c,f;  #24 a,d;  # 30;  #32;  #34.
• HOMEWORK 2:  Predicate Logic (with quantifiers)
  • From the text, Rosen, pp. 33
    • #8 (a - e only, so skip f)
    • #12 (a-d)
    • #24 (a,b)
• HOMEWORK 3:  Number Systems (binary, octal, and hexadecimal) and some Arithmetic
  • Main part, click here.
  • Extra Credit:  (<= 5pts.)  Hypercubes (label the vertices of the 4-D hypercube)
• HOMEWORK 4:  Combinatorics (learning how to REALLY count!)
  • From the text, pp.  257--260
    • #6 (d,e,f only)
    • #10, #14, #20, #26, #28, #30, #56
• HOMEWORK 5:  Intro to Graphs
  • Assigned:  Monday, April 1, 2002
  • Due:  Wednesday, April 10, 2002
  • Read Chapter 7, at least 7.1 - 7.3
  • Understand the terminology (e.g., vertices, edges, directed edges, adjacency, etc.)
  • Do problems:
    • page 443-444   # 12, 16
    • page 455-456 
      • # 6 (use a graph to model the problem!  explain to me the meaning of the graph)
      • #20, #34
    • The Modify Koenigsberg Problem!  #1
      1. Draw the seven bridges
      2. Now find the MINIMUM NUMBER OF CHANGES* to Koenigsberg's bridges, that WILL allow the citizens of the city to cross each and very bridge exactly ONCE, returning to their starting point.
      3. SHOW me the change, on paper, and then show me the circuit that crosses each bridge exactly once, and returns to the start.
      4. *(  A "change" is defined as EITHER destroying (removing) a bridge, or adding one).
    • The Modify Koenigsberg Problem!  #2  (same as above, but with one difference:  the citizens do not HAVE to return to their starting points; in other words, they can start and end in different parts of the city, but they must still cross each and every bridge once.  Another way to put it is we are looking for an Euler Path in this second variation on the problem, rather than an Euler Circuit as in #1 above.  Does this relaxation of the requirements mean fewer changes?)
    • Something Fishy handout.  (to be handed out in class on Wednesday, April 3, 2002)
   
• HOMEWORK 6:   More Graphs, and some Trees
  • Assigned:  Wed. April 17, 2002
  • Due:  Wednesday, April 24, 2002  (HARD deadline!)
  • Read chapter 8, but you can skip sec. 8.4.
  • pp. 463-466   #4, #6, #12, #36, #38 (Ch. 7, Graphs)
  • p. 560, #8, #11, #16  (Tree traversal and node visitation orders)
  • pp. 578-580,  #10
  • In a full binary tree of depth 20, what is the deepest tree I can create by simply choosing another node (any node) to be the root? Which node should I pick, and what would be the new depth?  Assume the root node is at depth d = 0.  (In other words, start counting from "0").
  • EXTRA CREDIT (<=5%):  Answer the above question but for the general case of a full tree with branching factor "b" (e.g., b=2 means a binary tree), and depth "d".  

   

•  

TESTS AND QUIZES

• QUIZ 1:  Central Park Tour (click here)