CS/IT 352: Data Structures and AlgorithmsCredits: 3

Course Coordinator: Appie van de LiefvoortCSEE - UMKC

This course is required for the degree program BS in CS / Bachelor of IT

Frequency of offering: This course is offered every semester

Specifics for FS2009: :

Class Times and Room:Tuesday/Thursday, 12:30 pm – 1:45 pm in room 14 BlochSchool

Tuesday/Thursday, 5:30-6:45pm in room 312 Royall Hall

Instructor:Judy Mullins

450N Flarsheim Hall

816-235-5938

Office hours: MW 12:00-1:00pm or by appointment (drop-ins welcome if I’m free)

Graduate Assistant:Satish Bhat

531 FH

office hours: tbd

Course description:Introduction to complexity of algorithms through the study of data structures, trees, priority queues , graphs, and hash tables. Comparison of efficiency of searching and sorting algorithms as implemented with various data structures.

Prerequisites:

CS201 Programming & Problem Solving II
CS191 Discrete Mathematics
MAT160 or MAT210(recommended)

Required Textbook:Data Structures and Algorithm Analysis in C++ 3ed by Mark Allen Weiss, Addison Wesley, 2006.

Course Objectives, Goals or Learning Outcomes:Students will be able to (1) analyze a code fragment and determine the algorithmic complexity class of the algorithm (2) write, trace and /or explain algorithms that manipulate stacks, queues, lists, various tree structures, priority queues, disjoint set ADTs, and graphs (3) understand the difference between types of sorting algorithms (priority queue sorts, divide-and-conquer sorts, insertion-based sorts and index-computation sorts)and the best-, worst- and average-case time complexities of these sorts (4) understand traversal algorithms for graph structures and the space and time complexities of graph algorithms, (5) understand the difference between program complexity and algorithm complexity.

Instructional Strategies/Pedagogical Approach:

Classes meet two days each week for 75 minutes each period. The first class of the week will have 50-60 minutes of lecture and discussion covering the topic for that day, followed by a hands-on activity which covers the topic of that day’s lecture or the previous lecture. Students will work in pairs or small groups to do the activity. The second class of the week will have 50-60 minutes of lecture and discussion, followed by a quiz covering material that was taught the previous week.

Each week a study session is held prior to the quiz day to help students understand the material to be covered on the quiz. All course materials are available on Blackboard. Discussion boards are set up for each project and for general topics so that students can share questions and insights about projects. Practice exercises are made available for students to review in preparation for quizzes and the final exam.

CS/IT 352: Data Structures and Algorithms

Proposed ScheduleFall 2009****Dates Are Subject to Change****

