Data Structures and Algorithm Design

Course Description

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.

Topic: Data Structures

  • 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
Learning Objectives:
  1. Describe the representation of numeric and character data.
  2. Understand how precision and round-off can affect numeric calculations.
  3. Discuss the use of primitive data types and built-in data structures.
  4. Describe common applications for each data structure in the topic list.
  5. Implement the user-defined data structures in a high-level language.
  6. Compare alternative implementations of data structures with respect to performance.
  7. Write programs that use each of the following data structures: arrays, strings, linked lists, stacks, queues, and hash tables.
  8. Compare and contrast the costs and benefits of dynamic and static data structure implementations.
  9. Choose the appropriate data structure for modeling a given problem.

Topic: Recursion

  • The concept of recursion
  • Recursive mathematical functions
  • Simple recursive functions
  • Divide-and-conquer strategies
  • Recursive backtracking
Learning Objectives:
  1. Describe the concept of recursion and give examples of its use.
  2. Identify the base case and the general case of a recursively defined problem.
  3. Compare iterative and recursive solutions for elementary problems such as factorial.
  4. Describe the divide-and-conquer approach.
  5. Implement, test, and debug simple recursive functions and procedures.
  6. Determine when a recursive solution is appropriate for a problem.
AL/BasicAnalysis [core] Minimum core coverage time: 4 hours Topics: • Asymptotic analysis of upper and average complexity bounds • Identifying differences among best, average, and worst case behaviors • Big O, little o, omega, and theta notation • Standard complexity classes • Empirical measurements of performance • Time and space tradeoffs in algorithms • Using recurrence relations to analyze recursive algorithms Learning Objectives: 1. Explain the use of big O, omega, and theta notation to describe the amount of work done by an algorithm. 2. Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms. 3. Determine the time and space complexity of simple algorithms. 4. Deduce recurrence relations that describe the time complexity of recursively defined algorithms. 5. Solve elementary recurrence relations.

Topic: Algorithmic Strategies

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

  1. Describe the shortcoming of brute-force algorithms.
  2. 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.
  3. Implement a greedy algorithm to solve an appropriate problem.
  4. Implement a divide-and-conquer algorithm to solve an appropriate problem.
  5. Use backtracking to solve a problem such as navigating a maze.
  6. Describe various heuristic problem-solving methods.
  7. Use pattern matching to analyze substrings.
  8. Use numerical approximation to solve mathematical problems, such as finding the roots of a polynomial.

Topi: Fundamental Algorithms

  • 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
Learning Objectives:
  1. Implement the most common quadratic and O(NlogN ) sorting algorithms.
  2. Design and implement an appropriate hashing function for an application.
  3. Design and implement a collision-resolution algorithm for a hash table.
  4. Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing.
  5. 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.
  6. 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.
  7. 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
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback