CMPS-012B.  Introduction to Data Structures
 
Catalog copy 
   CMPS-012B.  Introduction to Data Structures. F,W,S
   Teaches students to implement common data structures and the
   algorithms associated with each data structure, through
   progressively difficult exercises. Topics include big "O" notation;
   pointers, recursion (induction), and dynamic allocation; linked
   lists and list processing; stacks, queues, binary trees and binary
   search trees; simple sorting techniques and simple search
   techniques. Students will gain a working knowledge of the elements
   of the Java and C programming languages. Prior experience with Unix
   is assumed.  Prerequisite(s): course 12A.  Enrollment limited to
   150.  (General Education Code: IN.) W. Mackey, The Staff

Explanation of prerequisites 
   CMPS-012A.  Students must already be familiar with basic programming
   concepts, including variables, strings, arrays, control structures,
   simple debugging, functions and procedures, input and output.
   Provides students with basic experience using Java and Unix.
 
Required skills to pass the course.
1. familarity with Unix, the command line, shell redirection
2. ability to use tools to make software, separate compilation 
3. simple linked list manipulation, testing, and debugging
4. understanding of interface vs implementation
5. recursion and intuitive understanding of asymptotic complexity
6. knowledge of and ability to implement:
   a. linear structures, stacks and queues
   b. binary trees, traversals, and searching
   c. simple forms of searching and sorting
7. familiarity with Java, ANSI C, Unix tools, and documentation

Core topics I (must be taught) -- Language-independent concepts
1. basic pointer skills: allocation, references to objects
2. linked lists: construction, traversal, insertion, deletion
3. debugging and program tracing: debuggers and print statements
4. simple linear data structures: stacks and queues
   a. linked list implementation of each
   b. array implementation of each and resizing of arrays
5. recursion and informal reasoning about correctness
   a. understanding of the implicit function call stack
   b. asymptotic complexity analysis, big-``O'' notation, informal
      intuitive analysis without mathematical rigor
6. searching and information retrieval
   a. linear searching: arrays and linked lists
   b. binary searching: arrays
7. binary trees
   a. depth-first traversals: preorder, inorder, postorder
   b. construction, insertion, deletion
   c. binary search trees: searching, insertion, deletion
8. sorting, details of O(n^2) sorting: e.g., insertion sort
9. program documentation
   a. high level description, and low-level algorithmic details
   b. assertions, preconditions, postconditions, class invariants

Core topics II (must be taught) -- Java-, C-, and Unix- dependent
1. All topics listed under part 1 are currently taught in Java
   a. interface classes vs implementation classes
   b. minimal object-orientation, except that collection classes
      contain Objects or Comparables as appropriate
   c. wrapping and unwrapping of primitive objects and casting
2. programming interaction with Unix
   a. shell pipes and file redirection
   b. access to command line arguments, stdin, stdout, files
   c. tools to automate separate compilation of modules
3. introduction to ANSI C
   a. basic libraries: assert.h, stdio.h, stdlib.h, etc.
   b. header files and implementation files
   c. emulation of references and objects via pointers
   d. storage management: malloc/ calloc/ realloc/ free
   e. information hiding and abstract data type structure

Optional topics 
1. expression trees and relation to reverse polish notation
2. hash tables with collision resolution by chaining
3. informal discussion of balanced binary search trees
4. breadth first traversal of trees using a queue
5. O(n log n) sorts: some of: quicksort, mergesort, or heapsort
6. repetition of much of the Java part of course using ANSI C.
8. stdin, stdout, stderr, system exit codes in C and Java
9. assembling Java class files into a jar file or CLASSPATH usage

Core lab exercises 
1. Unix interaction with the command line, argv, file access
2. pointer (reference) skills, dynamic allocation, linked lists
3. program using trees and recursion
4. at least one program in ANSI C
5. interactive debuggers and program tracing
   
Optional lab exercises 
1. program using hash tables
2. program using some other advanced data structure
 
Comments on related concurrent courses 
   Not applicable.
 
Comments on follow-on courses 
   CMPS-101 discusses the material began in CMPS-012B but in a more
   detailed and mathematically rigorous manner with more advanced data
   structures and algorithms.

Texts
   Carrano, Pritchard, ``Data Abstraction and Problem Solving in Java'',
      Addison-Wesley, 2001.
   Muldner, ``C for Java Programmers'', Addison-Wesley, 2000.
   Sobell, ``A Practical Guide to Unix'', Addison Wesley, 1995.

Prepared by Wesley Mackey, 11/02