The design, analysis, and implementation of data structures and their associated algorithms. Lists, stacks, queues and priority queues, trees, graphs, dictionaries, time and space complexity, sorting and searching, advanced problem-solving, and algorithm design strategies.
Athena Title
Data Structures
Prerequisite
CSCI 1302 and (CSCI 2610 or CSCI 2610E or CSCI 2611)
Semester Course Offered
Offered fall, spring and summer
Grading System
A - F (Traditional)
Student Learning Outcomes
Analyze algorithms using the asymptotic analysis notations.
Design, analyze, and implement recursive solutions.
Design, analyze, and implement generic reusable abstract data types.
Articulate algorithm design methods and be able to use them in problem solving.
Implement, and analyze the principal algorithms for sorting, searching, hashing, and graph algorithms and be able to select the appropriate algorithm and apply it to solve real-world problems.
Choose the appropriate data structure and algorithm to solve real-world problems and to defend the selection.
Topical Outline
Algorithm Analysis:
a) Explain and compare the growth of functions: logarithmic functions, polynomials, linearithmic, and exponential functions.
b) Given a function, prove that it falls into a particular complexity class.
c) Formally Define the Asymptotic Complexity notations (Big O, Big theta, and Big Omega). Distinguish between case analysis methods (best case, average case, and worst-case analysis).
d) Calculate the running-time T(n) for a given function by calculating the number of processing steps.
e) Find the asymptotic complexity of an algorithms as a function of problem size.
Recursion:
a) Identify the base case and the general case of a recursively defined problem.
b) Write recursive functions to solve computational problems.
c) Convert a recursive function to an iterative function and vice versa.
d) Analyze the running-time for recursive functions by finding the depth of recursion, the tree method, and the master method of decreasing functions.
e) Compare iterative and recursive solutions for a problem and select the best solution and be able to defend the selected solution based on non-functional attributes such as efficiency, simplicity, maintainability, code reuse, and others.
Abstract Data Types and Their Implementations: Lists, Queue, and Stack:
a) Explain the different representations (array and linked implementations) of the ADT and its manipulating operations.
b) Analyze and assess the impact of the ADT representation on the running-time complexity of the ADT operations and space requirements.
c) Implement (with templates) at least two representations (array, singly linked list, doubly linked list, circularly linked list) of at least one of the ADTs and use the implementation to solve a real-world problem.
Abstract Data Types and Their Implementations: Binary Search Trees BST, AVL Trees, Red-Black Trees, and B-Trees:
a) Explain the different tree implementations and associated operations.
b) Analyze and assess the impact of the ADT implementation on the running-time complexity of the ADT operations and space requirements.
c) Implement at least one search tree.
d) Select a tree type that is best suited to solve a problem and be able to defend the selection.
Abstract Data Types and Their Implementations: Heaps and Priority Queues:
a) Implement the Heap ADT and its basic operations.
b) Analyze the basic heap operations.
c) Use the heap structure as an internal traversal method to develop efficient solutions to real world problems.
Abstract Data Types and Their Implementations: Design and implement the Priority Queue ADT using various data structures (Array List, Linked List, and Heap) and evaluate the different implementations with respect to space and running-time efficiency.
Abstract Data Types and Their Implementations: Graphs and Graph Algorithms:
a) Depict various representation (adjacency list and adjacency matrix) given a picture or a description of the graph.
b) Compare the adjacency list and the adjacency matrix implementations of the Graph ADT according to the running-time complexity of the graph operations and space requirements.
c) Trace basic graph algorithms, including depth first traversal, breadth first traversal, minimum spanning trees (Prim’s and Kruskal’s), topological sort, and single-source and all-pairs shortest path (Dijkstra’s and Bellman Ford’s) for a given graph.
d) Choose the appropriate graph algorithms to solve a problem given a description of the problem.
Abstract Data Types and Their Implementations: Hash Tables:
a) Design and implement two different versions of the hash table interface: open addressing (linear probing, quadratic probing, double hashing, rehashing) and chaining.
b) Analyze and assess the running-time complexity of basic hash table operations (insert, delete, and search).
Algorithm Design Strategies:
a) Differentiate between the strategies (greedy, divide-and-conquer, and dynamic programming) through teaching well-known algorithms, and identify a practical example to which the design strategy would apply.
b) Use divide-and-conquer to solve an appropriate problem.
Sorting Algorithms:
a) Implement and analyze sorting algorithms including quadratic sorts, linearithmic sorts, and non-comparison linear sorts.
b) Select a sorting algorithm to solve a given problem based on running-time and space efficiency and be able to defend the selection.
Implement and test projects that use data structures to solve real-world problems and satisfying a set of predefined functional requirements (pre/post conditions) and nonfunctional requirements (efficiency, robustness, code-reuse, maintainability, and others).
