Revised January 6, 2012

CS 234: Data Types and Structures

General Description

An introduction to widely used and effective methods of data organization, focusing on data structures, their algorithms, and the performance of these algorithms. Students will learn how the choice of a data structure affects the performance and usability of applications, with examples from Web browsing and searching, computer databases, data analysis, text processing, etc. Specific topics include lists, stacks, queues, sets, maps, priority queues, trees, and graphs, together with general algorithmic techniques such as sorting, searching, and other transformations on data. Students who successfully complete the course will be able to use these tools to design and develop efficient programs for a wide variety of applications.

Logistics

This course will interest those wishing to understand how choices made in program design can significantly affect performance, and how to make such choices in particular cases. It is a central course for the Computer Science minor and is highly recommended for students in Information Management or similar fields and for those in the Mathematics/Teaching plan.

CS 234 is aimed at students in any discipline. Students in Computer Science plans (including SE and CFM) should take CS 240 instead.

Related courses (see calendar for official details)

Predecessors: One of CS 116, 136, 138, 145 taken fall 2010 or earlier, 146; Not open to Computer Science students. The initial topics of CS 234 will overcome the differences between CS 116 and 136/146 and put students on a common footing. Students who have taken introductory computer courses from outside the Math Faculty should consult a CS advisor to determine the adequacy of their preparation.

Successors: CS 338.

Conflicts: CS 240.

Typical Reference(s)

Rance D. Neçaise, Data Structures and Algorithms Using Python, Wiley.

Required preparation

Before starting the course, students will need the ability to do the following.

• Use and follow mathematical reasoning and notation; in particular, work comfortably with simple predicate logic, functions and elementary probability.
• Describe basic quadratic sorting algorithms, such as Selection Sort or Insertion Sort.
• Given a simple, well-specified computational task, write a program in a high-level imperative language (e.g., any of Python, C, or Java), and generate appropriate test cases. Use as appropriate simple types, built-in compound types and control idioms such as selection, iteration, and recursion. These programs should not require more than a single routine, possibly together with a small number of additional helper routines.
• Define and write programs that work with recursively defined structures, such as binary trees.

Note: The course will use the Python language for its programming examples and assignments. The necessary syntax and idiom will be presented at the start of the course, as a review for those who know Python and an explanation for those who don't. Experience in other common imperative languages, such as C or Java, will suffice.

Learning objectives

• Describe several common computer applications, for which the choice of data structure can make the difference between efficient usability and complete non-functionality. For each application, describe one data structure appropriate to the application and one structure inappropriate to the application (although appropriate in some other context).
• Explain the concept of "asymptotic run time" and the effects of logarithmic, linear, quasi-linear, quadratic, cubic and exponential run times. Given a simple algorithm, determine and informally justify its asymptotic run-time, as expressed in order notation.
• Explain the relative advantages and disadvantages of using arrays versus linked structures. Describe the trade-offs involved in maintaining elements in a well-specified order.
• Explain the benefits of abstraction and representation independence.
• Explain the concept of Abstract Data Type (ADT). Define several different ADTs (e.g., Stack, Queue, Priority Queue and Map), and give a sample application for each. Explain the complexity of some common implementations of these ADTs. Given a well-specified computational problem, determine which (if any) would assist the solution.
• Explain how external memory differs from internal memory, and describe how this difference affects the performance of a program. Give several examples of real-world tasks requiring external memory, and describe a structure and algorithm appropriate for each.
• Explain and justify the best- and worst-case behaviours of simple quadratic sorting algorithms, as well as Mergesort, Heapsort, Quicksort and at least one non-comparison-based algorithm. Select the appropriate algorithm for a given set of circumstances. Apply sorting-based techniques to algorithmic problems such as elimination of duplicates.
• Describe data structures and algorithms for efficient traversals of graphs (networks) and computations of minimum spanning trees.
• Explain how specialized data structures can lead to efficient solutions to problems. Illustrate this principle by describing algorithms and data structures for a particular real-world problem (e.g., text compression, processing geometric data, etc.)
• Write, test and debug programs using the above structures and algorithms in the Python language, or other imperative language known to or subsequently learned by the student. (At the instructor's discretion, students may be permitted to code partially in another language rather than in Python. Regardless of such permission, students may be tested on the Python language in assignments and/or exams.)

Typical syllabus

The following gives only a general guide for prospective students and instructors. Exact topics and timings will vary from term to term. Students should consult the materials for their particular section at the start of the term.

(Note: each student should find some parts of this material as new and some as review. A student's individual background will determine which material falls into which category.)
The Python language: basic data types, functions, selection, iteration, recursion, strings, association lists, console I/O and file I/O. The runtime of an algorithm: worst-case, best-case, and average-case. Asymptotic analysis and order notation. Definition and examples of abstract data types. Arrays and linked lists.

Review of Selection Sort and Insertion Sort. Mergesort. Quicksort. Non-comparison-based sorting algorithms (e.g., Bucket Sort, Radix Sort). The worst-case, best-case and average-case complexity of these algorithms. Selecting an appropriate algorithm for a specific application.

Stacks and queues. The Priority Queue ADT and simple implementations. Heaps and Heapsort. Application to problems such as selection.

The Map ADT and simple implementations. Linear search and binary search. Self-organizing lists. Balanced search trees (e.g., 2-3-4 trees). Searching in external memory. Hashing: key-indexed search, simple hash functions, and collision-resolution strategies. Example applications.

Adjacency list and matrix representations. Depth-first and breadth-first traversals of graphs. Minimum spanning trees as a case study of algorithms and data structures.

A case study in selecting, designing and implementing data types for a real-world problem (e.g., text compression/retrieval, geometric data, etc.)

---

David R. Cheriton School of Computer Science
University of Waterloo
Waterloo, Ontario, Canada N2L 3G1

Tel: 519-888-4567 x33293
Fax: 519-885-1208

Contact | Feedback: cs-uops@cs.uwaterloo.ca | David R. Cheriton School of Computer Science | Faculty of Mathematics

---

Last modified: Wednesday, 15-Feb-2012 10:28:28 EST

• About CS
• Research
• Grad Studies
• Current Undergraduates
  • FAQ
  • First-year
  • News
  • Non-majors
  • Plans & Courses
    • General Information
    • All Courses
    • Checklists & Sequences
  • Enrichment
  • People
• Future Students
• Services | Facilities
• Outreach
• People
• Site Map

Menu:ShowHide

Search: