COM 212 Fall 2022
Data Structures

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:

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. 



Tuesdays and Thursdays from 1:15 to 2:30 in NLH 214



Christine Chung, PhD

New London Hall 220

Office hours:  Sign up for an available time slot.



Homework exercises (about 20 of them)


Participation (including posts to moodle forum)


Exams (midterm and final)


Programming Assignments


Final Project



TA lab sessions: 

Times TBA.  TA sessions are run by our 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, along with the course moodle page:  login at

·         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  (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:

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

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

·         BBEdit, Textmate, Smultron, others (Mac only)

·         In the second half of the semester, you will be permitted/encouraged to use an integrated development environment (IDE), like Eclipse, NetBeans, IntelliJ, or VS Code, if you prefer.

Required text

Data Structures and Algorithms in Java (5th or 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

Written homework 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 before the start of class via the moodle submission link.

·         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 lab usage requirement

You must log a total of 12 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.  To log these hours, go during regular TA 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. 

Final projects

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

*Emerson quote slightly edited from its original form

Other important info (which applies to all your classes) 

Credit Hour Definition

A semester course is normally equivalent to four credit hours.  Connecticut College complies with federal regulations defining the credit hour.  For each credit hour awarded, a course will provide an average of at least one hour of classroom or direct faculty instruction (class meetings, labs, review sessions, field trips, office hours, film screenings, tutorials, training, rehearsals, etc.) and at least two hours of out-of-class work (homework, preparatory work, practice, rehearsals, etc.) per week. 

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, falsifying data, misrepresenting class attendance, 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 may be referred to the college's Honor Council for resolution.

Title IX Statement

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 trained and required to report any incidents of gender-based discrimination, including discrimination based on gender identity, gender expression, and sexual orientation. This means that I cannot keep information confidential about sexual harassment, sexual assault, dating violence, stalking, or other forms of gender-based discrimination, and that I will report that information to the Title IX office, if it is shared with me.  However, the Title IX office typically only acts on formal complaints, and in response to notice from me will reach out to you to offer support and resources, and offer you the opportunity to file a formal Title IX complaint, which is up to you.  The Director of Sexual Violence Prevention and Advocacy and the SVPA Confidential Advocates can advise you confidentially as can Counseling Services and any of the College chaplains.  SVPA can also help you access other resources on campus and in the local community.  You can reach the Confidential Advocates at, make an appointment with the Confidential Advocates at or contact the SVPA Confidential Advocate ON Call 24/7 at 860-460-9194.  The student sexual harassment, dating violence, stalking, and non-discrimination policies are in the Sexual Harassment and Nondiscrimination Policy, 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. If you need to report an incident or have any questions about the policy, you can contact 860-439-2624 or

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. Its offices are located on the second floor of Shain Library. Students can make appointments by clicking on this link:  The ARC is open to the community Monday – Friday, 8:30 – 5:00 (evenings are by appointment only).  Students may continue to use the ARC as a quiet study space, though social distancing and masks are required at ALL times.  If faculty or students have any questions or concerns, they should contact Noel Garrett ( or Patricia Dallas (

Writing Center

The Roth Writing Center provides one-to-one peer tutoring (free of charge) to help student writers of all abilities during all stages of the writing process. If you're a confident, experienced writer, our tutors can help you to push your ideas and polish your style; if you're a relatively inexperienced and not-so-confident writer, they can help you to work on grammar or organization or whatever you need. Working with a tutor gives you the opportunity to share your work-in-progress with an actual reader so that you can get useful feedback on that work before you have to turn it in for a final grade. You can make an appointment by using the Google Calendar link on the Writing Center's website at or by emailing the Writing Center at; a new calendar of appointments will become available by the second week of each semester.

Office of Student Accessibility Services

Connecticut College complies with Section 504 of the Rehabilitation Act of 1973 and the Americans with Disabilities Act. If you have a documented disability and have been approved for academic accommodations, please have your Faculty Notification Letter emailed to me through the Student Accessibility online management system (AIM) and schedule a meeting during my office hours as early as possible in the semester so that we can discuss the logistics of your accommodations. If you are not approved for accommodations, but have a disability requiring academic accommodations, or have questions about applying for accommodations, please contact Student Accessibility Services at 860-439-5428 or

Classroom Recording

With the exception of those granted accommodations through the Office of Student Accessibility Services, students are prohibited from audio, video, or photographic recording during class periods or out-of-class meetings with the instructor without explicit permission from the instructor. Recordings approved in this manner may not be shared in any form without permission of the instructor. Violations of this policy shall be considered an Honor Code violation.

Office Hours

Office hours provide students with additional opportunities to review or ask questions about the class discussions and assignments. Connecticut College faculty encourage students to go to office hours so they might learn about your interests, both inside and outside the classroom. In addition to talking about class material and assignments, you may find you share common interests, such as music, books, hobbies, and movies. If a professor knows your interest, they may inform you about campus programs and activities or other opportunities like fellowships and scholarships. Most importantly, a professor who knows their students writes better letters of recommendation. Successful students at Connecticut College make time to go to their professors’ office hours. All Connecticut College faculty are required to have office hours on their syllabus and posted on their office door.  If you cannot make your professor’s scheduled office hours, contact your professor to set up an appointment. 

Respecting Personal Pronouns and Identity

Everyone deserves to be referred to and addressed in accordance with their personal identity. As a faculty member, I am committed to ensuring my classroom affirms people of all gender expressions and gender identities. In this course, we will only use the name and pronouns of each individual's choosing. The repeated usage of incorrect names and/or pronouns are against Connecticut College policy and may constitute a T9 policy violation as well as a violation of state and federal law. In the classroom, be assured that you will always be referred to by the name and pronouns you choose. If you go by a different name than your legal name, Connecticut College has a process to change your preferred name on most campus systems. If you want to learn more about this process go to or email Students, faculty and staff are now able to choose and share their pronouns within the college community by using the Preferred Name/Pronouns link on the navigation menu in CamelWeb and the CC Mobile App.  Your gender pronouns will appear in the internal directory located in CamelWeb and the CC Mobile App. If none are selected, or if “Not Applicable” is selected, no pronouns will display. Enrolled students’ gender pronouns will also display in Moodle for instructors via the class participants page.  Pronouns are one way to affirm someone’s gender identity, but they are not necessarily indicative of a person’s gender identity. Commonly, they/them is a gender-inclusive pronoun used by a variety of identities. However, while some people use they/them, others may use pronouns like ze/zem, xi/xim, he/him, she/her, any combination of those and/or many others. They may even reject pronouns altogether and use their name in place of pronouns. Remember to ask for pronouns, listen, and then respect the gender identities of those around you by using the proper terminology. If you have any further questions or you want to learn more about gender & sexuality, please do not hesitate to contact the Director of Gender & Sexuality Programs at


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. 






Aug 30

Intro, course logistics

HW1 (due on Thurs, Sept 1): 

·         Getting started

a.       [You may skip this first step if you have a mac, since Java should already be installed.]  Install Java (JDK 17) on your own machine or go to NLH 214 during a TA session, and learn how to run it on a lab machine there.  When installing Java, be sure to install JDK version 17 and follow the installation instructions.   

b.      Write the Hello Universe program from page 2 of the text.  Here are a couple useful links that will walk you through this homework:

                                                               i.      For Windows:

                                                             ii.      For Mac:

c.       Compile and run your working program for a TA so that they can check you off for completing this HW!  TA sessions for this week are:  Tuesday 7:30-9pm and Wednesday 7-9pm in NLH 214

·         Reading

1.       The course website

2.      Chapter 1.1 pages 2-4 and pages 20-37 (in the 5th edition of GT this is roughly pages 2-6 and 20-37)

Sept 1

Java basics, Arrays

HW2 (due on Tues, Sept 6 via moodle by 1:05 pm):

·         Complete the worksheet from class practicing with arrays using methods with return values and input parameters (if you didn’t finish it in class already).

·         Code up the method from your worksheet that returns the max value of an array.  Test it by calling it from a main method.  [See your class notes for an example of how to call a method from the main method.  Remember the cube() function that I put on the board?]  Add comments to indicate that you understand how/why it always returns the right answer.  [It is a good idea to take the time to code up and test all the code we write in class to review, make it concrete, and check it for errors.  But it is not required.]

·         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 (which is section 1.3 in the 5th edition of GTS).

·         Textbook exercise(s)

1.       Complete exercise R-1.5 on page 55 of GTS (it is exercise R-1.12 in the earlier edition of GT).  You may write your 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).

2.      For one bonus point each: also complete exercises R-1.6 and R-1.7 (R-1.13 in the earlier edition of GT)

·         Explain your solution by writing on the print out or commenting the code. 

·         Upload everything in pdf/jpg format (either typed or hand-written) to the moodle submission link for HW2.  Remember to explain/narrate your solutions for full credit!






Tues Sept  6

Arrays, cont’d, Run-time analysis

HW 3 (due on Thurs, Sept 8 via moodle by 1:05 pm)

Reading:  pages 163-171 in GTS (or roughly pages 169-185 in the 5th edition)


·         Write a method that takes an array of integers and returns an array with the integers in reverse order.  Code up and test this method, as you did for the HW2 worksheet.  Give the run-time complexity of your algorithm in big-O notation.

·         R-4.8 (or R-4.13 in the 5th edition).  Start by writing each function in big-O notation.  Explain all your work as always.

Tutorial (due before Mon night, Sept 12):  go to NLH214 and use the lab machines there to complete the first 5 pages of this Linux Tutorial.  (If the lab machine is currently running Windows you will need to reboot it so it loads up Linux.)  Make sure a TA witnesses that you are working on the tutorial and notes that you’ve completed it using the Linux Usage Log form.  Let me and a TA know if you have any questions/problems as you proceed through this tutorial.  Since you will complete this on the Linux machines in the lab, this time will also count toward your total required Linux usage time of 12 hours.


Sept 8

Parallel arrays, Object-oriented programming review, sorting an array (Insertion sort), preview of Project 1

HW 4 (due on Tuesday, Sept 13 via moodle by 1:05 pm)

Reading:  both packets that were handed out in class about constructors and OOP


·         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.

·         Complete the written exercises in the pages of the packet from above reading (“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. 

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

Linux Tutorial (see above) due by Mon night, Sept 12.







Sept 13

Project 1:  Arrays, binary search
(Files needed:,

HW 5 (due Thursday, Sept 15):

Reading:  Read chapters 3.1.1 (Keeping High Scores in an Array).  Also read: this review of binary search.


·         Sorting.  See worksheet from class.  Code up, test, and analyze the run-time of Bubble 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.)

·         Searching.  Once you have your sort function working, try implementing a binary search function based on the above reading link.

·         Parallel sorting.  Use your sorting algorithm to sort the ages[] array from class, which was 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 Bubble 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?



Sept 15

Two-dimensional arrays, Arrays of objects

HW6 (due Tues, Sept 20)

Reading:  3.1.5 (2D Array for Tic Tac Toe) of GT text. Introducing our next data structure…  Linked Lists!  Read Chapter 3.2 of GTS text. 


·         C-3.23 on page 146 of GT text (C-3.6 in the 5th edition).  Hint: think 2D array…

·         Also complete the worksheet of five questions about the GameEntry and ScoreBoard classes we looked at in class (see handouts).  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.

·         Finish writing the add(GameEntry e) method that we started in class for adding a new GameEntry object e into the array of high scores in the ScoreBoard class.  See if you can code it and test it using these starter code files: and  Note:  the reading assignment of HW5 covered this add() method, but after reading about it, try writing down your own version of the code rather than simply copying the book code.  Afterward, you can go back and check your code against the book code and note any differences.

·         Continue working on Project 1.  It is due in one week.







Sept 20

Linked Lists

Project 1 due by 1:05 pm on Thursday, Sept 22. 

Late (grace) deadlines:  -1% if submitted by midnight, and -2 percentage points if submitted by Friday at 1:05.  Minus 10% per day after that.



Sept 22

Project 2:  Linked Lists

(Files needed:,

HW 7 (due Tues, Sept 27)

·         Reading:   

o   Review/re-read Chapter 3.2 of GTS text.

o   Read Chapter 3.4 of GTS text (Doubly Linked Lists), which is chapter 3.3 in the 5th edition. 

·         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 have also created (or 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), or C-3.12 in the 5 edition.

Other assignments:

·         Continue work on Project 2, due in two weeks on Thursday before class.

·         Continue logging your linux usage time at TA sessions… 12 hours are required total, so aim for about 1 hour per week on average.






Tuesday Sept 27

Doubly Linked Lists, Circularly Linked Lists

HW 8 (due Thurs,  Sept 29)


·         Review Chapter 3.4 of GTS text (Doubly Linked Lists), which is chapter 3.3 in the 5th edition.

·         Read Chapter 3.3 of GTS text (Circularly Linked Lists), which is chp 3.4 in the 5th edition.

Exercises:  from page 147 of GT… complete C-3.26 and C-3.27 (C-3.10 and C-3.11 in the 5th edition), 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 on Thursday, Oct 6, before class.


Sept 29


HW 9 (due Tues, Oct 4):

·         Reading:  Chapter 6.1 in GTS (Stacks), which is chapter 5.1 in the older edition of the text.  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 (which is R-5.5 in the older edition) and C-6.22 (or C-5.10 in the older edition).  Also complete C-6.16 and C-6.34 for some fun bonus exercises!  (In the 5th edition these bonuses are C-5.4 and C-5.12.)

Other assignments:

·         Continue work on Project 2.







Oct 4


Project 2 due by 1:05 pm on Thursday, Oct 6.

Late (grace) deadlines:  -1% if submitted by midnight, and -2 percentage points if submitted by Friday at 1:05.  Minus 10% per day after that.


Oct 6

Project 3:  Stacks and Queues

HW 10 (due Tues, Oct 11):

·         Reading:  Chapters 6.2 and 6.3 in GTG (Queues and Deques, pronounced “decks”).  [Or 5.2 and 5.3 in the GT 5th edition.]

·         Exercises: Complete exercises R-6.9 & C-6.32.  [These are R-5.8 & C-5.9 in the GT 5th edition.]

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







 Oct 11

Queues, cont’d
Postfix notation

HW 11 (due Thurs, Oct 13)

·         Reading:  Review all assigned chapter 6 reading.

·         Exercises:  Complete C-6.24 [this is the same exercise as C-5.2 in the 5th edition of GT.]

·         Other:  try to have Parts A & B & (C or D) of Project 3 completed.



Oct 13


HW 12 (due Thursday, Oct 20)

Reading:  Chapters 8.1, 8.2, 8.4.1, and 8.4.3 in GTS (or 7.1, 7.2, and 7.3 in GT 5th edition)


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

·         Complete R-8.1, R-8.11, R-8.20 (or R-7.2, R-7.11, R-7.12 in the 5th edition)

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


·         Work on take-home midterm. The midterm is open-note, open-book, no computer.  Due in hard copy on Tues, Oct 25.

·         Continue work on Project 3 with your partners.










Oct 20

Binary Search Trees (BSTs)

Midterm Exam due Tues, Oct 25.  Submit them in hard copy in class or in my office, NLH220. 










Oct 25

BST delete and AVL Trees

Project 3 due Thurs, Oct 27.  Late deadline is now extended to Sunday night, Oct 30.  Until the late deadline, penalties are-1 point per day. 



Oct 27

Project 4:  Binary Trees

(Files needed: traverse.txt, displayTree.txt,

HW 13 (due Tues, Nov 1)


·         GTS chapters 8.3.1 (Implementing Trees) and 11.1 (Binary Search Trees).

·         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 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!


·         R-8.22 (aka R-7.15), and

·         R-11.2 & R-11.4, which say: “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.)


·         Make sure you’ve filled out your project 3 questionnaire on moodle in order for us to complete grading on your project submissions.

·         Vim Tutorial (due by end the of the semester): Spend at least two hours learning to use and/or using Vim, a powerful unix-based text editor used by some programmers.  The first hour or so will be just completing this Vim tutorial, courtesy TA Julia Proft ’15.  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.  The more you use Vim after this, the better you’ll get at it and the more you’ll enjoy it…  one day, you can impress your friends, family, and future employers with your esoteric (yet powerful) text-editing skills.  ;)






Nov 1

AVL trees, continued

HW 14 (due Tues, Nov 8)

Reading:  Chapters 11.2-11.3 of GTS (10.1-10.2 of the older edition).  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 (these are R-10.8, 10.9, and 10.10 in the older edition)

Other:  Continue meeting with your partners to work on project 4.  Please follow partnering guidelines!


Thurs Nov 3

No Class

All-College Symposium






Nov 8

Priority Queues and Heaps

HW 15 (due Thurs, Nov 10)

·         Reading:  Chapters 9.1 and 9.3 of GTS.  (Chapters 8.1 and 8.3 in the 5th edition)

·         Exercises:  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.  (R-8.5, 8.10, 8.18, 8.19 in the 5th edition.  Also, R-9.10 is not in the older edition.  It says: “At which positions of a heap might the largest key be stored?”)

·         Other:  Project 4 due (in hard copy and via moodle) by 1:05 pm on Tues, Nov 15.  Also: fill out the mandatory project 4 questionnaire (required for all students)



Nov 10

Array-based Heaps

HW 16 (due in one week on Thurs, Nov 17)

·         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(). 

o   Write code for the extractMin() method on a priority queue implemented using an array-based heap (as discussed in class).  You should include in your submission the 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.  Use these methods as convenient from your extractMin() function.  Another useful private helper method  to write and call from extractMin() will be a boolean method hasSmallerChild(int i), which returns True if the node at i has a child with a smaller key, and false otherwise.  This boolean function can be called as the condition of your while loop.  As always, comment your code to describe what is going on.

·         Other:  Project 4 due (in hard copy and via moodle) by 1:05 pm on Tues, Nov 15.  Also: fill out the mandatory project 4 questionnaire (required for all students)





Nov 15


Hash Tables and Final Project

HW 17 (due Tues, Nov 22)

·         Reading:  Chapter 10.2 (Which is 9.2 in the older edition.)

·         Exercises:  [A couple of these were done in class already, so you can just show the work/add explanation to what you did in class, then upload photos of the in-class worksheet.]  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: 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. 

·         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. 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.

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



Nov 17

Hash Codes and Final Project






Nov 22

Graphs (adjacency matrix, adjacency list)

HW 18 (due Tues, Nov 29)

·         Reading:  Chapters 14.1 and 14.2.  (Or 13.2 and 13.2 in the older edition.)

·         Exercises:  R-14.3 (13.2 in the 5th edition), R-14.11 (part a only) (R-13.8 in the 5th edition).  For fun (bonus?):  R-14.5 (aka R-13.3)

·         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?  Try some small example graphs to see what you come up with.  Explain/justify/prove your answer is correct in general in any undirected graph.


Work on final projects.  Also see tentative grading rubric.

Wed Nov 23-

Sun Nov 27




Nov 29

Graphs cont’d (DFS, BFS)

HW 19 (due Thurs, Dec 1)

·         Read 14.3 (or 13.3 in the older edition)

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

·         For a chuckle that might help you remember the difference between Depth-First Search and Breadth-First Search, see  (BTW, the comic is mouseover-sensitive.)

·         Work on your final projects (and work on logging your required Linux hours at the TA sessions this week, while you are at it!  In other words, work on your final project on the Linux workstations together.)


Dec 1

Graphs cont’d (DFS, BFS, Minimum Spanning Tree)

HW 20 (due Tues, Dec 6)

·         Trace through the DFS and BFS algorithms on the graph in Figure 14.1 on page 612 of the text.  (This is the same graph of CS research collaborators from the HW 18, Ex 14.3, a reprint of which was handed out in the sample solution in class.)

o   Start your DFS and BFS from Garg. For consistency and ease of grading, assume the set of neighbors of a vertex are always stored in alphabetical order by the author’s name.

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

o   After you do the trace and list the nodes, also draw the traversal tree for each trace.

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

·         Also complete exercise R-14.16 in the text.  (R-13.7 in the older edition.)

·         Bonus (this one is not very hard so you should go for it):  what kind of graph will have simultaneously the longest/tallest/skinniest possible DFS traversal tree and the widest/thickest/shortest possible BFS traversal tree?

·         Please complete a course evaluation for our class.  Your feedback is really important to me and the department and the school:







Dec 6

Final Projects

HW 21 (due Thurs, Dec 8)

·         Read 14.7 (or 13.6 in the older edition) of GTG text

·         Trace through Prim’s and Kruskal’s on this graph.  For Prim’s you can start from vertex (a).

·         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.  Will they always return trees of the same total weight/cost?

·         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…

·         Please complete an online course evaluation if you haven’t already:

·         Work on your final projects.


Dec 8

Final Projects

Start wrapping up final projects!  (Remember the mandatory final project questionnaire).



Dec 12-19

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

Final exams and final project submission due by noon on Mon, Dec 19