CS206: Data Structures, Bryn Mawr College

Douglas Blank
Computer Science Department
Spring 2013

Overview

This course provides an introduction to the fundamental algorithms and data structures of computer science: sorting, searching, recursion, lists, stacks, queues, trees, graphs, and dictionaries. It also provides an introduction to the analysis of algorithms. Prerequisite: CMSC 205 or 110, or permission of instructor.

General Information

Course URL: cs.brynmawr.edu/cs206
Instructor: Douglas Blank, 248 Park Science Building, 526-6501
Email: dblank (at) cs (dot) brynmawr (dot) edu
Web: cs.brynmawr.edu/~dblank
Office hours: Monday and Wednesday, 1-2pm and by appointment
Course Meetings: Tues and Thursdays, 2:15-3:45pm
Lab: Park Science Building, room 349
On-line course materials: moodle.brynmawr.edu
Lab Assistants:
  • Sundays, 3-5 PM (Maggie)
  • Mondays 7-9 PM (Esther)
  • Tuesdays 8-10 PM (Esther)
  • Thursdays 4-6 PM (Maggie)

Texts

Software

We will be using the language Java for this course. In addition, we will be using a series of environments for accessing Java, including:

We will be doing much of our work in Linux, and will gain understanding of the underlying mechanisms of compiling Java. For this, you will need a Linux account that I will provide. You (and the world) will also be able to access Java applets that you will write through a computer science computer (TBA).

Schedule (approximate, schedule may change)

WeekDatesTopicAssignment
1 Tue 01/22/2013, Thu 01/24/2013 Introduction, Lecture 1
Variables, Functions, and Loops, Lecture 2 		Assignment #1
2 Tue 01/29/2013, Thu 01/31/2013 Object-Oriented Programming, Lecture 3
Finding things, Lecture 4 		Assignment #2
3 Tue 02/05/2013, Thu 02/07/2013 Binary Trees, Lecture 5 Assignment #3
4 Tue 02/12/2013, Thu 02/14/2013 Review, and introduction to Graphs, Interactive Fiction Assignment #4: type in game code, and design a game
5 Tue 02/19/2013, Thu 02/21/2013 Abstractions, Lecture 6. Arrays and HashMap. Assignment #5: remove linked list data structures from game, and allow loading a game from a file
6 Tue 02/26/2013, Thu 02/28/2013 Files, Exceptions, and Abstractions: Lecture 7
Sorting Algorithms		 Finish Assignment #5
Sample Code from class, #1
7 Tue 03/05/2013, Thu 03/07/2013 Games, Review and Midterm
8 Tue 03/12/2013, Thu 03/14/2013 Spring Break!
9 Tue 03/19/2013, Thu 03/21/2013 Graphics, Applets, Unix, the Web, Compiling Java Assignment #7: Turn your game into an applet, like this. Additional details: Moving your game to the web. Also, if you have trouble with appletviewer, see these hints.
10 Tue 03/26/2013, Thu 03/28/2013 Applets, a review, Java Security Event-driven algorithms; Sample Applet
11 Tue 04/02/2013, Thu 04/04/2013 Final Text Adventure Games
  1. http://bubo.brynmawr.edu/~amastriann/
  2. http://bubo.brynmawr.edu/~bklewis/
  3. http://bubo.brynmawr.edu/~blin/games
  4. http://bubo.brynmawr.edu/~ebaelenkin/
  5. http://bubo.brynmawr.edu/~eschroeter
  6. http://bubo.brynmawr.edu/~ewilliam03/game.html
  7. http://bubo.brynmawr.edu/~jcoles01/Slendergame.html
  8. http://bubo.brynmawr.edu/~jserota/index.html
  9. http://bubo.brynmawr.edu/~kholladay/index.html
  10. http://bubo.brynmawr.edu/~kkury/index.html
  11. http://bubo.brynmawr.edu/~kshrestha/play.html
  12. http://bubo.brynmawr.edu/~kvenugopal/index.html
  13. http://bubo.brynmawr.edu/~lobrien/GameApplet.html
  14. http://bubo.brynmawr.edu/~mkasahun/index.html
  15. http://bubo.brynmawr.edu/~mneuburger/game/textadventure.html
  16. http://bubo.brynmawr.edu/~plu/public.html
  17. http://bubo.brynmawr.edu/~yhuang/index
  18. http://bubo.brynmawr.edu/~yzhang03/index.html
Stacks and Queues (Lafore, chapter 4)
Workflow
 Assignment #8
12 Tue 04/09/2013, Thu 04/11/2013 Stacks, Queues, and Deques (Part 1)
Stacks, Queues, and Deques (Part 2)		 ExprCompute.java - example code using a Stack to implement an postfix expression evaluator
Node.java
DoubleLinkList.java
13 Tue 04/16/2013, Thu 04/18/2013 Graph Theory
Designing Objects
 Chapter 13; Work on project
14 Tue 04/23/2013, Thu 04/25/2013
  1. Implementing and Extending Class Hierarchies
  2. Inheritance, Abstractions, and Interfaces
Work on project
15 Tue 04/30/2013, Thu 05/02/2013
  1. Common Errors
  2. Review
Projects

Other dates of interest in Spring 2013:

Classes Begin Tuesday, January 22, 2013
PE Classes Begin Monday, January 28, 2013
Last day to drop a fifth class Friday, February 8, 2013
Last day to sign up for Credit/No Credit for Semester classes Friday, March 1, 2013
Spring Vacation Begins (after last class) Friday, March 8, 2013
Spring Vacation Ends (at 8:00am) Monday, March 18, 2013
Preregistration begins Monday, April 8, 2013
Preregistration ends Friday, April 19, 2013
Last Day of Classes Friday, May 3, 2013
Review Period Starts Saturday, May 4, 2013
End of Review Period Monday, May 6, 2013
Examination Period (Start) Tuesday, May 7, 2013
Final examinations end for seniors (@ 12:30pm) Saturday, May 11, 2013
Examination Period (Ends at 12:30pm) Friday, May 17, 2013
Commencement Saturday, May 18, 2013

Grading

Final grades will be calculated as a weighted average of all grades according to the following weights:

Written work: 50%
Midterm Exam: 20%
Final Exam: 20%
Project: 10%
dblank (at) cs (dot) brynmawr (dot) edu