COM 212 Fall 2014
Data Structures
http://cs.conncoll.edu/cchung/com212

Shall I tell you the secret of the true scholar?  It is this: every person I meet is my master in some point, and in that I learn of them.* - R. W. Emerson

 

This is the web page for COM212 at Connecticut College.  It will be used in conjunction with the course moodle page.  To access the course moodle page, log in to moodle here:  moodle.conncoll.edu.

Course Schedule

Course Description

We will study and explore abstract data structures, such as lists, stacks, queues, trees, hash tables, and graphs.  Students will implement these data structures using the Java programming language.  Run-time and performance analysis of data structures and their related algorithms will also be discussed, and principles of software design will be used in the context of programming projects. 

Course Info

 

All information is subject to change at any time.  Check the course web and moodle pages daily for announcements and updates. 

 

Lectures:

Tuesdays and Thursdays from 11:50-1:05 in NLH 214

 

Professor:

Dr. Christine Chung

http://cs.conncoll.edu/cchung

cchung@conncoll.edu
860-439-2074

New London Hall 220

Office hours:  Thursdays 2:30 – 4:00.  (Sign up for an available time slot.)

 

Grading:

Homework exercises (about 20 of them)

20%

Participation (including posts to moodle forum)

5%

Exams (midterm and final)

20%

Programming Assignments

40%

Final Project

15%

 

TA lab sessions: 

TA lab sessions are run by your TAs in NLH 214.  They are a great place to work on (or get added guidance on) your readings, homework exercises, programming assignments, etc. 

Course Materials

Required software

·         The course web page, which is at http://cs.conncoll.edu/cchung/com212, along with the course moodle page:  login at moodle.conncoll.edu

·         Sun Microsystems JDK (Java Development Kit), which will be available on all Ubuntu workstations in NLH 214, can be downloaded for use on Windows PCs from http://www.oracle.com/technetwork/java/javase/downloads/index.html.  (It should already come installed on macs, but you could install an updated version if you’d like.)

·         Coding can be done using any text editor, but you should use one that does syntax highlighting for Java (color-codes Java keywords as you type for much easier readability).  Examples of such text editors (which you can download and install) include:

·         Emacs and Vim (Linux/Unix, Mac, Windows, etc)

·         Notepad++, Crimson Editor, TextPad, others (Windows only)

·         TextWrangler, Textmate, Smultron, many more (Mac only)

·         In the second half of the semester, you will be permitted to use an integrated development environment (IDE), like Eclipse, if you prefer.

Required text

Data Structures and Algorithms in Java (6th edition), by Michael Goodrich, Roberto Tamassia, and Michael Goldwasser

There will be readings and exercises assigned from this text each week.  There is one on reserve at the library.

Optional/recommended/supplemental texts

Data Structures and Algorithms in Java, by Robert Lafore

                A good, thorough Java reference

Head First Java, by Kathy Sierra & Bert Bates

                A very nice, readable and fun Java tutorial!  Lots of humor and visuals. 

Course Policies

Classroom expectations

Most classes will meet in NLH214 and will not involve coding on computers.  In class we will be learning concepts, usually on the board.  Any “coding” will be done by hand and usually written in Java-like pseudocode on the board (and in your notes).  The use of computers in class is discouraged.  If you plan to use your computer in class, please discuss it with me ahead of time.

Some days will be “lab days” where we work on the computers.  These days will be announced ahead of time, both in class and via moodle, and will be reflected on the course schedule.

Cooperation and academic integrity

In this class you are expected to work cooperatively.  You are encouraged to discuss ideas and ask each other for help.  Indeed, giving and asking for constructive input to/from fellow students is a part of the important learning experience we will be striving for.  Toward this end, you are encouraged to attend the TA lab sessions to engage in your coursework collaboratively whenever possible. 

However, you are not allowed to copy solutions/code from one another.  Likewise it is forbidden to copy solutions/code from anyone/anywhere.  Copying code or submitted work of any kind without citing your source is considered an honor code breach (see Honor code section below)Working together on the same code is allowed only when explicitly specified in the assignment.  To be safe, and to be sure you are maintaining academic integrity, you should always include in your code (via comments) where your ideas came from, if they were inspired by classmates or TAs (give their names), the internet (give URLs), the textbook (give pages/section), etc.  And be clear about whether you’ve copied it exactly or were only inspired by these sources.  Obviously, an assignment using code that you’ve copied (and cited) will not earn full credit, unless the copied code is not critical for the assignment.  Any work that you’ve copied and not cited will result in an honor council referral.

