COM 212 Fall 2022
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 1:15 to 2:30 in NLH 214 |
||||||||||
|
Professor: |
Christine
Chung, PhD cchung@conncoll.edu New London Hall
220 Office
hours: Sign
up for an available time slot. |
||||||||||
|
Grading: |
|
||||||||||
|
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 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:
·
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).
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 SVPA@conncoll.edu, make an appointment with the
Confidential Advocates at http://bit.ly/ConnCollSVPA 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 titleix@conncoll.edu.
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: https://forms.gle/BQecmVdK8Bg1sv5P7. 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 (ngarrett@conncoll.edu)
or Patricia Dallas (pdallas@conncoll.edu).
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 http://write.conncoll.edu/ or by emailing the
Writing Center at writingcenter@conncoll.edu; 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 sas@conncoll.edu.
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
conncoll.edu/equity-inclusion/preferred-name-faq/ or email GSP@conncoll.edu.
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 gsp@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 |
Tues |
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: http://download.oracle.com/javase/tutorial/getStarted/cupojava/win32.html
ii.
For Mac: https://www.instructables.com/Hello-World-in-Java-on-Mac-OS-X/
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) |
|
Thurs |
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! |
|
|
WEEK |
DATE |
TOPIC |
AFTER
CLASS |
|
2 |
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) Exercises: · 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. |
|
|
Thurs |
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 Exercises: ·
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 HighArray.java 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. |
|
WEEK |
DATE |
TOPIC |
AFTER
CLASS |
|
3 |
Tues Sept 13 |
Project
1: Arrays, binary search |
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. Exercises: ·
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? |
|
|
Thurs 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. Exercises:
·
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: GameEntry.java and Scoreboard.java. 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. |
|
WEEK |
DATE |
TOPIC |
AFTER
CLASS |
|
4 |
Tues 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. |
|
|
Thurs Sept 22 |
Project
2: Linked Lists (Files needed: GameEntry.java,
Node.java) |
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. |
|
WEEK |
DATE |
TOPIC |
AFTER
CLASS |
|
5 |
Tuesday Sept
27 |
Doubly Linked Lists, Circularly
Linked Lists |
HW 8 (due Thurs, Sept 29) Reading: ·
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. |
|
Thurs Sept 29 |
Stacks |
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. |
|
|
WEEK |
DATE |
TOPIC |
AFTER CLASS |
|
6 |
Tues Oct 4 |
Queues |
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. |
|
Thurs 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. |
|
|
WEEK |
DATE |
TOPIC |
AFTER
CLASS |
|
7 |
Tues Oct 11 |
Queues, cont’d |
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. |
|
|
Thurs Oct 13 |
Trees |
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) Exercises: ·
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. Other:
·
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 15-18 |
FALL
BREAK |
||
|
WEEK |
DATE |
TOPIC |
AFTER
CLASS |
|
8 |
Thurs Oct 20 |
Binary Search Trees (BSTs) |
Midterm Exam due
Tues, Oct 25. Submit them in hard copy
in class or in my office, NLH220. |
|
|
|
|
|
|
WEEK |
TOPIC |
AFTER CLASS |
|
|
9 |
Tues 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.
|
|
|
Thurs Oct 27 |
(Files needed: traverse.txt,
displayTree.txt,
TreeApp.java) |
HW 13 (due
Tues, Nov 1) Reading: ·
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! Exercises: ·
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.) Other: ·
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. ;) |
|
WEEK |
TOPIC |
AFTER
CLASS |
|
|
10 |
Tues 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. Other:
Continue meeting with your partners to work on project 4. Please follow partnering guidelines! |
|
|
Thurs Nov 3 |
No Class |
All-College Symposium |
|
WEEK |
TOPIC |
AFTER CLASS |
|
|
11 |
Tues 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) |
|
|
Thurs 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) |
|
WEEK |
TOPIC |
AFTER
CLASS |
|
|
12 |
Tues |
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. |
|
|
Thurs Nov 17 |
Hash Codes and Final
Project |
|
|
WEEK |
TOPIC |
AFTER CLASS |
|
|
13 |
Tues 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 |
THANKSGIVING
BREAK |
||
|
14 |
Tues 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 http://xkcd.com/761/. (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.) |
|
Thurs 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: http://moodle.conncoll.edu/. |
|
|
WEEK |
|
|
|
|
14 |
Tues Dec 6 |
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: http://moodle.conncoll.edu ·
Work on your final projects. |
|
|
Thurs Dec 8 |
Start wrapping up final projects! (Remember the mandatory final project
questionnaire). |
||
|
15 |
Mon 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 |
|
