0.Introduction§

What we are doing today:

Administration stuff
Course mechanics
Course introduction (OpenDSA Chapter 1)

Administration stuff

Sign-in sheet (be sure to sign-in on one of them)
Get a copy of the syllabus
Force Add System:
- https://www.cs.vt.edu/F16Force-Adds,
- Password: 3114cas#, 3114bap#
Consent forms (please return at end of class)

Course Mechanics

Go over Syllabus
Course online support: Canvas, OpenDSA, Web-CAT

Canvas

We will use Canvas

Project specs and supporting documents
Link to Piazza forum
Post grades
Access to OpenDSA (online textbook)

OpenDSA

Access OpenDSA through Canvas->Modules
Lots of visualizations, exercises
Mastery-based approach
Homework due most days before class
- Small homework due at 1pm this Wednesday (Chapter 1)

Web-CAT

Get the updated plugin
Project submission
Support for junit testing
Auto-grading: Correctness, style

Milestones

4 projects, each with a 3-4 week life cycle
Most projects will have 3 milestones
- Intermediate deliverables with due dates
- First due at end of first week
- Second due about 2 weeks before due date
- Third due about 1 week before due date
Milestones designed to encourage incremental development
Last semester, milestones had the effect of boosting the final grade of the middle third of the class by about a full letter grade.

Course Introduction

Goals of this Course

Reinforce the concept that costs and benefits exist for every data structure.
Learn the commonly used data structures.
- These form a programmer's basic data structure "toolkit".
Understand how to measure the cost of a data structure or program.
- These techniques also allow you to judge the merits of new data structures that you or others might invent.

Role in the Curriculum

This course represents a transition between "learning to program" courses (CS 1114, CS 2114) and "content" courses.
To do well, you must be able to handle both
- Programming (we focus on projects with dynamic memory allocation and file processing)
- Content, theory and analysis
The projects test programming proficiencies
OpenDSA exercises test knowledge of how algorithms work
Exams test understanding of the theory (analysis)

Costs and Benefits

Each data structure has costs and benefits.
- Rarely is one data structure better than another in all situations.
Any data structure requires:
- space for each data item it stores,
- time to perform each basic operation,
- programming effort.
Only after a careful analysis of problem characteristics can we know the best data structure for a task.

Data Structure

A data structure is the physical implementation of an ADT.
- Each operation associated with the ADT is implemented by one or more subroutines in the implementation.
Data structure usually refers to an organization for data in main memory.
File structure: an organization for data on peripheral storage, such as a disk drive.

Logical vs. Physical Form

Data items have both a logical and a physical form.
Logical form: definition of the data item within an ADT.
- Ex: Integers in mathematical sense: +, -
Physical form: implementation of the data item within a data structure.
- Ex: 32/64 bit integers, overflow.

Logical vs. Physical Form (2)

Data Type

ADT

Type

Operations

Data Items

Logical Form

Data Structure

Storage Space

Subroutines

Data Items

Physical Form

Homework

Look at Canvas
Look at Piazza site, make sure you are enrolled there
Look at Project 1 spec: Will discuss next time
Do Chapter 1 exercises in OpenDSA by 1:00pm Wednesday

Before you leave today

Put your name and PID on sign-up sheet
If you need to add the course:
- Log in to https://www.cs.vt.edu/F16Force-Adds:
- Password: 3114cas#, 3114bap#
Please return consent form