CSCI 136

Data Structures and Advanced Programming

Lectures | Labs | Resources

Home

Instructors: Duane A. Bailey (email: bailey), TPL 306
Aaron Williams (email: aw14), TBL 309A
Technical Support:Lida Doret (email: lpd2), TCL 205
Web Site:http://www.cs.williams.edu/~cs136 (this page!)
Course Calendar:https://tinyurl.com/cs136-calendar-f21
Lecture: Schow 030B, MWF 9-9:50am (§ 1), 10-10:50am (§ 2), or 11-11:50am (§ 3)
Labs:All labs are in Chemistry 217a
W 1:10-2:25pm, with Bailey (§ 7); or
W 2:35-3:50pm, with Williams (§ 8); or
R 9:55-11:10am (§ 4) or 1:10-2:25pm (§ 5), with Bailey; or
R2:35-3:50pm (§ 6), with Williams.
Textbook: Duane Bailey's Java Structures (Root-7 Edition), here (book resource page is here)
TAs: Milo Chang, Kary Chen, Samuel Chistolini, Diego Esparza, Gaurnett Flowers,
Nolan Holley, Emma Neil, Saul Richardson, and Ye Shu
TA Hours:Posted to the Course Calendar

Course Description

This course couples work on program design, analysis, and verification with an introduction to the study of data structures. Data structures capture common ways in which to store and manipulate data, and they are important in the construction of sophisticated computer programs. We will use the Java programming language in class and for the assignments.

Students will be expected to write several programs, ranging from very short programs to more elaborate ones. Since one of our goals in this course is to teach you how to write large, reliable programs composed from reusable pieces, we will be emphasizing the development of clear, modular programs that are easy to read, debug, verify, analyze, and modify.

Policies

All lab assignments will be graded (35% of the final grade) on design, documentation and style, correctness, and efficiency, in that order. Programs should be turned in electronically by 5pm on the due date, typically the Tuesday following lab.

Late programs will be accepted with an extreme penalty; we prefer an incomplete program over a late but otherwise perfect program. We will refuse to grade or debug programs that are poorly documented.

There will be a scheduled 75 minute midterm (25%) on the evening of Thursday, October 14. There will be an 2.5 hour final exam (30%) scheduled during the final examination period.

Over the semester, we expect participation. You will be graded (10%) based on that effort.

Syllabus

Course Syllabus
Department Honor Code and Computer Usage Policy

Lectures

Description | Labs | Resources

Date Topic Readings Associated Resources
Fri. Sept. 10 Introduction

The Syllabus

Duane: Lecture notes

Aaron: 01-intro.pdf, Hello.java, Knock.java.

Mon. Sept. 13 Java Basics Ch. 0, 1, and App. B Duane: Lecture 2 Notes and Java files (zipped)
Wed. Sept. 15 Organization

Duane: Lecture 3 Notes and Date.java (day-of-week calc.)

Aaron: 03-organize.pdf.

Fri. Sept. 17 Associations Ch. 1, 2

Duane: Lecture 4 Notes, Ratio.java, and Recipe.java.

Aaron: 04-associations.pdf, Check.java, Courses.java.

Mon. Sept. 20 Vectors Ch. 3, 4

Duane: Lecture 5 Notes, Die.java, Die2.java, Die3.java, WordFreq.java, gettysburg.txt.

Aaron: 05-vectors.pdf.

Wed. Sept. 22 Complexity Ch. 5

Duane: Lecture 6 Notes WordList.java

Aaron: 06-complexity.pdf, Count.java.

Fri. Sept. 24 Recursion Ch. 5

Duane: Lecture 7 Notes rec.java (recursion examples)

Aaron: 07-recursion.pdf, BinarySearch.java (start), BinarySearch.java (done).

Mon. Sept. 27 Recursion II Ch. 5

Duane: Lecture 8 Notes rec2.java (more recursion examples)

Aaron: nanorc (.nanorc), 08-recursion.pdf (updated), Binary.java, Combo.java.

Wed. Sept. 29 Lists I Ch. 7,9

Duane: Lecture 9 Notes

Aaron: See previous and next lectures.

