We will begin class with our summaries of the reading from our text as planned last class.

We have already discussed ADTs (section 2.4) and algorithms (section 2.5), so our next task is to look at Section 2.6: Different Approaches to Designing and Algorithm.

The key idea in this section is the comparison between a top-down design approach and a bottom-up design approach. We can talk about that in class.

The discussion of control structures used in algorithms is already very familiar, so you should just read through that to see how our textbook author addresses the topic.

I suspect the remaining sections of the chapter will be new to you, and since time and space complexity and the analysis of algorithms will be central to our investigation in this course, we should spend some time on them. I would like to have you plan a summary of this section as a class for presentation in class on Monday.

Divide up the remaining sections of this chapter:

• Section 2.8: Time and Space Complexity
• Section 2.9: Big O Notation
• Section 2.10: Omega Notation (Ω)
• Section 2.11: Theta Notation (Θ)
• Section 2.12: Other Useful Notations

And prepare summaries for presentation in class on Monday. As will become our custom, these will be evaluated using our class presentation rubric.

We will begin class with a discussion of the following:

First Definitions

Efficient Program

An efficient program is one that executes in the minimum time using the minimum memory space.

Data Structure

A data structure is a collection of data elements grouped under one name that are organized and stored so they can be used efficiently.

Abstract Data Type (ADT)

An abstract data type (ADT) consists of a set of data values and the associated operations which can be performed on them precisely specified independent of any particular implementation.

Algorithm

An algorithm is a finite sequence of instructions used to solve a class of specific problems or to perform a computation.

Steps for Choosing a Data Structure

1. Analyze the problem to determine the operations on the data that must be supported.
2. Quantify the resource constraints for each of these operations.
3. Select the data structure that provides the required operations within the resource constraints as efficiently as possible.

Create a new git repo for this class named csc223 on the same git host you used for last semester's class. Please confirm that the link on the students page (Jose's already does ;-) from your name works once you have finished.

Reading Summary Plan

Before leaving class today, divide up the ideas / topics assigned for homework so that you can prepare a smooth summary of these at the beginning of class on Thursday.

As a nice addition, I would like someone to volunteer to do a quick bit of research and prepare a short summary of CRUD as it relates to our study.

Read Chapter 2: Introduction to Data Structures and Algorithms from Section 2.1: Basic Terminology through the end of Section 2.3: Operations on Data Structures (pages 43 through the beginning of 50) in our text.

Create a markdown file in your new git repo named DataStructuresAlgorithmsVocab.md, and put notes from your reading in this document. Your notes should include a summary of the following ideas / topics:

• primitive vs. non-primitive data structures
• linear vs. non-linear data structures
• array
• linked lists
• stacks
• queues
• trees
• graphs
• traversing
• searching
• inserting / deleting
• sorting
• merging

In addition to your class summary, you'll need to have this completed file in your git repo to earn an A for week 1.

We should decide together in class whether you just want to work on this individually or if you would like to divide the sections down and present them in class next period guided by this rubric.