Steven L Tanimoto
Fundamental algorithms and data structures for implementation. Techniques for solving problems by programming. Linked lists, stacks, queues, directed graphs. Trees: representations, traversals. Searching (hashing, binary search trees, multiway trees). Garbage collection, memory management. Internal and external sorting. Intended for non-majors. Not open for credit to students who have completed CSE 326 or CSE 332. Prerequisite: CSE 143.
Math Review; Intro to Eclipse, Visual Data Structure Applet; Discrete Math Background; Asymptotic Analysis; Abstract Data Types, Lists, Iterators, Queue ADT; Trees, BSTs; AVL Trees; Memory Hierarchy; B-Trees; Hashing; Programming Techniques; Priority Queues, Binary Min Heaps; Binary Min Heaps; Sorting; Disjoint Sets (UNION-FIND ADT); Graphs: Representations, Topological Sort; Dijkstra's Algorithm; Minimum Spanning Trees, Kruskal's Algorithm, Prim's Algorithm; Dynamic Programming and String Matching Algorithms Image Data Structures.
Student learning goals
understand fundamental data structures.
choose an appropriate data structure for an application.
implement a Java program using tree, hash table, graph, or disjoint set management.
understand how to use asymptotic analysis to compare algorithms.
use a state-of-the-art integrated development environment for programming in Java.
develop interactive graphical demonstrations of data structures and algorithms in Java.
General method of instruction
lectures, readings, programming assignments, problems, in-class exercises.
Take CSE 143. Understand high-school mathematics: especially sets, boolean logic, functions, exponents, logarithms, arithmetic and geometric series.
Class assignments and grading
Develop a program in Java using the Eclipse IDE. The program may involve a graphical user interface as well as data structures and algorithms. Analyze a fragment of Java code and characterize its running time using big O notation.
(tentative weighting) # Assignments: 30 percent # Project: 20 percent # Midterms: 20 percent # Participation: 10 percent (including, quizzes, peer evaluations selected class activities # Final exam: 15 percent