Overview
Welcome to CSC 223: Data Structures and Analysis of Algorithms! Since we have been using our textbook for this course for awhile already, there will be a lot of continuity in our study as we move to this new course.
That said, we will begin this course by going back to Chapter 2: Introduction to Data Structures and Algorithms, which will provide a high level overview of what we will be doing this semester.
Thursday, February 1st
Classwork
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.
Homework
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.
Monday, February 3rd
Classwork
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
- Analyze the problem to determine the operations on the data that must be supported.
- Quantify the resource constraints for each of these operations.
- 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.
Homework
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.