TWiki> Main Web>CSNewNonTraditionalMajors>SoftwareEngineeringAcceleratedProposedCurriculum>DataStructuresGPS (2013-10-21, RobertKasper) EditAttach

**CSC2033 Data Structures and Algorithm Design [3]. **A study of common data structures including lists, stacks, queues, trees, graphs and networks, algorithm design methods, and object-oriented design and implementation.

**Prerequisites:** CSC2023 Foundations of Computer Science 2, and MAT1053 Elementary Discrete Mathematics.

**Note: This course is intended to be equivalent to the course with the same number in the traditional program.**

**TO DO: revise detailed list of topics.**

- Representation of numeric data
- Range, precision, and rounding errors
- Arrays
- Representation of character data
- Strings and string processing
- Runtime storage management
- Pointers and references
- Linked structures
- Implementation strategies for stacks, queues, and hash tables
- Implementation strategies for graphs and trees
- Strategies for choosing the right data structure

- Describe the representation of numeric and character data.
- Understand how precision and round-off can affect numeric calculations.
- Discuss the use of primitive data types and built-in data structures.
- Describe common applications for each data structure in the topic list.
- Implement the user-defined data structures in a high-level language.
- Compare alternative implementations of data structures with respect to performance.
- Write programs that use each of the following data structures: arrays, strings, linked lists, stacks, queues, and hash tables.
- Compare and contrast the costs and benefits of dynamic and static data structure implementations.
- Choose the appropriate data structure for modeling a given problem.

- The concept of recursion
- Recursive mathematical functions
- Simple recursive functions
- Divide-and-conquer strategies
- Recursive backtracking

- Describe the concept of recursion and give examples of its use.
- Identify the base case and the general case of a recursively defined problem.
- Compare iterative and recursive solutions for elementary problems such as factorial.
- Describe the divide-and-conquer approach.
- Implement, test, and debug simple recursive functions and procedures.
- Determine when a recursive solution is appropriate for a problem.

- Brute-force algorithms
- Greedy algorithms
- Divide-and-conquer
- Backtracking
- Branch-and-bound
- Heuristics
- Pattern matching and string/text algorithms
- Numerical approximation algorithms

- Describe the shortcoming of brute-force algorithms.
- For each of several kinds of algorithm (brute force, greedy, divide-and-conquer, backtracking, branch-andbound, and heuristic), identify an example of everyday human behavior that exemplifies the basic concept.
- Implement a greedy algorithm to solve an appropriate problem.
- Implement a divide-and-conquer algorithm to solve an appropriate problem.
- Use backtracking to solve a problem such as navigating a maze.
- Describe various heuristic problem-solving methods.
- Use pattern matching to analyze substrings.
- Use numerical approximation to solve mathematical problems, such as finding the roots of a polynomial.

- Simple numerical algorithms
- Sequential and binary search algorithms
- Quadratic sorting algorithms (selection, insertion)
- O(N log N) sorting algorithms (Quicksort, heapsort, mergesort)
- Hash tables, including collision-avoidance strategies
- Binary search trees
- Representations of graphs (adjacency list, adjacency matrix)
- Depth- and breadth-first traversals
- Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms)
- Transitive closure (Floyd’s algorithm)
- Minimum spanning tree (Prim’s and Kruskal’s algorithms)
- Topological sort

- Implement the most common quadratic and O(NlogN ) sorting algorithms.
- Design and implement an appropriate hashing function for an application.
- Design and implement a collision-resolution algorithm for a hash table.
- Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing.
- Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data.
- Solve problems using the fundamental graph algorithms, including depth-first and breadth-first search, singlesource and all-pairs shortest paths, transitive closure, topological sort, and at least one minimum spanning tree algorithm.
- Demonstrate the following capabilities: to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in programming context.

Topic revision: r3 - 2013-10-21 - RobertKasper

Copyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback