CSC 365 - 3 Semester Hours

Data Structures and Algorithms

Advanced data structures and their internal and external representations are studied. Important algorithms for graphs are presented. External sorting techniques are demonstrated and analyzed. Relevant data structures for the implementation of database systems are discussed. Students' knowledge in the Java language, GUI design, and event-driven programming techniques are extended.

CSC 241 - Computer Science 2

This is the first core course that formally introduces external storage concepts, external data representation, and external sorting techniques. The extensive coverage of advanced data structure topics prepare students for many of the upper division courses that require data Analyzing algorithms behavior mathematically; and studying them empirically in this course helps to orient students to the more scientific facets of the discipline. One section of this course will be taught each semester to classes of size thirty. This course is required for CS majors.

Upon successful completion of this course, students will be able to:

1. Understand some of the most advanced data structures.
2. Understand the concept of external files.
3. Perform studies on algorithms, both mathematically and empirically.
4. Develop external sort Algorithms.
5. Survey some of the most important algorithms in computer science.
6. Expand on their knowledge of programming in Java.
7. Increase their understanding of event-driven programming techniques.
8. Learn more GUI design concepts.

1. Further discussion on internal data structures:
   1. Trees. Implementation, Application, and Analysis of each of the following:
      1. AVL tree.
      2. B-tree.
      3. other topics, such as, tries, heaps, threaded trees.
   2. Graphs.
      1. Directed graphs. Implementation via adjacency matrix and list.
      2. Weighted graphs.
      3. Shortest path problem.
      4. Maximum-Flow problem.
      5. Other topics, such as, Bellman's principle of optimally, Dijkstra's algorithm and its analysis, Reachability matrix, Floyd-Warshall algorithm on all pairs shortest path, Graph traversal, depth first and breadth first search, Critical paths, Topological sort, Minimum spanning trees, spanning forests, Prime's algorithm, Berge-Kruskal algorithm, Bipartite graph.
   3. Hashing.
      1. Hash functions.
      2. linear probing and chaining.
      3. techniques for collision resolution.
2. Files.
   1. Concepts.
   2. Storage Media.
   3. Common file organization: sequential, Random.
   4. Indexing techniques: such as, Hash indexing (Extendible hashing), Tree indexing(Btree, B*Tree).
   5. External sorting: Implementation and analysis of K-way merge, Polyphase merge.

1. Lectures.
2. Discussion.

1. Readings from the textbook.
2. Design and implementation of programs.
3. Empirical and mathematical study of algorithms.

1. Individual programming projects.
2. Examinations.
3. Homeworks that require analysis of algorithms mathematically.

R. Sedgewick. Bundle of Algorithms in Java (Parts 1-5): Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms (3ed). Addison Wesley, 2003.

N. Dale, D. Joyce, C. Weems, and S. Rebelsky. Data Structures In Java. Jones & Bartlett, 2002.

F. Carrano and J. Prichard. Data Abstraction and Problem Solving with Java: Walls and Mirrors. Addison Wesley. 2001.

R. Lafore. Data Structures and Algorithms in Java (2ed). Sams, 2002.

B. Eckel. Thinking in Java (3ed). Prentice Hall, 2002.

S. Sahni. Data Structures, Algorithms and Applications in Java. McGraw-Hill, 2001.

M. Campione, K. Walrath, and A. Huml. The Java(TM) Tutorial: A Short Course on the Basics (3ed). Addison-Wesley, 2002.

D. Flanagan. Java Examples in a Nutshell: A Tutorial Companion to Java in a Nutshell (Nutshell Handbook) (2ed). O'Reilly & Associates, 2000.

R. Richard Wiener and L. Pinson. Fundamentals of OOP and Data Structures in Java. Cambridge University Press, 2000.

M. Weiss. Data Structures & Algorithm Analysis in Java. Peachpit Press, 1998.

T. Standish. Data Structures in Java. Addison-Wesley. 1998.

R. Kruse. Data Structures and Program Design in C. Prentice-Hall, 1991.

R. Kruse. Data Structures and Program Design (2ed). Prentice-Hall, Englewood Cliffs, NJ, 1988.

E. Horowitz and S. Sahni. Fundamentals of Data Structures (classic). Computer Science Press, 1976.

A. Aho, J. Hopcroft, and J. Ullman. The Design and Analysis of Computer Algorithms (classic) Addison-Wesley. 1974.