Homework exercises

Reasonably small written homeworks will be due almost every class.  They are written assignments that will allow you to reflect on what you’ve learned the previous class, or prepare you for what we will be learning in the next class. 

·         They must be turned in at the start of class in hard copy (either typed or hand-written). 

·         They will be graded on completeness and clarity rather than correctness.  The lowest homework grade will be dropped.

o   A “complete” homework is one that does not just give an answer, but demonstrates and explains your solution process.  This means you must show your thought process in arriving at an answer.  It also means that if you don’t arrive at a correct answer at all, but describe your thought process during your (sufficiently lengthy) attempts at finding one, you will have demonstrated a complete effort.  If you are still not sure what I’m looking for, follow these steps, journaling as you go, and you will be in good shape. 

o   Complete homeworks will earn a 5 out of 5. 

·         Homework turned in after class starts is considered late.  (If you are late to class, your homework will be late.) 

o   Late submissions will be accepted until the start of the next class, and will earn a maximum grade of 3. 

·         The lowest homework grade will be dropped.

Programming projects

Programming assignments will be submitted in soft copy via moodle, and also in hard copy at the start of class on the day of the deadline.  Projects will sometimes be completed with partners and in this case each group will jointly make a single submission.  Project grades will be reduced by 10% for each day late. 

Linux usage requirement

You must log a total of 15 hours of time (outside of class) on the lab computers running Ubuntu.  This will ensure that you become familiar with a Linux-based computing environment.  It will also encourage you to spend time with your TAs and fellow CS students in the lab, building a sense of team-oriented camaraderie.  There are two ways to log these hours. 

1.       Go during regular TA lab sessions and work on the machines during those lab sessions.  Make sure the TA tracks your time and the TA will fill out this form under their login with your name and hours afterward. 

2.      Go to the lab on your own.  (You can get in using your student ID card.)  In this case, you will be able to track your own hours on a Linux machine (invoking honor code) and you will simply submit the same form using your own log-in.  However, hours logged in this way will count at 50% time.  So if you spend two hours on the machines outside of TA sessions, you will get credit for one hour of Linux usage. 

Final projects

Final projects will be completed in designated teams.  No late final projects will be accepted. 

Campus-wide Policies and Resources

The Connecticut College Honor Code 

Academic integrity is of the utmost importance in maintaining the high standards of scholarship in our community. Academic dishonesty is considered to be a serious offense against the community and represents a significant breach of trust between the professor, the classmates, and the student. There are many forms of academic dishonesty including plagiarism, submitting the same work in two courses without prior approval, unauthorized discussion or distribution of exams or assignments, and offering or receiving unauthorized aid on exams or graded assignments.  Students violating the Honor Code will be referred to the college's Honor Council for resolution.  

Academic Resource Center

The Academic Resource Center (ARC) offers services to support your academic work such as study skills workshops, time management, coaching and tutoring.  Our offices are located in Main Street West, The Plex.  Please visit us or call 860-439-5294 for more information or to schedule an appointment. 

Office of Student Accessibility Services

If you have a physical, mental or learning disability, either hidden or visible, which may require classroom, test-taking, or other reasonable modifications, please see me as soon as possible. If you have not already done so, please be sure to register with the Office of Student Accessibility Services. You can do so by going to the Office of Student Accessibility Services, which is located in Crozier Williams, Room 221, or by contacting the Office at 860-439-5240 or 860-439-5428, or by email to barbara.mcllarky@conncoll.edu or lillian.liebenthal@conncoll.edu. 

Title IX

As a faculty member, I am deeply invested in the well-being of each student I teach. I am here to assist you with your work in this course. If you come to me with other non-course-related concerns, I will do my best to help. It is important for you to know that all faculty members are mandated reporters of any incidents of sexual misconduct. That means that I cannot keep information about sexual misconduct confidential if you share that information with me. Darcie Folsom, the Director of Sexual Violence Prevention and Advocacy, can advise you confidentially as can Counseling Services and any of the College chaplains. Darcie can also help you access other resources on campus and in the local community. You can reach Darcie at x2219 or darcie.folsom@conncoll.edu, and her office is in Cro 222. The student sexual misconduct policy is in the Student Handbook, which can be found on Camelweb, in the “Documents/Policies” section, under the Student Life section. There you will find the policies, definitions, procedures and resources.

 

Student Health Services

 

Student Health Services, located in the Warnshuis Student Health Center behind the library, is available to all full-time, matriculated students. Our purpose is to help students maintain optimal general health through the disciplines of physical and mental health, and health education around lifestyle choices. This is accomplished through a full-time staff and a variety of professional consultants in many disciplines. All professional services are delivered with attention to confidentiality. In the event of a serious illness or injury, parents or guardian will be notified at the discretion of the staff. You can schedule an appointment Monday through Friday by calling 860-439-2275. Information on Care When We Are Closed, Our Services, and Student Health Insurance may be found on Camelweb, in the Student Life Section, under Student Health Services.

 

Student Counseling Services

The mission of the Student Counseling Services is to promote the emotional and psychological growth and well being of the students at Connecticut College. The Student Counseling Services' goal is to enhance each individual's ability to learn, to create and to be fully participating members of the College community by utilizing safe, culturally sensitive and inclusive approaches to mental health treatment.To carry out this mission, Student Counseling Services makes available to students a wide range of outpatient clinical services in a safe, non-judgmental atmosphere including:

o   Evaluation

o   Individual and group counseling

o   Psychopharmacological evaluation and medication management

o   Crisis intervention services

o   Outreach and consultation to the College community

o   Psycho-educational forums

o   Referral to off-campus clinicians for specialized and/or intensive treatment

 

Connecticut College Student Counseling Services has been accredited by the International Accreditation of Counseling Services (IACS) since 2005. Appointments may be made by phone at (860) 439-4587 or via email at SCS@conncoll.edu.

 

Course Schedule

As with everything else, the schedule listed below is subject to change.  Check back often for updates.

Note:  you are expected to participate by asking questions and contributing to class discussion as well as by posting your questions/comments to the forums on the class moodle page. 

WEEK

DATE

TOPIC

AFTER CLASS

1

Aug 28

Intro, course administrivia

HW1 (due on Tuesday, Sept 2): 

·         Getting started

o   Here are a couple useful links that will walk you through this homework:

1.       For Windows: http://download.oracle.com/javase/tutorial/getStarted/cupojava/win32.html

2.      For Mac: http://www.cs.princeton.edu/courses/archive/spr04/cos126/hello/mac.html

o   Install Java (JDK 8) on your own machine (if you have a mac it should already be installed, but it may be an older version) or go to NLH 214 and learn how to run it there.  When installing Java, be sure to install JDK version 8 and follow the installation instructions.  If you are on Windows, you should definitely do the (“optional”) section of the installation instructions on Updating the PATH Environment Variable, also see  instructions from TA Evan Grey ‘13 on updating the PATH variable. 

o   Write the Hello Universe program from page 2 of the text.  Compile and run it for a TA or Prof Chung. 

o   Print out your working code, have a TA (or myself) initial it to certify that they have checked it, and hand it in at the start of class.

·         Reading

o   The course website

o   Chapter 1.1 pages 2-4 and pages 20-37

·         Textbook exercise(s)

o   Complete exercise R-1.5 on page 55 of GTS.  You may write you code in the main method rather than creating separate methods, and you may hard code the value of n for now rather than taking it as a parameter (or read/follow section 1.6 on user input and take the value of n from the user).

o   For one bonus point each: also complete exercises R-1.6 and R-1.7

o   Explain your solution by writing on the print out or commenting the code.  Submit it in hard copy at the start of class.

2

Sept 2

Java basics, Arrays

HW2 (due on Thursday, Sept 4):

·         Complete the worksheet from class practicing with arrays using methods with return values and input parameters

·         Code up the method from your worksheet that returns the max value of an array.  Test it by calling it from a main method.  Add comments to indicate that you understand how/why it always returns the right answer.

·         Recall that the top of page 4 of the GTS text has a list of the primitive types in Java.  You will also find it helpful to review section 1.4.

·         Hand everything in hard-copy (either typed or hand-written) at the beginning of class.  Remember to explain/narrate your solutions…

Sept 4

Arrays, cont’d, Run-time analysis, Parallel arrays

HW 3 (due Tuesday, Sept 9)

Reading:  pages 163-171 in GTS

Exercises: 

·         Write a method that takes an array of integers and returns an array with the integers in reverse order.  You needn’t code up and test this method, but you can if you wish.  Give the run-time complexity of your algorithm in big-O notation.

·         Write a function that takes as parameters two parallel arrays String[] names and int[] ages and returns the name of the oldest person.  Give the run-time of your algorithm.

·         R-4.8.  Start by writing each function in big-O notation. 

·         Bonus:  In class we saw a quadratic-time algorithm for determining whether all the elements of an array are distinct.  Find a linear-time algorithm to do the same.  (Credit goes to Albert for this one.)

Tutorial (due Thursday, Sept 11):  go to NLH214 and complete this Unix Tutorial there (thanks to P. Fritzche ’11 for adapting it to our needs).  Make sure a TA witnesses this and notes that you’ve completed it using the Linux Usage Log form.  Since you will complete this on the Linux machines in the lab, this time will also count toward your regular Linux usage hours.  Make sure the TA also enters these separately, again using the form.

WEEK

DATE

TOPIC

AFTER CLASS

3

Sept 9

Object-oriented programming review, Sorting an array (Insertion sort), Preview of Project 1

HWs 4 and 5 (due Thursday, Sept 11)

Reading:  second packet that was handed out in class about constructors and OOP

·         Complete the written exercises in the pages of the packet (“thinking about objects”) that was handed out in class (except the “pool puzzle”).

·         Tracing through a while loop.  Place the following snippets of code in the following order into the blanks (from top to bottom) of the Pool Puzzle exercise on page 44 of the handout:  Echo e2 = new Echo();,  x < 4,  e1.count = e1.count + 1;,  x==3,  x > 0, Echo, count, hello().  (The code snippets here were delimited by commas.)  Trace through the code by recording the value of each variable at each iteration of the loop.  To do this neatly, create a table with the following column headers:  e1.count, e2.count, x, and output.  In the first row you should put the initial values of each variable before the loop starts.  Each successive row should show the value of each variable upon each successive iteration of the while loop.  The output column should show any output that resulted from each iteration. 

·         Insertion Sort.  Code up, test, and analyze the run-time of Insertion Sort, giving your answer in Big-O notation.  (Recall that the while loop had a missing piece to its condition as we left it in class.)

·         Project 1 prep. Read and understand all the comments and code in the HighArray.java class.  Analyze the run-times of each of the methods in the HighArray class.  Indicate your answers using Big-O notation. 

Sept 11

Project 1:  Arrays, binary search
(Files needed:  HighArray.java, OrdArray.java)

HW6 (due Tuesday, Sept 16):

Reading:  Read chapters 3.1.1 (Keeping High Scores in an Array) and 3.1.5 (2D Array for Tic Tac Toe) of GT text.

Exercises:

·         C-3.23 on page 146 of GT text.  Hint: think 2D array…

·         Parallel sorting.  In class we were sorting the ages[] array, which was originally parallel to an array called names[].  What if we now want to also sort the names, but in increasing order of age?  Add some code to your Insertion Sort that ensures the names[] array stays “parallel” to the ages[] array as the ages get moved around.  What is the run-time of your modified algorithm?

WEEK

DATE

TOPIC

AFTER CLASS

4

Sept 16

Two-dimensional arrays, Arrays of objects

HW7 (due Thursday, Sept 18)

Exercises: 

·         Complete a practice submission for your first project, to test that you can correctly execute the submission instructions.  Don’t worry about what your submit for now, just use the Project 1 submission link on moodle and make sure you successfully compress a folder of at least two Java files.  Anything you submit can be resubmitted, so don’t worry.

·         Finish writing the remove(int i) method that we started in class for removing the GameEntry object at position i of the entries array in the Scores class.  Then try writing the add(GameEntry e) method of the Scores class.  Start with pseudocode solutions (you can use the ones we put up in class), then translate them to Java.  I encourage you to work with other students on this (and on all homeworks, unless otherwise specified), but you should each submit a separate, individualized, write-up.  Note:  the discussion in the book regarding these tasks can be helpful, but try coding it up yourself first rather than copying the book code.  Afterward, it’s good to go back and check your code against the book code and note any differences.

Reading:  Introducing our next data structure…  Linked Lists!  Read Chapter 3.2 of GTS text. 

Sept 18

Linked Lists

Project 1 due by 11:50 am on Tuesday, Sept 23.

WEEK

DATE

TOPIC

AFTER CLASS

5

Sept 23

Project 2:  Linked Lists

(Files needed:  GameEntry.java, Node.java)

HW 8 (due Thursday, Sept 25)

·         Exercises: 

o   Write up Java-like pseudocode for the add(GameEntry e) method of Part A of Project 2.  You may make calls to the addFirst or addLast methods that you will also be creating for Part A. 

o   Also, complete C-3.25 on page 147 of GTS, which says:  “Describe a good algorithm for concatenating two singly linked lists L and M into a single list L’ that contains all the nodes of L followed by all the nodes of M.”

o   Bonus exercise: C-3.28 (worth one or two additional HW points)

·         Reading:  Read Chapter 3.4 of GTS text (Doubly Linked Lists). 

Other assignments:

·         Continue work on Project 2, due Tuesday, Oct 7 at the start of class.

Sept 25

Doubly Linked Lists, Circularly Linked Lists

HW 9 (due Thursday, Oct 2)

Reading:  Read Chapter 3.3 of GTS text (Circularly Linked Lists)

Exercises:  From page 147 of GT:  complete C-3.26 and C-3.27, which respectively read…

·         Give a fast algorithm for concatenating two doubly linked lists L and M with header and trailer sentinel nodes, into a single list L’ .

·         Describe in detail how to swap two nodes x and y (and not just their contents) in a singly linked list L given references only to x and y.  Repeat this exercise for the case when L is a doubly linked list.  Which algorithm takes more time?

Other assignments:

·         Continue work on Project 2, due Tuesday, Oct 7 at the start of class.

WEEK

DATE

TOPIC

AFTER CLASS

6

Sept 30

No class:  fall break

 

Oct 2

Stacks

Project 2 due by 11:50 am on Tues, Oct 7

WEEK

DATE

TOPIC

AFTER CLASS

7

Oct 7

Project 3:  Stacks and Queues

HW 10 (due Thurs, Oct 9):

·         Reading:  Chapter 6.1 in GTS (Stacks).  You will notice in your reading that much of the code has started to look, as one student put it, “foreign,” because it is expressed in terms of generic data types.  To learn about generics in java, refer to chapter 2.5 of the text.  We will not use generics in our class meetings, but they are good to know about and will help you to more easily read and understand the code in the text.

·         Exercises:  R-6.3 and C-6.22.  Also complete C-6.16 and C-6.34 for some fun bonus exercises!  

Other assignments:

·         Continue work on Project 3 with your partners.

 

Oct 9

Queues

HW 11 (due Tuesday, Oct 14):

Reading:  Chapters 6.2 and 6.3 in GT (Queues and Deques)

Exercises:

·         Complete the worksheet on linked-list-based Queues.  Give clear, complete answers.

·         Complete exercises R-6.9 & C-6.32.

Other:

·         Try to get Parts A & B of Project 3 completed.

·         Vim Tutorial (due Oct 21): Spend at least two hours learning to use and/or using Vim, a powerful text editor used by some programmers.  The first hour or so will be just completing this Vim tutorial (courtesy TA Julia Proft).  Your second hour of practicing with Vim can be done coding your projects.  Once you’ve completed it, have a TA submit the usual lab usage form with the words “Vim tutorial” in the “notes” field. 

WEEK

DATE

TOPIC

AFTER CLASS

8

Oct 14

Postfix expression evaluation (Project 3 Part C) and Midterm Exam Overview

Prepare for midterm on all homework and lecture topics through week 7, including projects 1 and 2.  Midterm will be in class, 75 minutes, closed book, closed notes, no computer.

 

Oct 16

Midterm Exam

Try to have Parts A & B & C of Project 3 completed.

Vim Tutorial (due Oct 21): Spend at least two hours learning to use and/or using Vim, a powerful text editor used by some programmers.  The first hour or so will be just completing this Vim tutorial (courtesy TA Julia Proft).  Your second hour of practicing with Vim can be done coding your projects.  Once you’ve completed it, have a TA submit the usual lab usage form with the words “Vim tutorial” in the “notes” field. 

WEEK

TOPIC

AFTER CLASS

9

Oct 21

Trees

HWs 12&13 (due Thurs, Oct 23)

Reading:  Chapters 8.1, 8.2, 8.3.1, 8.4.1, 8.4.3, and 8.4.6 in GTS