Fri. Oct. 1 Mountain Day!
Mon. Oct. 4 Lists II Ch. 7,9

Duane: Lecture 9 Notes (again)

Aaron: 09-lists.pdf

Wed. Oct. 6 Lists III Ch. 7,9

Duane: Lecture 11 Notes

Aaron: 10-lists.pdf

Fri. Oct. 8 Sorting I Ch. 6

Duane: Lecture 12 Notes BinarySearch.java, Sorting.java.

Aaron: 11-sorting.pdf

Mon. Oct. 11 Reading Day
Wed. Oct. 13 Sorting II Ch. 6

Duane: Lecture 13 Notes, Sorting2.java

Aaron: 12-sorting.pdf, Sorting.java

Fri. Oct. 15 No Class
Mon. Oct. 18 Sorting with Comparators and Lambdas No readings.

Duane: Lecture 14 Notes, Sorting3.java StdIntComp.java pfIntComp.java DoIt.java

Aaron: 13-sorting.pdf

Wed. Oct. 20 Stacks Ch. 10

Duane: Lecture 15 Notes, MazeRunner.java maze

Aaron: 14-stacks.pdf (updated)

Fri. Oct. 22 Queues Ch. 10

Duane: Lecture15 (continued)

Aaron: 15-queues.pdf

Mon. Oct. 25 Ordered Structures Ch. 11

Duane: Lecture 16 Notes

Aaron: 16-ordered.pdf

Wed. Oct. 27 Iteration Ch. 8

Duane: Lecture 17 Notes

Aaron: 17-iterators.pdf, SimpleIterator.java, cool.ps

Fri. Oct. 29 Advanced Iteration

Duane & Aaron: Lecture 18 Notes, java iterator code

Mon. Nov. 1 Trees I Ch. 12

Duane: Lecture 19 Notes

Aaron: 19-trees.pdf

Wed. Nov. 3 Trees II Ch. 12

Duane: Lecture 19 Notes (continued)

Aaron: 20-trees.pdf, 20-gray.pdf.

Fri. Nov. 5 Trees III Ch. 12

Duane: Lecture 20 Notes

Aaron: 21-trees.pdf

Mon. Nov. 8 Priority Queues & Heaps Ch. 13

Duane: Lecture 20 Notes (continued)

Aaron: 22-bst.pdf (see 16-ordered.pdf for PQ and Heaps)

Wed. Nov. 10 Binary Search Trees I Ch. 14

Duane: Lecture 21 Notes

Aaron: 23-bst.pdf

Fri. Nov. 12 Binary Search Trees II Ch. 14

Duane: Lecture 21 Notes (continued)

Aaron: 24-advanced.pdf

Mon. Nov. 15 Binary Search Trees III Ch. 14

Duane: Lecture 22 Notes

Aaron: 25-splay.pdf

Wed. Nov. 17 Maps & Dictionaries Ch. 15

Duane:

Aaron: 26-maps.pdf

Fri. Nov. 19 Hashing & Hashtables Ch. 15

Duane:

Aaron: 27-dictionaries.pdf

Mon. Nov. 22 Hashing & Hashtables Ch. 15

Duane:

Aaron: 28-hash.pdf

Laboratories

Description | Lectures | Resources

Date Topic Handout
September 14Lab 0: Setting up a Git and Java EnvironmentLab Handout, Viewing your grades.
September 21Lab 1: The Silver Dollar GameLab Handout
September 28Lab 2: RecursionLab Handout
October 5Lab 3: Linked Lists with Dummy NodesLab Handout
October 19Lab 4: Sorts of PetsLab Handout
October 26Lab 5: PostScriptLab Handout (revised)
November 2Lab 6: The Two Towers ProblemLab Handout
November 9Lab 7: Hex-a-PawnLab Handout, hexapawn.pdf
November 16Lab 8: Darwin!Lab Handout

Resources

Description | Lectures | Labs

Item
A sample midterm. (and solutions)
How to view your lab grades.
Java API Documentation (Version 11)
Java Tutorials
Duane's Incredibly Brief Intro to Unix and Emacs
Java Structures web site