Outline 01: An Introduction to the Course

Held: Friday, 29 August 2014

On to Outline 02 - An Introduction to ADT Design.

Summary

We begin the course by considering the subject matter of the course and attempting an exercise in design.

Related Pages

Handout: Learning Outcomes
Handout: Academic Honesty
Reading: Designing Abstract Data Types
Reading: Designing Data Structures
Assignment 1: Introductory Survey
Assignment 2: Exploring an Expandable Array ADT
EBoard 1 (Source 1) (HTML 1)

Overview

About the course.
A few notes on academic honesty.
ADTs and data structures.
An exercise: Designing a stack ADT.

Administrivia

Welcome back to campus!
Yes, I'll be taking attendance for the first few days/weeks of class (but after all of the other preliminaries).
The department has a mailing list of events and opportunities in CS. Please let me know if you'd like to be on it
Don't forget that we have class on Monday, even though it is labor day.
The data structures reading for Monday is not yet available. It should be up later tonight.

Upcoming Work

HW 1 is due Sunday night at 10:30 p.m.
HW 2 is also due Sunday night at 10:30 p.m.
Readings for Monday:
- Designing Abstract Data Types
- Designing Data Structures

Extra Credit Opportunities

Academic

CS table today (and every Friday) at 12:10 in JRC 224A.

Peer Support

Men's Soccer Sunday at 3:00 p.m.
...

Miscellaneous

Second-year students get extra credit for doing the second-year science retreat. You should have gotten a notice about it.

Attendance

I would like to know
- What name to use for you in less formal situations. This will usually be your given name or a nick name.
- What name to use for you if I am addressing you by family name or last name.
- Your preferred gender pronoun.
- (Optional) Any upcoming events in which you are participating that you would like classmates to attend.
When I call your name, please answer using something like the following models.
- Hi. My name is Casey Smith. I prefer that you call me "Case" or "Mr. Smith". My preferred gender pronouns are he, him, and his.
- Hi. My name is Casey Smith. I prefer that you call me "Casey" or "Ms. Smith". My preferred gender pronouns are she and her."
- Hi. My name is Casey Smith. I prefer that you call me "Cay" or "Mx. Smith". My preferred gender pronouns are zi and zir.

About the Course

In considering these issues, you may also want to look at my goals for the course.

CSC 207, like CSC 151 and CSC 161, is about a lot of different but related things.
- It's a course about formalized problem solving, how you take a problem, formalize the problem, design a solution, express the solution in a formal language, and analyze the solution (and perhaps the problem).
- It's a course about algorithms, the instructions we write to solve problems.
- It's a course about abstract data types and data structures, the ways in which we organize information as we solve problems. (Our organization can have a significant impact on our algorithms.)
- It's a course in programming, the implementation of algorithms and data structures.
- And it's a course in software design, how you approach the problem of designing and linking together disparate parts to make a working program.
In exploring algorithms, we will
- Consider a few classic algorithms.
- Learn asymptotic analysis, a formal technique for comparing the running time or space usage of algorithms.
- Develop some general patterns of algorithm design.
- And, of course, design our own algorithms.
In exploring abstract data types and data structures, we will
- Consider a few classic ADTs and data structures
- Design our own ADTs and Data structures
- Develop a few general approaches to the design of data structures
- Consider ways to consider the efficacy of a data structure (typically in terms of the algorithm it serves)
- And, of course, implement a variety of ADTs and data structures
In exploring program design, we will begin your path on understanding object-oriented design. We will focus on the three foundations of OOD -
- Encapsulation - techniques for grouping related parts together and shielding them from the resting of the program.
- Inheritance - techniques for defining new things from old.
- Polymorphism - techniques for designing and writing things that work in multiple, related, contexts.
And yes, you'll learn how to program in Java.
We will also help you develop a variety of general skills in addition to problem solving - group work, thinking on your feet, communication, and more.

Thinking Broadly

