0.1.1.1. Introduction¶

What we are doing today:

• Administration stuff
• Course mechanics
• Course introduction (OpenDSA Chapter 1)

0.1.1.2. 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)

0.1.1.3. Course Mechanics¶

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

0.1.1.4. Canvas¶

We will use Canvas

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

0.1.1.5. 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)

0.1.1.6. Web-CAT¶

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

0.1.1.7. 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.

0.1.1.8. 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.

0.1.1.9. 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)

0.1.1.10. 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.

0.1.1.11. 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.

0.1.1.12. 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.

0.1.1.13. Logical vs. Physical Form (2)¶

0.1.1.14. 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

0.1.1.15. 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