CS42A - Data Structures
CS41A - Introduction to Computer Programming
Data structures used in computer programming to represent domain objects
and activities. Algorithms for manipulating the data structures. Advanced
object oriented programming techniques to implement the algorithms.
- Demonstrate knowledge of commonly used internal and external data
- Implement these data structures using an object oriented programming
- Use appropriate algorithms for building, accessing, and manipulating
these data structures
- Determine the time and space efficiency of these data structures
and associated algorithms
- Use advanced object oriented programming techniques for manipulating
- Fundamental data structures.
- Linear data structures: linked list, stack, queue, priority queue,
- Trees and graphs: binary tree, general tree, DAG, graph, directed
- Self-balancing search trees: binary, AVL, splay, 2-4, red-black,
- Sets and maps: heap, hash
- Elementary sorting and searching.
- Sorting: bubble, selection, insertion, heap, merge, bucket, quick,
- Searching: list traversal, tree traversals, binary search,
- Graph: paths, tours, spanning trees, coloring
- Set and maps: union-find
- Advanced object-oriented programming.
- Event-driven and concurrent programming.
- Using APIs.
Students are required to pass both components.
- Coursework - 40%
- Test - 10%
- Assignments - 30%
- Final exam - 60%
- Wolfgang Koffman, Objects, Abstraction, Data Structures and Design
Using Java Version 5.0
Joseph Cottrell, MSc.(UWI)