General Information

Instructor:

Geoffrey Towell Park Science Building 526-5064 gtowell at brynmawr dot edu http://cs.brynmawr.edu/~gtowell

Lecture Hours: Tuesday / Friday 1:10-2:30
Room: Park 25
Lab: Friday 2:40-4:00
Office Hours: 4-6pm Wednesday and Thursday
Office hours will be by zoom. Meeting code: 232 840 6920. I have provided the password in email

Course Description: An introduction to the fundamental data structures of computer science: lists, stacks, queues, trees, Binary Search Trees, graphs, sets and their accompanying algorithms. Principles of algorithmic analysis and object reasoning and design will be introduced using mathematical techniques for the notions of both complexity and correctness.

---

Text

There will be no official textbook for this class. The following are pretty good books on Data Structures. The first of these I will refer to in the Syllabus with chapter references. I will not do so for the other books. You will only be responsible for material discussed in class. These books should only be used to provide additional viewpoints and alternate explanations.

---

Important Dates

• Sep 8, First lecture
• Oct 6, First Midterm
• Second MidtermNov 3 Nov 6 TBD
• Spring 2020 final All of the examples will follow this general format.
• In class on Friday Oct 2 I handed out a very brief review sheet. Here is that sheet along with answers for most of the questions.
• Midterm Makeup part 3 Midterm make question 3 is here. This must be handed in by the start of class of Nov 3

instructions for taking the final Note these instructions will not be truly final until Dec 12, not will the exam be available before then

A set of practice questions

Answers to the review questions

Final Exam (login required)

---

Assignments

There will 10-11 weekly homework assignments. Homework will be electronically submitted. All work must be turned in by the due date or it will not be considered. That said, you have 3 (three) 24 late passes to be used at your discretion during the semester. To use a late pass you merely have to send me an email saying that you intend to use a late pass. This email MUST be sent prior to the due date. (I have received email with time stamps less than one minute before the due date.) Approval is automatic. You can use more than one late pass on an assignment. These late passes are intended to give you a little scheduling flexibility. For major issues requiring more than 24 hours, talk to me and/or your dean.

Despite my best efforts, homeworks may have sections that are not quite correct. If you find one, let me know. If I agree that the issue is an issue, bonus points will be awarded as follows:

3 points for the first issue reported
2 points for the second issue reported
1 point for the third issue reported

Ordering is based on date of email recipt. One bonus per person per assignment.

All assignments must abide by the following standards

• 206 Design Principles
• 206 Code Formatting Standards

Posted code samples will adhere to these standards. (Code shown in class may not so that it can fit on screens)

In addition, all assignments must be accompanied by a README file. See the file for a description of the expected contents.

1. Getting started Due Sep 17, 11:59 pmSep 18, 11:59pm due to issues with Lab.
2. Zip Codes using Arrays Due Sep 24, 11:59pm
3. Zip Codes using ArrayList Due Oct 1, 11:59pm
4. Counting Words Due Oct 15, 11:59pm
5. Working with Stacks Due Oct 22, 11:59pm
6. Priority Queues Due Oct 30, 11:59pm Nov 2, 11:59pm
7. Sudoku with recursion Due date TDB
8. Quicksort Due date TDB
9. BabyNames Wed Dec 2
10. EXTRA CREDIT: The towers of Hanoi, home edition.
11. Babies in trees -- rock-a-bye?? Fri Dec 11

---

Labs

1. Sep 11
2. Sep 18
3. Sep 25
4. Oct 2
5. Oct 9
6. Oct 23
7. Nov 6 Also, to do this lab, and to be better at using VSC, you should read (and understand) My document on breakpoints in VSC
8. If you were not in class on Nov 6, rather than doing the lab that is struck out above, do the following:Nov 6

---

Lectures

• Week 0
  Course Overview
  Slides from Course overview
