Course Description: | 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. |
Course Objectives: | 1. Analyze algorithms using the asymptotic analysis notations.
2. Design, analyze, and implement recursive solutions.
3. Design, analyze, and implement generic reusable abstract data types.
4. Articulate algorithm design methods and be able to use them in problem-solving.
5. 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.
6. Choose the appropriate data structure and algorithm to solve real-world problems and to defend the selection. |
Topical Outline: | 1. 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 algorithms as a function of problem size.
2. 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.
3. Abstract Data Types and Their Implementations
3.1 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.
3.2 Search tress: 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.
3.3 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.
3.4 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.
3.5 Graphs and Graph Algorithms:
a) Depict various representations (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.
e) Analyze the impact of data structures on the complexity of graph algorithms and choose a data structure to store the
edges and/or nodes for a given graph algorithm and be able to defend the selection.
3.6 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).
4. Algorithm Design Strategies
a) Differentiate between the strategies (greedy, divide-and-conquer, and dynamic programming) and identify a practical
example to which the design strategy would apply.
b) Use divide-and-conquer to solve an appropriate problem.
5. 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.
6. 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 non-functional requirements (efficiency, robustness, code-reuse,
maintainability, and others). |