©2008 Institute of Technology, University of Washington Tacoma

TCSS 342: Data Structures

Winter 2007

Instructor: Prof. Ankur Teredesai

Class Schedule: M/W 4:30pm - 6:45pm @ CP 334A

Office Hours: M/W 2 pm - 3 pm PNK 215 and by special appointment requested via e-mail.

Textbook: Data Structures and Problem Solving Using Java - 3rd Ed. by M.A.Weiss

References (General suggested reading prior and thru the course):

Additional references may be provided by the instructor.

Goals:

1. Increase awareness and knowledge of application for when to use the appropriate data structure to solve a computing problem.

2. Gain experience designing and solving computational problems.

3. Gain increased understanding of programming tools and techniques for problem solving.

4. Appreciate the need to design algorithms using new and existing data structures. Familiarize yourself with formal constructs of complexity.

Prerequisites: TCSS 305 (may be taken concurrently), TCSS 321, one quarter of calculus, one quarter of calculus based physics.

Topics:

See the schedule for changes in the this list of topics. 

1. Problem solving using computing

2. Programming as a means for problem solving

    a. Design considerations.

    b. Individual and team programmatic problem solving.

3. Mathematical tools for program analysis.

    a.        RAM model

    b.Big oh notation, worst case and best case analysis

    c.proof techniques: proof by contradiction, proof by induction

    d.logarithms, exponents, summations, modular arithmetic

4.Data structures

    a.linear structures: lists, stacks, queues

    b.trees, binary trees, binary search trees, balanced binary search trees

    c.hash tables

    d.heaps

    e.external memory data structures: B-trees

    f.graphs

    g.basic abstract data types: List ADT, Dictionary ADT, Priority Queue ADT, Disjoint ADT (optional)

3.Basic algorithms

    a.searching and lookup: binary search, tree searching, hash table lookup

    b.traversal: tree traversal (preorder, inorder, postorder), graph traversal (depth-first search, breadth-first search)

    c.sorting: insertion sort, heapsort, mergesort, quicksort

    d.information-theoretic lower bound for comparison-based sorting

    e.breaking the lower bound: bucket sort, radix sort

    f.graph algorithms (optional): topological sort, shortest path algorithms, minimum spanning tree algorithms

Grading Policy:

          UW Grading Scale Guidelines: Link

Homework (40%), Midterm Exam (20%), Final Exam (20%), In-Class Quizzes & Participation (10%), Student Presentation (10%)

Note: these outgoing characteristics are similar to those of TCSS 305.  The difference is that the outgoing characteristics of TCSS 342 are in the context of the material discussed in TCSS 342.

Characteristics of an A student – Work is consistently outstanding in quality and displays particular insight and creativity.  It is consistently presented with exceptional clarity and completeness.  (S)he shows academic leadership in class discussions and contributes to others understanding and learning. In addition the student is:

1.Able to implement and document a high quality, medium complexity program when given little guidance for how to design and implement it.

2.Demonstrates an understanding of when to employ appropriate data structures.

3.Has a strong ability to generate and evaluate different design alternatives based on the criteria described in the course.

4.Has a strong ability to reason about programs abstractly.  This includes formalisms such as the RAM model and big oh notation.

Characteristics of a B student – Work is consistently complete, the predominance of it is correct, it shows understanding of the material, and it is presented professionally and clearly.  (S)he makes regular contributions to class discussions.  (S)he is well prepared to use the material in the next course and the following:

1.Able to implement and document an above average quality, medium complexity program when given some guidance for how to design and implement it.

2.Understanding of when to employ appropriate data structures in situations that are simple variations of those described in the course.

3.Has rudimentary ability to generate and evaluate different design alternatives based on the criteria described in the course.

4.Has rudimentary ability to reason about programs abstractly.  This includes formalisms such as the RAM model and big oh notation.

Characteristics of a C student – Work is basically complete and correct, and it is presented coherently and completely. (S)he is prepared to use the material in the next course but will likely need additional study in the area. (S)he participates in class discussions and the following:

1.Able to implement and document a mediocre quality, medium complexity program when given guidance for how to design and implement it.

2.Knowledge of data structures, abstract data types, and basic algorithms: how they are defined, how they work.

3.Knowledge of when to employ appropriate data structures that have been discussed in the course.

Requesting changes to the grade: Each assignment, exam and activity will be graded and returned within a week by the instructor. Students should report any issues or requests for changes/review of grades by e-mail to the instructor/grader by the end of next working day after grades are provided. Failure or delay in reporting issues beyond that time will result in finalizing the grade for that item unless additional time is required to resolve the issue.

Dropping:

Please check the UWT calendar for the last day to drop the course without special permission. The instructor will appreciate if you let him know your plans to drop as early as possible.

Plagiarism and Cheating Policy:

First offense in any course: Zero on the paper or exam being graded and a permanent entry describing the cheating entered into the student's file.
Second offense in any course: F in the course grade, a permanent entry describing the cheating entered into the student's file, and referral of the cheating to Student Judicial Affairs.

Students are encouraged to collaborate regularly with colleagues to gain a deep understanding of the material, and to gain insight on options for problem solutions.  Solutions submitted are to display individual or their own groups knowledge and accomplishment.  Any significant contribution in a submission must be acknowledged and the responsible student or source given due credit.  See http://depts.washington.edu/grading/issue1/honesty.htm

    Safety Escorts:

        Safety escorts are available to accompany you to your vehicle 24 hours a day, 7 days a week. Call Campus Safety at      2-4416 from a campus phone, and 253-692-4416 from a non-campus phone.

Reporting Emergencies: From campus phones, report emergencies by dialing 9-911 and state the T-number that is on a sticker on the phone; from non-campus phones dial 911. Building location numbers are posted on all buildings. For assistance with non-emergencies call Campus Safety at 2-4416 from a campus phone, and 253-692-4416 from a non-campus phone.

Emergency Procedures: In case of emergency, follow your professor’s instructions. When an alarm sounds, evacuate the building immediately. MATT, CP, WG, GWP, and BB buildings assemble in the Cragle Parking Lot south of the library. BHS, WCG, and DOU buildings assemble near the transit station next to the Pinkerton Building on Broadway (across from Spaghetti Factory). Pinkerton occupants go to the convention center parking lot north of Pinkerton. For more information about emergency procedures and information, please go to: http://www.tacoma.washington.edu/safety/

Disability Support: If you would like to request academic accommodations due to a temporary or permanent disability, contact Lisa Tice, Manager for Disability Support Services (DSS) in the Mattress Factory Bldg, Suite 206. An appointment can be made through the front desk of Student Affairs (692-4400), through Student Development and Success (692-4501), by phoning Lisa directly at 692-4493 (voice) or 692-4413 (TTY), or by e-mail ltice@u.washington.edu. Appropriate accommodations are arranged after you've conferred with the DSS Manager and presented the required documentation of your disability to DSS.