Spring 2015, The College of Saint Rose

Lecture 2: Fundamental Data Structures
Date: Wednesday, January 14, 2015

Agenda

• Announcements
• don't come to class Monday: MLK Jr. day
• if you have any interest in seeing and/or volunteering at a robotics tournament at Albany Academy on Saturday, let me know
• Lecture 1 assignment recap
• Quick survey of data structure familiarity
• Fundamental data structures
• Problem Set 1: Data Structures [HTML] [PDF] further discussion

Due at the start of class, Wednesday, January 21.

Please submit answers to these questions in Submission Box under "LA2" or in hard copy by the start of our next class. We will discuss these questions at the start of class, so no late submissions are accepted. Please be sure that your name is clearly indicated in all submissions.

Note: this assignment is larger than your typical lecture assignments. Please plan accordingly. Fortunately, with the holiday next week, you have a week to do it.

1. Levitin Exercise 1.2.1, p. 17 (4 points).
2. Levitin Exercise 1.2.9, p. 18 (4 points).
3. Levitin Exercise 1.3.1, p. 23 (6 points).
4. Levitin Exercise 1.4.1, p. 37 (4 points).

Terminology

• linear structures
• lists
• arrays
• strings
• array/list index
• counted vs. null-terminated strings
• structure traversal
• abstract data structure/type
• iterator
• stacks/push/pop/LIFO
• queues/enqueue/dequeue/FIFO
• priority queue
• trees
• expression tree
• complete tree/full tree
• tree/node/root node/subtree
• tree edge
• children
• leaves/leaf nodes/interior nodes
• parent
• forest
• sibling/ancestor/descendant
• simple path
• path length
• height of tree node
• height of tree
• depth of tree node
• degree of tree node
• level
• binary tree
• left/right children
• tree traversals: preorder, in order, postorder, level order
• graph
• graph nodes/vertices
• graph edge/edge weights
• path
• simple path
• cycle
• directed/undirected graph
• vertex degree/in-degree/out-degree
• connected vertices
• connected component
• acyclic
• complete graph
• set
• universal set
• bit vector
• dictionary/multiset

Examples

• See Structure Source:
/home/cs431/src/structure5/VectorIterator.java
• See Example: