Computer Science 431
Algorithms
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
Lecture 2 Assignment
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.
- Levitin Exercise 1.2.1, p. 17 (4 points).
- Levitin Exercise 1.2.9, p. 18 (4 points).
- Levitin Exercise 1.3.1, p. 23 (6 points).
- Levitin Exercise 1.4.1, p. 37 (4 points).
Terminology
- linear structures
- lists
- arrays
- linked lists, list nodes, singly- and doubly-linked lists
- 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
- adjacent
- path
- simple path
- cycle
- directed/undirected graph
- vertex degree/in-degree/out-degree
- connected vertices
- connected component
- acyclic
- complete graph
- adjacency matrix/adjacency list
- set
- universal set
- bit vector
- dictionary/multiset
Examples
- See Structure Source:
/home/cs431/src/structure5/VectorIterator.java
- See Example:
/home/cs431/examples/SimpleLinkedList
- See Example:
/home/cs431/examples/Iterables
- See Example:
/home/cs431/examples/Iterators