From my perspective, CSC 207 is the real gateway to the major, the course in which you start to become a real computer scientist and/or a real programmer.
Yes, you've written programs, algorithms, and data structures in your previous courses, but your depth of analysis has been relatively shallow and your programs have been comparatively small.
Of course, our analysis won't be as deep as it gets in 301 or 341, and our programs won't be as large as they get in 323, 325, or 362, but we do ramp things up a bit in this course.
And no, we do not intend this course as a weed-out course!

Thinking About Problem Solving

A few underlying approaches:
- Separate interface and implementation. (You can also think of this as separating the what and the how, the six P's vs. the corresponding Scheme code.)
- Start simple. We're tempted to add lots of features. But more features limit your choice of implementation. So we'll start simple and build.
- Refactor. Good programmers find common code and write instructions that factor out the commonalities. So, whenever you are tempted to copy, paste, change, write a more general function and just call that function.

The Course Theme: Computing for Social Good

This semester, we are continuing an experiment of adding themes to the course, just as we have themes in 151 and 161.
Drawing upon surveys of prospective and past CSC 207 students, and with some of my input, my research students decided upon two general areas to include: Computing for Social Good and Android App Development.
Feedback also suggested that some students were worried that these additional topics would take away from the core of the course.
- We've worked hard to make the intrusion minimal
- In many ways, I think these topics help strengthen the core topics of the course - Certainly, they encourage you to develop skills that will serve you well in the long run, such as communication and working with a code base.
After two semesters of using Android App development, we concluded that the cost of including such development outweighed the benefits. I'm substituting a small unit on GUI building with JavaFX.
To keep things managable, we've chosen a fairly narrow focus. We will be working with the open-source crowdmapping application called Ushahidi.
- We will use an Ushahidi installation as our source of data for our algorithms and data structures.
- Toward the end of the semester, you will build an Ushahidi installation for a community member.
Stay tuned for further details.

Academic Honesty

As many of you know, this department has had some significant issues with academic honesty over the past few years. I think we should talk about them a bit today. The syllabus also contains additional information.
Academic honesty is particularly important for computer scientists. When you work for a company and use code (or even ideas) from elsewhere and don't cite them, you put your company at risk.
Note that I care primarily about citation. In most cases, I think you work better as a programmer and thinker if you talk to other people and look up ideas on the Interweb (even on StackOverflow).
How do you avoid problems? Make it a habit that each time you talk to someone or copy code, you document what you've done. It takes a few seconds at most, and it avoids a host of problems.

ADTs and Data Structures

A key theme of this course is the design of abstract data types (ADTs) and data structures.
Both relate to the organization of data.
As the name suggests, an ADT in an abstraction - think of it as specifying what operations you can perform on the data.
In constrast, a data structure specifies how the data are actually arranged in memory.
There's not a hard line between the two. We'll often do some abstraction in the design of data structures and may consider some implementation issues as we design ADTs.

Steps in Design

I've used arrays in the example below. I'll probably switch to stacks, since you also do those in 161.

Abstract Data Types

Decide upon the overall philosophy of the ADT. That is, what is its primary purpose?

For example, we might say that a vactor is a collection of values indexed by sequential integers.
Identify some applications of the ADT. What problems will the ADT help us solve? Vectors might be useful if we assign identification numbers to people and want to look them up by identification number.
Identify the primary procedures (procedures, methods, subroutines, whatever you want to call them).
- Create a new vector
  - perhaps of fixed size
  - perhaps with a default value
- Set the value at a particular index
- Get the value at a particular index
- Delete a vector you've created

Data Structures: Implementing ADTs

Figure out a way to lay out the ADT in memory
- We might use a sequential chunk of memory with pointers to the individual elements
- We might use a sequence of structures that contain a value and a link to the next structure. (We often call such structures pairs, nodes, or cons cells.)
Decide how to implement the ADT using this layout
- You can write the algorithms for each function in pseuodocode or real code
Evaluate the efficiency of the implementation
- How much time will each of the functions take?
- How much space does the implementation use? (Sometimes we ask about the overhead of bookkeeping data to data stored.)
- You may consider each in terms of a typical use case
Evaluate other aspects of the implementation