• Lecture 1; Sept 8
  
  • Lecture slides We only got to slide 22. Do not do anything with the homework/quizlet on slide 26.
  • BoundTest
  • inchworm
  • StringEquals class We did not get to this.
  • wrapper
  • caster
  • zoom recording (login required)
  • During the lecture I mentioned "Visual Studio Code" as the IDE (integrated development environment) I will expect you to be using this semester. This is not a requirement. If you are installing Java, get Java 11. Any version is OK, but I will assume Java 11. (The default on a Mac is Java 8, it is worth the effort to upgrade to Java 11.
• Lecture 2; Sep 11
  • Lecture slides We only got to slide 17.
  • StringEquals
  • Animal
  • Dog
  • Cat
  • Shelter
  • Student
  • File Open (read one line)
• Lecture 3; Sep 15
  • Lecture Notes
  • Opening files with try and catch and resources
  • Basic illustration of nested class (Not discussed in class)
  • Nested classes and method overriding.
  • breaking up strings using the split function of strings
  • Defining and using generic methods
  • Defining and using generic classes
• Lecture 4; Sep 18; ArrayList
  • Lecture Notes
  • Interface for ArraList
  • Implementation of ArraList This implementation includes code for add and remove which were in class exercises
  • Word Count example
• Lecture 5; Sep 22; HashTables
  • Lecture Notes In class we made it to slide 11
  • An interface for maps
  • Implementation of the interface
  • Reimplementation of word counter using Map206
  • Very simple hashtable
  • A Hashtable using separate Chaining Not discussed in class on Tuesday.
  • In class exercise: Get in Map206
    

            private ArrayList> underlying = new ArrayList<>();
            public V get(K key) {
              Pair pair = iContainsKey(key);
              if (pair!=null)
                  return pair.value;
              return null;
          }
          private Pair iContainsKey(K ky) {
              for (Pair pair : underlying) {
                  if (pair.key.equals(ky)) {
                      return pair;
                  }
              }
              return null;
          }
        

• Lecture 6; Sep 25; More HashTables
  • Lecture Notes
  • A Hashtable using separate Chaining
  • break up a web log line
  • Analyze a web log file
  • Reads words from a book
  • In class exercise to do insert on separate chaining hashtable where: table size is 7, keys are integers, h(t) = t % 7, Data: (0,a) (32,b) (39,c) (12,d) (14,e) (35,f) (27,g) (13,h) (15,i) (5,j) (12,k) (13,l) (4,m) (0,n) (35,o)
    The final table will be
    

          0 (0,n), (14,3), (35,o) 
          1 (15,i)
          2
          3
          4 (32,b), (39,c), (4,m)
          5 (12,k), (5,j)
          6 (27,g), (13,l)
        

  • In class exercise for linear probing where: table size is 13, all keys are integers, h(t) = t % 13, Data: (0,a) (32,b) (39,c) (12,d) (14,e) (35,f) (27,g) (13,h) (15,i) (5,j) (12,k) (13,l) (4,m) (0,n) (35,o)
    The final table will be
    

      0 (0,n)
      1 (39,c)
      2 (14,e)
      3 (27,g)
      4 (13,l)
      5 (15,i)
      6 (32,b)
      7 (5,j)
      8 (4,m)
      9 (35,o)
      10
      11
      12 (12,k)
    

• Lecture 7; Sep 29; Finish HashTables, Start Algorithm Analysis. Some Review too. We only made it to slide 8
  • Lecture Notes : We only made it to slide 8.
  • Inheritance and private variables
  • A class in the shakespeare example
  • Another Shakespeare class
  • Yet another Shakespeare class
  • The data file used for shakespeare
  • In class exercise to write the rehash function for a probing system, assuming no tombstones.

        private void rehash(int newSize) {
          Pair[] oldArray = backingArray;
          backingArray = new Pair[newSize];
          for (int i = 0; i < oldArray.length; i++) {
              if (oldArray[i] != null) {
                  put(oldArray[i].key, oldArray[i].value);
              }
          }
      }
    

• Lecture 8; Oct 2; Algorithm Analysis. Some Review too
  • Lecture Notes
  • Timing code
  • Counting primitive operations
• Lecture 9;Oct 9, Midterm recap; Sorted Array Lists
  • Lecture Notes
  • Comparing Strings
  • A sorted Array List
  • Sorted ArrayList v2 By extending ArrayList
  • Solution for Q4, not discussed in class
• Lecture 10; Oct 13: Classes, Abstract Classes, Stacks
  • Lecture Notes
  • Comparing Strings
  • A sorted Array List
  • Sorted ArrayList v2 By extending ArrayList
  • Geometric Object
  • Circle
  • Square
  • Regular Polygon
  • Square using Regular polygon
  • Interface for stacks
  • Stacks of Java Methods
  • Palindrome tester
• Lecture 11; Oct 16: Stacks
  • Lecture Notes
  • Interface for stacks
  • Stacks of Java Methods
  • Palindrome tester
• Lecture 12; Oct 20: Queues and Comparable
  • Lecture Notes
  • Interface for stacks
  • Rabbits
  • SAL with Comparable
  • Example with Comparable and Rabbits
  • Queue built on array
• Lecture 13; Oct 23: Priority Queues
  • Lecture Notes
  • Priority Queue Interface
  • Unordered Priority Queue
  • Ordered Priority Queue
  • Heap based priority Queue
  • Abstract class for priority Queue
  • The Vererable SAL class
  • Rabbits
• Lecture 14; Oct 27: Heaps, Recursion
  • Lecture Notes
  • Abstract class for priority Queue
  • Heap based priority Queue
  • A set of recursive methods
  • Towers of Hanoi
• Lecture 14; Oct 30: Recursion
  • Lecture Notes
  • A set of recursive methods
  • Towers of Hanoi
  • Midterm Makeup part 3 Midterm make question 3 is here. This must be handed in by the start of class of Nov 3
  • Towers of Hanoi extra Credit. Go to CS 231. Do the towers of Hanoi in less than 45 seconds using the Tower timing web app This will opportuntity will close in Mid November. Worth 5 exam points!!!
• Lecture 15; Nov 6: Recursion
  • Lecture Notes
  • A set of recursive methods
  • Towers of Hanoi
  • Recursive backtracking and breaking down words
  • Binary Search
• Lecture 16; Nov 10: Recursion, Sorting
  • Lecture Notes
  • Recursive backtracking and breaking down words
  • Binary Search
  • zoom recording (login required)
• Lecture 17; Nov 13: Sorting
  • Lecture Notes
  • zoom recording (login required)
  • Mini-Lab: For the set of numbers:
    

                  14, 6, 18, 2, 13, 7, 8, 9, 3, 17, 5, 10, 11, 12, 15, 19, 16, 0, 1, 4
                

    show all the steps of sorting this list using insertion sort and merge sort. See slides 5 (interactively built in the lecture) and 8. Just do it by hand. Send a picture of your steps to gtowell206@cs.brynmawr.edu
• Lecture 18; Nov 17: Linked Lists
  • Lecture Notes
  • Linked List Interface
  • Linked List Implementation
  • zoom recording (login required)
  • Mini-Lab: Write, by hand is fine, the remove function as defined in LinkedListInterface. (Remove is not fully implemented in the provided Linked List implementation. But be inspired by the code there.) Send a picture of your code to gtowell206@cs.brynmawr.edu
• Lecture 19; Nov 20: Doubly Linked Lists
  • In the code presented in the lecture, on slide 11 I missed a case where the node being deleted is the head of the linked list. To cover this case, immediately before return ret; add the lines:

                          if (curr==head)
                              head=curr.next;
                        

    I have NOT updated any of the linked materials with this change.
  • Lecture Notes
  • Linked List Interface
  • Linked List Implementation
  • Rabbit Implementation
  • SortedDLL
  • zoom recording (login required)
  • Mini-Lab: Write, by hand is fine, methods for addFirst and addLast for the SortedDLL class. These methods must keep things in sorted order.) Send a picture of your code to gtowell206@cs.brynmawr.edu
