CS13H Honors Introduction to Programming and Data Structures

Catalog copy 
CS13H. Honors Introduction to Programming and Data Structures. F

An honors programming and data structures course for outstanding
freshman computer science and engineering majors with previous
programming experience.  This course covers the material usually
taught in CS12A, Introduction to Programming, and CS12B, Data
Structures.  The first three weeks of this class cover material taught
in CS12A: programming and documentation skills, algorithmic problem
solving, and programming methodologies.  Topics for this portion of
the class include, but are not limited to, procedures and functions,
conditionals and loop control structures, static and dynamic memory
manipulations, and text processing.  The remaining seven weeks of this
class cover material taught in CS12B: common data structures and the
algorithms associated with each data structure.Topics include big "O"
notation; pointers, recursion, and dynamic allocation; linked lists
and list processing; stacks, queues, binary trees and binary search
trees; simple sorting techniques and simple search techniques.

Prerequisite(s): Permission of the instructor.  In general, eligible
students must be eligible to enroll in Mathematics 19A (Mathematics 2B
or 3 or Mathematics Placement Exam score of 40 or higher) or
completion of Mathematics 19A or 11A. (General Education Code: IN.),
have received a grade of A or B in previous programming classes (high
school or equivalent), or a score of 3 or 4 on the CS AP test.


Explanation of prerequisites
CMPS 13H is an honors freshmen-level introduction to programming and
data structures.  It requires some prior programming experience and a
degree of mathematical sophistication.

Required Skills to pass the course
1. Basic use of Unix: cd, pwd, ls, vi, etc.
2. Use of java tools: javac, java, jdb
3. Basic software design principles: design, documentation, comments,
   coding style
4. Familiarity with java keywords, types, and syntax
5. Command of java programming fundamentals:
   A. declarations and assignments
   B. procedures and functions
   C. conditionals and loop control structures
   D. static and dynamic memory manipulations
   D. text processing
6. Ability to use java to solve basic programming problems 
8. Ability to use tools to Make software, separate compilation 
9. simple linked list manipulation, testing, and debugging
10. knowledge of linear structures, stacks and queues
11. understanding of interface vs implementation
12. recursion and intuitive understanding of asymptotic complexity
13. knowledge of trees and associated algorithms
14. knowledge of simple forms of searching and sorting
15. familiarity with Java, ANSI C, and Unix tools

Core topics (must be taught)
1. Tools: javac, java, etc.
2. I/O
3. Data types
4. Declarations and assignments
5. Procedures and functions
6. Conditionals and loop control structures
7. Recursion
8. Static and dynamic memory manipulations
9. Basic text processing
10. Classes and Object-Oriented Programming fundamentals
11. basic pointer skills
   a. allocation of objects (structures) and the use of 
      references (pointers) to objects
   b. construction and access to elements of linked lists,
      insertion into, deletion from, and traversal of linked
      lists
12. interactive debugging and program tracing
   a. assert statements, preconditions and postconditions
   b. using print statements to trace programs
   c. use of specific interactive debugging tools, breakpoints,
      execution tracing, dumping values of variables
13. simple linear data structures
   a. stacks and queues
   b. linked list implementation of each
   c. array implementation of each and resizing of arrays
14. asymptotic complexity analysis, big-``O'' notation
   a. informal discussion of the basic concepts
   b. intuitive analysis of specific algorithms given in class
      without any significant mathematical rigor
15. trees
   a. binary trees
   b. depth first traversals:  preorder, inorder, postorder
   c. construction, insertion, deletion of nodes in binary trees
   d. implementation of binary trees using references (pointers)
      and nodes
16. searching and information retrieval
   a. linear searching an array and a linked list
   b. binary searching an array
   c. construction and searching of binary search trees,
   d. insertion and deletion in binary search trees
   e. intuitive reference to balanced trees, but no details
      on the balancing algorithms
   f. informal discussion of asymptotic complexity
17. sorting, details of one of the O(n^2) sorts
   a. insertion sort
   b. possibly bubble sort or selection sort

LANGUAGE- AND UNIX- DEPENDENT TOPICS
18. All topics listed under part 1 are currently taught in Java
   a. interface classes vs implementation classes
   b. minimal use of object-orientation, except that collection
      (container) classes are written generically to hold
      Objects or Comparables as appropriate
   c. wrapping and unwrapping of primitive objects and casting
      to/from Object and Comparable
19. programming interaction with Unix
   a. basic Unix commands and interaction via the command line
   b. shell pipes and file redirection
   c. access to command line arguments, standard input,
      standard output, reading and writing files
   d. tools to Make software automatically using separate
      compilation of modules
20. introduction to ANSI C
   a. basic libraries, <assert.h>, <stdio.h>, <stdlib.h>,
      <strings.h>, <errno.h>, etc.
   b. header files and implementation files
   c. emulation of Java references using C pointers, avoiding
      any usage of pointer arithmetic
   d. emulation of Java object allocation using malloc/ free
   e. dynamically allocated and resizing of arrays in C using
      malloc/ calloc/ realloc
   f. compilation of source files into object files and
      linking of object files into executable images,
      using tools to Make this automatic


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. sorting, discussion of better sorts, O(n log n), such as
   quicksort, mergesort, or heapsort
6. experience constructing Makefiles for automatic separate
   compilation and linking of programs
7. stdin, stdout, stderr, system exit codes in C and their
   equivalents in Java
8. assembling Java class files into a jar file to Make 
   execution more flexible than the use of the CLASSPATH.

Required Text(s):
Pohl and McDowell, "Java by Dissection", 3rd Edition, Addison-Wesley,
2002.

Carrano, Pritchard, ``Data Abstraction and Problem Solving in Java'',
Addison-Wesley, 2001.  The basic data structures textbook.

Optional Text(s): 
Muldner, ``C for Java Programmers'', Addison-Wesley, 2000.  Provides
an introduction to C.

Sobell, ``A Practical Guide to the Unix System'', Addison Wesley,
1995.  Many students enter the course not being thoroughly familiar
with Unix.


Prepared by Scott Brandt, 10/02