CS 445: Data Structures

Fall 2017

General Information

Instructor

Lectures

  • A (#11206/13398)
    • M/W 3:00–4:15
    • BENDM 318
  • B (#22768/22770)
    • T/H 11:00–12:15
    • BENDM G29

Teaching Assistants

  • Aaron Tamenne (grader)
  • Alec Magnani
  • Anthony Sicilia
  • Evan Stephenson
  • Jon Rutkauskas
  • Jordan Carr
  • Marcus Dubreuil
    • Email: mld130@pitt.edu
    • OH: SENSQ 5806
      M 1:00–3:00
    • CRC?: SENSQ 5710
      M/W/F 9:00–10:00
      W 2:00–3:00
      H 11:00–12:00

Recitations

  • A1 (#11207/13399)
    • Alec Magnani
    • SENSQ 6110, M 1:00–1:50
  • A2 (#11709/19366)
    • Jordan Carr
    • SENSQ 5505, F 10:00–10:50
  • A3 (#27115/27163)
    • Jon Rutkauskas
    • SENSQ 5505, H 4:00–4:50
  • B1 (#22769/22771)
    • Anthony Sicilia
    • SENSQ 5505, T 3:00–3:50
  • B2 (#23213/23212)
    • Marcus Dubreuil
    • SENSQ 6110, W 1:00–1:50
  • B3 (#25722/25721)
    • Evan Stephenson
    • SENSQ 6110, H 9:00–9:50

Grading

  • 45% Exams:
    • 25% higher grade
    • 20% lower grade
  • 39% Assignments:
    • 9% each, top four grades
    • 3%, lowest grade
  • 10% Top Hat:
    • 3.5% attendance
    • 6.5% lecture questions
  • 6% Recitation:
    • 3% quizzes
    • 3% lab attendance

Course Description

This course emphasizes the study of the basic data structures of computer science (e.g., bags, lists, stacks, queues, trees) and their implementations using the Java language. We will cover objects and reference variables, as well as programming techniques that use recursion. Students will be introduced to various searching and sorting methods and will develop an intuitive understanding of the complexity of algorithms.

Textbook

Frank M. Carrano and Timothy M. Henry. Data Structures and Abstractions with Java (4th Edition). Pearson, 2014.

ISBN 0-13-374405-1

Online textbook resources available here.

Top Hat

Students must subscribe to Top Hat, the platform we will use for lecture participation. Please see Lectures for instructions.

Course Policies

Course Communications

The instructor will periodically post updates to the course website. It is each student’s responsibility to regularly monitor these updates.

The instructor and TA will periodically email enrolled students with announcements. Students must check their Pitt email at least once per day to ensure these announcements are received.

When contacting the course staff via email, messages must be addressed to (or CC) both the instructor and the TA. Email subject should be prefaced with “[445]”.

Academic Integrity

All assignment submissions must be the sole work of each individual student. Students may not read or copy another student’s solutions or share their own solutions with other students. Students may not review solutions from students who have taken the course in previous years. Submissions that are substantively similar will be considered cheating by all students involved, and as such, students must be mindful not to post their code publicly. The use of books and online resources is allowed, but must be credited in submissions, and material may not be copied verbatim. Any use of electronics or other resources during a quiz or examination will be considered cheating.

Cheating in this course will result in a report to the appropriate school and/or university authority. The instructor will impose a grade of F for the course, and additional sanctions may be imposed by school or university authorities.

Please read, understand, and abide by the Academic Integrity Code for the School of Arts and Sciences.

Lecture Attendence

Students are encouraged to attend all lectures, which frequently include material that is not directly taken from the text. If a student misses a lecture, he/she is still responsible for the material covered and is advised to acquire notes from a classmate.

Respectful Discussion

This course may include open discussion or other interactions among students. To allow all participants to express their viewpoints, all discussion must remain civilized and respectful, and participants must avoid comments and behaviors that disparage others. A student who feels their viewpoints are not being respected is encouraged to contact the instructor, who will work to correct the situation without revealing the student’s specific concerns to the rest of the class. A student in this situation who does not feel comfortable contacting the instructor directly is encouraged to contact the TA, who will uphold the same degree of confidence in relaying the issue to the instructor.

Audio/Video Recordings

To ensure the free and open discussion of ideas, students may not record lectures, discussion or other course activities without the advance written permission of the instructor. Any recording properly approved in advance can be used solely for the student’s own personal use.

Copyrighted Materials

All course material is subject to copyright, including notes, slides, assignments, and solutions. Students are allowed to use the provided material only for personal use, and may not share the material with others, including posting the material on the Web or other file sharing venues.

Collaboration

We believe that students should be able to distinguish between helping one another understand the core concepts of the course material and cheating. We encourage students to discuss the content of the course in ways that will improve understanding without violating academic integrity, such as clarifying the objective of an assignment or discussing general solution tactics.

Late Assignments

All assignments specify a precise due date and time. Late assignments will not be accepted. Students must ensure they understand each assignment’s submission procedure in advance of its deadline to ensure that submission difficulties do not cause an assignment to be rejected.

Grade Records

All graded materials that a student receives back should be saved in until after the term has ended and he/she has received and accepts his/her final grade. In this way, any grade discrepancies can be easily resolved.

Grade Appeal

An evaluation grade can be appealed up to two weeks after it has been returned. After this point, no appeals will be considered. The goal of a grade appeal is to ensure a fair and consistent score. Thus, a score will not be adjusted on an issue of partial credit if the awarded points are consistent with the grading policy adopted for the class as a whole.

When appealing a grade, first contact the grader: email (CC'ing the instructor) for assignments, or return the hard copy for quizzes. If the grader does not find any mistakes made in the original grade, and is unable to clarify adequately the reasons for any assessed penalties, directly contact the instructor describing why you feel the assignment was graded unfairly. The entire assignment will be re-graded by the instructor, so the score may increase, remain the same, or even decrease.

Make-up Exams and Quizzes

Students must be present for all exams and quizzes. Make-up exams will be given in the event of a documented emergency. The instructor must be informed of the emergency in advance of the missed exam. Missing an exam or quiz under any other circumstances will result in a score of 0.

Students with Disabilities

If you have a disability for which you are or may be requesting an accommodation, you are encouraged to contact both your instructor and Disability Resources and Services, 140 William Pitt Union, 412-648-7890, drsrecep@pitt.edu, as early as possible in the term. Disability Resources and Services will verify your disability and recommend reasonable accommodations for this course.

Religious Observances

In order to accommodate the observance of religious holidays, students should inform the instructor (by email, within the first two weeks of the term) of any such days which conflict with scheduled class activities.

Lectures

Top Hat

Top Hat will be used for attendance, lecture slides, and in-class questions. Sign up at tophat.com using the appropriate join code below.

Section Join code
A (M/W @ 3) 463174
B (T/H @ 11) 327521

Schedule

Students are responsible for reading assigned materials prior to the lecture in which they will be discussed. Unless otherwise specified, readings are from Carrano & Henry.

This schedule is subject to change.

Lec. A Date B Date Topics Readings
1 8/28 8/29 Designing I: Classes and objects
Appx. C
2 8/30 8/31 Designing II: Composition and inheritance
Prelude
Appx. D
9/04 No class: Labor Day
3 9/06 9/05 Designing III: Polymorphism and generics
Java Interl. 1
Java Interl. 3
Java Interl. 7
4 9/11 9/07 Bag I: Abstract data type
Ch. 1
5 9/13 9/12 Bag II: Array implementations
Ch. 2
6 9/18 9/14 Bag III: Linked implementations
Ch. 3
7 9/20 9/19 Algorithm analysis
Ch. 4
8 9/25 9/21 Stack I: Abstract data type
Ch. 5
9 9/27 9/26 Stack II: Implementations and analysis
Ch. 6
10 10/02 9/28 Recursion I: Basic recursion
Ch. 7
Ch. 18.0–18.7
11 10/04 10/03 Recursion II: Divide & conquer
Ch. 7
Ch. 18.8–18.13
12 10/10 10/05 Recursion III: Multiple recursion and backtracking
Ch. 7
10/10 No class: Fall break
13 10/11 10/12 Sorting I: Selection and bubble sorts
Java Interl. 3
Ch. 8.0–8.8
14 10/16 10/17 Sorting II: Insertion sort and shellsort
Ch. 8.9–8.25
15 10/18 10/19 Sorting III: Merge sort and quicksort
Ch. 9.0–9.19
16 10/23 10/24 Midterm exam review
Study Guide
17 10/25 10/26 Midterm examination
18 10/30 10/31 Sorting IV: Analyzing quicksort
Ch. 9.0–9.19
19 11/01 11/02 List I: ADT and array implementations
Ch. 12–13
20 TBA 11/07 List II: Linked implementations and analysis
Ch. 14
21 11/06 11/09 Midterm exam post-review
22 11/13 11/14 Iterators and iterable
Java Interl. 5
Ch. 15
23 11/15 11/16 Tree I: ADT and representation in memory
Ch. 23–24
24 11/20 11/21 Tree II: Implementations of operations
Ch. 23–24
11/22 11/23 No class: Thanksgiving break
25 11/27 11/28 Queue ADT and implementations
Ch. 10.0–10.18
Ch. 11.0–11.33
26 11/29 11/30 Binary Search Tree
Ch. 23.29–23.32
Ch. 25
27 12/04 12/05 Priority Queue ADT and implementations
Ch. 10.19–10.23
Ch. 11.34
Ch. 23.33–23.35
Ch. 26
Heap visualization
28 12/06 12/07 Final exam review
Study Guide
12/13 Final examination A (4:00)
12/14 Final examination B (8:00)

Recitation materials

Lab materials are distributed via Box. Login to Pitt Box to view the materials.

This schedule is subject to change.

Lab Dates Topic
8/28–9/01 No recitation
1 9/05–9/11 Java from command line, packages
2 9/12–9/18 Bag client
3 9/19–9/25 Bag implementation
4 9/26–10/02 Algorithm analysis
5 10/03–10/10 Recursion
Q1 10/11–10/17 Quiz 1
6 10/18–10/24 Quiz 1 review
7 10/25–10/31 Divide and conquer
8 11/01–11/07 Sorting improvements
9 11/08–11/14 List client
10 11/15–11/21 Iterators
Q2 11/27–12/01 Quiz 2
11 12/04–12/08 Tree traversals

Assignments

Assignment materials are distributed via Box. Login to Pitt Box to view the materials.

All deadlines are 11:59 PM.

Future assignments are subject to change.

Assignment Description Assigned Due
A1 Data structure implementation 9/14 9/28
A2 Stack client 9/28 10/12
A3 Recursive backtracking 10/12 11/02
A4 ADT design 11/02 11/16
A5 Complex data structure implementation 11/21 12/07