CS 260 - Data Structures I

CS 162U  or CS 234U  and MTH 111Z  

Corequisite(s):  

MTH 251Z  

Course Description: Studies the merge of abstract data types and the algorithms which manipulate them. Topics include the study of elementary searching and sorting algorithms and hashing, and object-oriented implementation strategies for stacks, lists, queues, trees, binary trees, B-trees, and hash tables. For each data structure examined, common and useful algorithms that utilize such structures will be studied. Course also covers an introduction and application of complexity analysis: asymptotic analysis of upper and average complexity bounds, Big O(), Theta() and Omega() notation, as well as a general introduction to resource consumption, including the tradeoff between time and space.

Course Learning Outcomes:

• CLO#1: Define the concepts behind abstract data types and data structures.
• CLO#2: Correlate and implement various abstract data types in a programming language using multiple implementation strategies. (ILO: Critical Thinking)
• CLO#3: Select and use various data structures to solve problems and implement algorithms. (ILO: Critical Thinking)
• CLO#4: Write programs that use one or more of the data structures covered (lists, trees, hash tables, sets & bags).
• CLO#5: Explain the use of O(), Theta(), and Omega() to describe the amount of work done by an algorithm. Relate this to the consumption of resources (time/space) in real-world applications.
• CLO#6: Derive a running time equation and determine O() for a number of algorithms, starting from both source code and pseudo-code.
• CLO#7: Discuss the computational efficiency of inserting and retrieving data from various data structures and of the principal algorithms for sorting, searching and hashing.
• CLO#8: Discuss factors other than computational efficiency that influence the choice of certain data structures and algorithms.
• CLO#9: Be able to empirically determine the behavior of an algorithm and understand the limitations of this approach. (ILO: Critical Thinking)
• CLO#10: Write various sorting algorithms and understand their strengths and weaknesses.