CSC 332 – General
Course Information
Course
Description
Study of basic data structures and their applications. Lists and trees; graph algorithms; internal and external sort and search techniques; hashing; analysis and design of efficient algorithms; file processing techniques.
_________________________________________________________________________
Course
Information
Meeting Days/Time:
MWF 10:00 - 10:50
Location: CI1006
_________________________________________________________________________
Instructor
Information
Name:
Office Location: CI 2046
Office Hours: MWF 11am-12noon; W
2-3pm
Phone: (910) 962-3819
email: simmondsd[at]uncw.edu
_________________________________________________________________________
Required
Text
Mark Allen Weiss,
Data Structures and Algorithm Analysis in Java,
Second Edition, Addison-Wesley,
2006.
ISBN: 0-321-37013-9.
Course
Syllabus/Outline
The following topics will be
addressed in the classes.
1. Structured data types
1.1.
Introduction to data structures and data types
1.2.
Mapping to Storage of simple types - integers and reals.
1.3.
Arrays
1.3.1.
One Dimensional Arrays
1.3.2.
Multi-dimensional Arrays
1.3.3.
Mapping To Storage of Arrays
1.3.4.
Triangular Arrays
1.3.5.
Linerization of Triangular Arrays
1.3.6.
Sparse Arrays
1.3.7.
Arrays in Java
1.4.
Structures (records/classes)
1.4.1.
Definition
1.4.2.
Declaring Structure Variables
1.4.3.
Referencing Structure Elements
1.4.4.
Initializing structures
1.4.5.
Arrays of structures
1.4.6.
Passing structures to functions
1.4.7.
Returning structures from functions
2. Abstract Data Types (ADTs)
2.1.
Procedural and data abstraction
2.2.
ADTs for stacks, queues, linear linked lists
3. Linked lists
3.1.
Dynamic memory implementation
3.1.1. Inserting items into the list
3.1.2. Deleting items from the list
3.1.3. Building and searching a list
3.2.
Circular lists
3.3.
Double linked lists
3.4.
Array implementation
3.5.
Stacks
3.6.
Queues
4. Sorting.
4.1.
O(n2) sorts: Exchange (bubble) sort, selection sort,
insertion sort.
4.2. O(nlogn) sorts:
quicksort and mergesort
5. Searching.
5.1. Linear search
5.2. Binary search.
6. Stacks and their implementation
using arrays
6.1.
The push and pop operations
6.2.
Infix, prefix and postfix notation
6.3.
Use of stacks for expression evaluation
7. Recursion
7.1.
Definition
7.2.
Recursion and the program stack
8. Complexity Analysis.
8.1.
Efficiency of algorithms
8.2.
Worst case and average case analysis
8.3.
O(n2) and O(nlogn) family of sorts
9. Binary trees and their
applications
9.1.
Definition: Graphs, trees, and binary trees
9.2.
Array representation of binary trees
9.3.
Dynamic memory representation of binary trees
9.4.
Tree traversal
9.5.
The binary search algorithm
9.6.
Binary Search Trees (insertions, deletions, searching)
9.7.
Balanced trees
10. Queues and their implementation
using arrays
10.1.
The insert and delete operations
10.2.
Priority queues
10.3.
Applications of queues