CS 313         Intermediate Data Structures

[ Assignments | CS | Piazza| Canvas ]

Course Description

Our main theme is the equation (proposed by Niklas Wirth) "Programs=Algorithms + Data Structures." First, we will review the asymptotic complexity notations, loop invariants and recurrence equations, as well as the basic linear data structures. Then, we will discuss rooted ordered trees and their usage, especially as search structures (i.e., Binary Search Trees, Reb-Black Trees). We will conclude with some basic sorting algorithms and some analysis using the newly introduced data structures. The objective of the course is to acquire facility using tools to analyze (and design!) algorithms (computational complexity, proofs of correctness) and structuring the information manipulated by the algorithms.

Instructor

Thien Huu Nguyen, thien@cs.uoregon.edu

Lectures and Labs

Prerequisites

• CIS 212 - Computer Science III
• MATH 231-232

Textbooks and Readings

• (Required) Cormen, Leiserson, Rivest, & Stein, Introduction to Algorithms, 3rd Edition, MIT Press, 2009 (CLRS). (text homepage).
• (Recommended) Dasgupta, Papadimitriou, and Vazirani, Algorithms, McGraw-Hill, 2008. (Also used in 315.)
• (Recommended) Michael Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, 3rd Edition, Wiley, 2004.
• (Recommended) Weiss, Data Structures and Problem Solving using Java, Addison-Wesley, 1998.
• (Recommended) Knuth, The Art of Computer Programming, vol.I, Addison-Wesley 1975.

Major Topics

• Algorithm analysis, measuring complexity, big-oh notation: 3 lectures
• Proofs of correctness: 1 lecture
• Linear data structures: linked lists, stacks, queues priority queues: 2 lectures
• Binary heaps, heap operations, heapsort, binomial heaps: 2 lectures
• Hash tables, binary trees: definitions, operations binary tree efficiency: 2 lectures
• Intro to self-balancing trees: rotations AVL trees, 2-3-4 trees: 2 lectures
• Red-black trees, red-black deletion: 3 lectures
• Quicksort, analysis, decision tree bound, linear time sorts, order statistics: 3 lectures

Expected Learning Outcomes

This course develops basic concepts and applications of data structures in computer science. The primary topics are familiarity with asymptotic complexity notations, loop invariants, recurrence equations, analysis of basic linear data structures along with their applications to computational problems, rooted ordered trees and their usage and analysis for basic operations of data structures: searches, additions, deletions, and basic sorting algorithms along with their analysis using the newly introduced data structures.

Upon successful completion of the course, students will be able to:

• demonstrate facility with asymptotic complexity notations, common functions and their asymptotic relations;
• demonstrate the ability to use asymptotic complexity notations and common functions to measure the complexity of basic algorithms (loops, recurrence, searches, additions, deletions);
• demonstrate facility using loop invariants to prove the correctness of loop functions;
• demonstrate facility with basic operations in linear data structures (stacks, queues, priority queues), their complexity, and their applications to some basic problems (expression evaluation, tree traversal);
• demonstrate facility with heaps (binary and binomial), procedures for basic operations (searches, additions, deletions) and their complexity;
• demonstrate facility with hash tables and basic hash functions;
• demonstrate facility with self-balancing trees (AVL, 2-3-4, and Red-Black trees), procedures for basic operations, and their complexity;
• demonstrate facility with basic sorting algorithms, their procedures, and their complexity; and
• demonstrate the ability to use the introduced data structures to develop efficient algorithms for some basic problems and compute the complexity for those algorithms.

Acquired Skills

Upon successful completion of the course, students will have acquired the following skills:

• be able to implement the introduced data structures and their operations using a programming language (e.g., Python);
• be able to design efficient algorithms for some basic problems in computer science using the introduced data structures, and implement them using a programming language;
• be able to run the implemented programs in computers and debug the programs if necessary.

Approximate Syllabus

Course Requirements and Grading

This course will be taught in-person, but we will provide options to join removely via Zoom and watch recorded lectures. We will use Canvas and Piazza for assignment submission and discussion.

Grading will be based on the following criteria:

CIS majors and minors, and DSCI majors, must take CIS 212 graded; others may take it graded or P/N.

Grading Scale

Barriers and Accommodations

Academic Honesty

• The University Student Conduct Code (available at conduct.uoregon.edu) defines academic misconduct. Students are prohibited from committing or attempting to commit any act that constitutes academic misconduct. Students should properly acknowledge and document all sources of information (e.g., quotations, paraphrases, ideas) and use only the sources and resources authorized by the instructor. If there is any question about whether an act constitutes academic misconduct, it is the student’s obligation to clarify the question with the instructor before committing to attempting to commit the act.
• All projects turned in for the course must be your own work. Copying from other class members or other sources is not acceptable. If you collaborate with someone else on an assignment, you must indicate such on the work you turn in. Collaboration that is not explicitly credited is plagiarism.
• Academic honesty is expected and cases of suspected dishonesty will be handled according to university policy. In particular, copying someone else's work (including material found on the web) will not be tolerated. If solutions to assignments are obtained from outside sources, the source must be cited.
• You are also responsible for protecting your work. That is, you must take reasonable precautions to prevent your work from being copied. This means that if you store your assignment solutions on a shared server, the file permissions must be set to keep others from accessing your files. If you are working on assignments in the lab, you must remove any of your files from the lab machine before you leave. Turning in someone else's code is collusion, and is a particularly heinous form of plagiarism; if collusion is detected, all individuals involved (i.e., the copyee and all copyers) will be given a grade of F in the course.