Exercises: 

·         R-8.1, 8.11, 8.20, 8.22

·         List the values when traversing this tree (also handed out in class) in (1) preorder, (2) postorder, and (3) inorder. 

·         Don’t forget, as always, to explain/narrate your solutions to all exercises.

 

Oct 23

Binary Search Trees (BSTs)

Make-up midterm exam due Friday afternoon in my office by 2 pm.  See moodle for directions/details.

Project 3 due by 11:50 am on Tuesday, Oct 28

Also fill out the mandatory project 3 questionnaire (required for all students)

WEEK

TOPIC

AFTER CLASS

10

Oct 28

Project 4:  Binary Trees

(Files needed: traverse.txt, displayTree.txt, TreeApp.java)

HW 14 (due Thursday, Oct 30)

Reading:  Read and review the entire project 4 assignment page along with your class notes on trees (especially BSTs) and make sure you understand them all thoroughly.  Do this together with your project partner or another classmate if possible.  Post to moodle any questions you have.  (The GTS text’s presentation of BSTs--Chapter 11.1--is not completely consistent with what we did in class, and what we did in class is what you are responsible for.  Post any particular differences you notice to the class forum.)  Remember, anything you post on moodle counts toward your class participation grade, which is a non-negligible fraction of your final average!

Exercises:  R-11.2 and R-11.4, which read: “Insert, into an empty binary search tree, entries with keys 30, 40, 24, 58, 48, 26, 11, 13 (in this order).  Draw the tree after each insertion.” and “Dr. Amongus claims that the order in which a fixed set of entries is inserted into a binary search tree does not matter—the same tree results every time.  Give a small example that proves he is wrong.”  (Note: in general, whenever you’re asked to give a counter example for something, the smaller the example, the better.)

Other:  Make sure you’ve filled out your project 3 questionnaire on moodle so that we can begin grading.

 

Oct 30

AVL Trees

HW 15 (due Tuesday, Nov 4)

Reading:  Chapters 11.2-11.3 of GTS.  (Keep in mind that the textbook uses blue squares to represent external dummy nodes with no values in them.  In class we just left these off, replacing them with null.  Either way works fine, it’s just a matter of some differences in implementation details.  E.g., a tree from our class notes with height 1 would have height 2 in the book.  So a tree with height zero in the book is just a dummy leaf node, which for us is no tree at all, or null.)

Exercises: R-11.7, R-11.8, R-11.9

WEEK

TOPIC

AFTER CLASS

11

Nov 4

Priority Queues and Heaps

HW 16 (due Thursday, Nov 6)

Reading:  Chapters 9.1 and 9.3 of GTS. 

Exercises:  In addition to the exercise we started in class based on doing insertions and extractions from the heap on the final slide of the handout, complete (from GTS) R-9.4, R-9.10, R-9.11, R-9.19, and R-9.20.  Remember as always to justify your answers.

 

Nov 6

Array-based Heaps

Project 4 due (in hard copy and via moodle) by 11:50 am on Tuesday, Nov 11

Also: fill out the mandatory project 4 questionnaire (required for all students)

WEEK

TOPIC

AFTER CLASS

12

Nov 11

Hash Tables and Final Project

HW 17 (due Thurs, Nov 13)

·         Reading:  Review 9.3 of GT.

·         Exercises: 

o   Draw pictures of how the array representing this tree evolves through each of the following commands:  insert(20), insert(8), insert(1), insert(3), extractMin(), extractMin(), extractMin(), extractMin().  [Note that this time we are using the tree from the start of the powerpoint slides on priority queues, not the tree as it looked on the final slide.]

o   Write code for the extractMin() method on a priority queue implemented using an array-based heap (as discussed in class).  You should write and use a swap(int i, int j) method, which swaps the nodes/entries at positions i and j in the array, as well as the methods int leftChild(int parentPos), and int rightChild(int parentPos), which returns the child position of the parent node at the given position.  As always, comment your code to describe what is going on.

Other:  Meet with your final project team and plan out the design of your final project, deciding on the classes and methods, and dividing it up into separate tasks so that the workload is spread out among your team members.  This project is really a challenge in project management as well as data structures.  Map out a timeline for your project, so you have explicitly established intermediary deadlines for each class/component.  That way you can be sure to leave yourself enough time to connect all the parts together at the end.  The final melding process can be bug-inducing and usually requires some time.  You might consider combining the components together incrementally as you go so that you don’t have to do it all at once in the end. 

 

Nov 13

Hash Codes and Final Project

HW 18 (due Tuesday, Nov 18)

·         Reading:  Chapter 10.2

·         Exercises:  R-10.4 (Which of the hash table collision-handling schemes could tolerate a load factor of above 1 and which could not?), R-10.6 (Draw the 11-entry hash table that results from using the hash function, h(i) = (3*i+5) mod 11, to hash the keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5, assuming collisions are handled by chaining.), and R-10.7 (What is the result of the previous exercise, assuming collisions are handled by linear probing?).

Other:  For each group:  “share” with me a google document and/or google drawing that describes/shows the classes your group plans to implement, their fields and methods, how the classes will interact, and the current planned distribution of labor.  (It is not necessary that all coding is evenly distributed.  Some group members may have responsibilities other than coding, like java docs and/or project management.  On the other hand, all group members may want to be involved in everything:  coding, documentation AND project management.  That’s fine too.)  This shared document should be maintained/updated over the course of these remaining weeks as your plans/implementations evolve.  I will refer to it when grading your projects and I may leave my comments on it during the course of your planning so you can get feedback on your design as you go along.

WEEK

TOPIC

AFTER CLASS

13

Nov 18

Final Project

Work on final projects.  If your design document did not include a timeline of when each piece would be complete, add one by Thursday.  Also add your schedule of meeting times to the document. 

 

Nov 20

Final Project

Work on final projects.  Also see tentative grading rubric.

WEEK

TOPIC

AFTER CLASS

14

Nov 25

Graphs (adjacency matrix, adjacency list)

HW 19 (due Tues, Dec 2)

·         Complete FICSIT surveys distributed in class

·         Reading:  Chapters 14.1 and 14.2.

·         Exercises:  R-14.3, R-14.11 (part a only).  For fun (bonus?):  R-14.5

·         If G is a graph with m edges, how can we compute/express the sum of all the degrees of the nodes in G in terms of m?  Explain/justify/prove your answer is correct.

 

·         Would you use the adjacency list structure or the adjacency matrix structure in each of the following cases?  Justify your choice. 

a.      The graph has 10,000 vertices and 20,000 edges, and it is important to use as little space as possible.

b.      The graph has 1000 vertices and all 499,500 possible edges, and it is important to use as little space as possible.

c.       You need to answer the query areAdjacent(i,j) as fast as possible, no matter how much space you use.

Work on final projects

THANKSGIVING BREAK

15

Dec 2

Graphs (DFS, BFS, Minimum Spanning Tree)

HW 20 (due Thurs, Dec 4)

·         Please complete a course evaluation for our class.  Your feedback is really important to us:  http://evaluations.conncoll.edu.

·         Read 14.3 and 14.7

·         Exercise R-14.11 in the text, parts b and c (continued from HW 19 above).

·         For a chuckle that might help you remember the difference between DFS and BFS, see http://xkcd.com/761/.  (BTW, the comic is mouseover-sensitive.)

·         Trace through DFS, BFS, Prim’s and Kruskal’s algorithm on this graph. 

o   Start your DFS and BFS from vertex A.

o   For each of the four algorithms, list the nodes/edges in the order they are visited/added to the tree. 

o   For the MST algorithms, give the total weight/cost of the MST found. 

o   As always, explain and/or show your work. 

·         Bonus:  will Prim’s and Kruskal’s always return the same tree?  If so, explain.  If not, give a graph where they return different MSTs.

·         Note that in class we learned that Prim’s and Kruskal’s always find an MST of any input graph, but we never argued/explained why or how we know this to be true.  You can find such explanation in your reading.  BTW, knowing whether an algorithm for a problem actually always give the right answer or only sometimes gives the right answer is an important skill that you will learn if you take the algorithms course…

·         Work on final projects

Dec 4

Final Projects

HW 21 (due Thurs, Dec 11)

·         Please complete an online course evaluation if you haven’t already:  http://evaluations.conncoll.edu

·         Exercise R-14.16 in the text.

·         Start wrapping up final projects

16

Dec 9

Final Projects

Finish up final projects (remembering the mandatory final project questionnaire)

Final project submission due by noon on Tues, Dec 16

Final Exam is self-scheduled

 

* This Emerson quote has been slightly edited from its original form.