ApproxDates / Topics / Readings / In-class Work / Comments
Aug 25 / Course Information, Introduction
Aug 27 / Writing/Reading Algorithms / Ch. 1 / Exercise 1
Sept 1 / Algorithm analysis / Ch. 2 / Exercise 2
Sept 3 / Asymptotics(Big-O, Theta & Omega) / Ch. 2 / Quiz 1 / Assign Project 1
Sept 7 / Labor Day holiday / Holiday / Holiday / Holiday
Sept 8 / More asymptotics / Ch. 2 / Exercise 3
Sept 10 / Abstract Data Types (ADT) List, implementation and complexities
Skip Lists / Ch. 3.1-3.5, 10.4.2 / Quiz 2 / Exercise
Sept 15 / ADT Stack, ADT Queue and their implementation complexities
Applications for Stacks & Queues / Ch.3.6-3.7 / Exercise 4
Sept 17 / General tree structures, binary trees, traversals / Ch. 4.1-4.2, 12.2 / Quiz 3 / Exercise
Sept 22 / Expression trees, binary search trees / Ch. 4.3 / Exercise 5
Sept 24 / Self-adjusting search trees -- AVL / Ch. 4.4 / Quiz 4
Sept 29 / Self-adjusting search trees -- finish AVL,Splay / Ch. 4.5 / Exercise 6 / Proj 1 due
Oct 1 / External tree structures: 2-3trees,2-3-4 trees, B+-trees, red-black trees / Ch. 4.7 / Quiz 5 / Proj 1 Report due
Assign project 2
Oct 6 / Hashing as search technique, Hash functions
Open hashing, Collision resolution with chaining / Ch. 5.1-5.3 / Exercise 7
Oct 8 / Closed hashing,Collision resolution methods, Double Hashing, Rehashing, Extendible hashing / Ch. 5.4-5.7 / Quiz 6
Oct 13 / Sets and Maps / Ch. 4.8 / Exercise 8
Oct 15 / Binary tree applications : Priority Queues, Heaps / Ch. 6.1-6.3 / Quiz 7
Oct 20 / Binomial Queues / Ch. 6.8 / Exercise 9
Oct 22 / Insertion sort algorithms and their performance : Insertion Sort,Shellsort / Ch. 7.1-7.2,7.4 / Quiz 8
Oct 27 / Lower bound for sorting,
Priority Queue sorts and their performance : Heapsort and Selection / Ch. 7.3,7.5, 7.9 / Exercise 10 / Project 2 due
Judy at OOPSLA
Oct 29 / Divide&Conquer sorting algorithms and their performance : Mergesort / Ch. 7.6 / Quiz 9 / Judy at OOPSLA
Project 2 Report due
Assign Project 3
Nov 3 / Divide&Conquer sorting algorithms and their performance : Quicksort / Ch. 7.7 / Exercise 11
Nov 5 / Disjoint sets-Union/Find algorithm / Ch. 8 / Quiz 10
Nov 10 / Graphs(basic facts, representations), Graph ADT, topological sort / Ch. 9.1-9.2 / Exercise 12
Nov 12 / Shortest path algorithms / Ch.9.3 / Quiz 11
Nov 17 / Graph Traversals : BFS,DFS / Ch.9.3 / Exercise 13
Nov 19 / Minimum Spanning Trees / Ch. 9.5 / .Quiz 12
Nov 23-
27 / Thanksgiving Break / Break / Break / Break
Dec 1 / Applications for DFS:Biconnectivity and Articulation Points / Ch.9.6.1-9.6.2 / Exercise 14 / Project 3 due
Dec. 3 / Critical path analysis, Network flow problems / Ch. 9.3.4,9.4 / Quiz 13 / Project 3 Report due
Dec. 8 / Introduction to NP and NP-Complete Problems / Ch. 9.7 / Exercise 15
Dec. 10 / Catch-up and Review / Quiz 14
Dec. 15 / Final Exam - comprehensive
VOC 5:45pm-7:45pm
Dec.16 / Final Exam - comprehensive
VOA 10:30am-12:30pm

IMPORTANT DATES

Sept. 7 / Labor Day holiday
Sept. 23 & Nov. 4 / WEPT Test
Sept. 21 / Last day to withdraw without assessment
Nov.30 / Last day to withdraw with assessment
Dec. 15 / V0B Final Exam 5:45pm-7:45pm
Dec. 16 / V0A Final Exam 10:30am-12:30pm

Evaluation / Assessment Criteria and Grading:

Projects

There will be 3 programming projects. Programs will involve problem solving skills and analytical thinking. Each project will require a written project report and analysis. Grades will be based not only on correctness, but also on programming style, documentation, efficiency and the written report and analysis.

Exams/Quizzes/Homework

There will be an in-class quiz every Thursday, given at the end of the class period. There will be 3 or 4 graded homework assignments.

Grading

Grade assessments will be based on the following:

3 Projects @ 9% each = 27%

Homework exercises = 10%
10 Quizzes @ 4% each = 40%
1 Final Exam = 23%

If you have a question about any grade received, you must see me or the grader within 10 school days of receiving the grade. After 10 school days have elapsed, no adjustment will be made to any grade.

Final lettergrades will be assigned according to the following scale:

A / A- / B+ / B / B- / C+ / C / C- / D+ / D / D-
93-100 / 89-92 / 86-88 / 80-85 / 78-79 / 76-77 / 70-75 / 68-69 / 64-67 / 60-63 / 57-59

Prepared by:Judy Mullins

Prepared on: 8/16/09