• Lecture 20: Trees
  • Lecture Notes We only got to slide 20.
  • Tree Interface
  • Linked Tree Implementation
  • zoom recording (login required)
  • Mini-Lab: Write, by hand is fine, an implementation of insertUtil. Send a picture of your code (or a cut and paste) to gtowell206@cs.brynmawr.edu
• Lecture 21: Trees, Part 2
  • Lecture Notes This is updated with the changes I made during class.
  • Tree Interface
  • Linked Tree Implementation
  • zoom recording (login required)
  • Mini-Lab: Write, by hand is fine, an implementation of removeUtil. Send a picture of your code (or a cut and paste) to gtowell206@cs.brynmawr.edu
• Lecture 22: Balanced Binary Trees
  • Lecture Notes
  • zoom recording (login required)
  • Mini-Lab: Draw the AVL BSTs that result from the following insertions/deletions. Show all rotations.
    • i 1000
    • i 500
    • i 750
    • i 625
    • i 560
    • i 590
    • i 400
    • i 300
    • i 600
    • i 200
    • d 560
    • d 590
    Send a picture of your code (or a cut and paste) to gtowell206@cs.brynmawr.edu
  • instructions for taking the final Note these instructions will not be truly final until Dec 12, not will the exam be available before then
  • A set of practice questions
  • Answers to the review questions

Course Policies

Communication

Attendance and active participation are expected in every class. Participation includes asking questions, contributing answers, proposing ideas, and providing constructive comments.

Please stay in touch with me, particularly if you feel stuck on a topic or assignment and can't figure out how to proceed. Often a quick e-mail, or face-to-face (via zoom in fall 2020) conference can reveal solutions to problems and generate renewed creative and scholarly energy. It is essential that you begin assignments early.

Grading

Grades will be awarded based on the number of points earned and according to the percentage breakdowns shown.

Homework	45%
Lab	5%
Midterms (2)	32%
Final exam	18%

Mid-terms will be in class (or possibly take-home). If take-home then the time to complete will be no more than 2 hours. Closed book, closed notes, no electronic devices unless otherwise instructed.

Incomplete grades will be given only for verifiable medical illness or other such dire circumstances.

ALL work submitted for grading should be entirely YOUR OWN (or that of a group if you are working in a group). Sharing of programs, code snippets, etc. is not permitted under ANY circumstances. That said, I encourage you to discuss assignments at an algorithmic level with other students.

Submission, Late Policy, and Making Up Past Work

No assignment will be accepted after it is past due.
No past work can be "made up" after it is due.

---

Links

---

Learning Accommodations

Students requesting accommodations in this course because of the impact of disability are encouraged to meet with me privately early in the semester with a verification letter. Students not yet approved to receive accommodations should also contact Deb Alder, Coordinator of Accessibility Services, at 610-526-7351 in Guild Hall, as soon as possible, to verify their eligibility for reasonable accommodations. Early contact will help avoid unnecessary inconvenience and delays.

This class may be recorded.

---

Created on July 2020. Subject to constant revision.