COSC 311: Data Structures

Winter 2020
 ID 23331

MW 5:30-7:10pm  203 PH

Instructor: Dr. William Sverdlik
Office: 512E Pray-Harrold
Office Hours: (tentative)
MW 9:00-9:50,
MW 12:00-2:00,
W 4:30-5:30,
MW after 7:10 (by appointment). Other times by appointment. Send me an e-mail if you need to arrange a different time.
Phone: 734-487-7081

What I hope you get out of this course (some might call this "Objectives") :

This class is the big one; probably the most important of all your undergraduate classes in computer science. I have three primary objectives/goals for all of you:
1) Become familiar with  implementing various data structures (this is coding!!)
2) Identify when to use a specific data structure and understand the various tradeoffs of a particular implementation
3) Analyze the time and space complexity of algorithms employed in 1) and 2)

Textbook:  Lafore, Data Structure & Algorithms in Java, 2nd Ed, SAMS . Find it here.

Student work and assessment:
Programming(4 programs) : 20%
        Quizzes (3 quizzes)     : 30%
        Tests (2 test) : 30%
        Final Exam: 20%

Important Dates This Semester
Jan. 6 - classes begin
Jan 20 - MLK Day (no classes)
Feb 24 - March 1 Winter Recess (no class)
March 11 March 16 - March 19 Bill is not here ( But Fear NOT! You will have class, including lectures and an exam)

             Homework and Link to Video for March 16-March 19

             Homework and Link to Video . Due: Monday April 6

April 20 - Last Day of Classes
April 27 - Your Final Exam (5:30pm - 7:00pm)

Quiz and Test Dates:
    Quiz 1 - Wednesday Jan 22
    Quiz 2 - Wednesday Feb. 5
    Quiz 3 - Wednesday Feb. 19
    Test 1 -  Monday March 16 Wednesday March 18
    Test 2 -  Monday April 13

    Final (cumulative) - Monday April 27 at 5:30pm-7:00pm   

The final score is calculated as follows:
    if (average score on all programming projects < 60%)
        earned grade is F
    else earned grade is as calculated by above percentage list
That is, you must be able to program in order to pass this class.

    91 - 100% A range
    81 - 90%   B range
    71 - 80%   C range
    61 - 70%   D range
    <=60%      E

SPECIAL NOTE: This class is the foundation of all upper level classes and probably the most important class in the curriculum. Give this class the time and respect it deserves!

Topic sequence: The chapters of the textbook will be covered as shown in the schedule below.

Attendance: is not required, but you miss class at your own risk. It is your responsibility to find out the missed work; I suggest you get the phone number of a classmate. Make-up exams will be given only in an extreme situation and will require documentation ; otherwise a missed exam will count as a zero.

Late Hand-Ins: Programming assignments will be due at 5:30pm on  the assigned day. Late submissions are penalized 50% per late class period. This means that if you hand in the program at 5:31pm on the due date, it will lose 50% of total credit.If you do not hand in your program on time, you will have until 5:30pm  the  following class meeting to hand it in and receive at most 50% credit. PLEASE NOTE: I enforce this rule strictly; this means you will not be able to print off your assignment on the due date. In other words, don't leave your homework until the last minute!

All programs must be demoed to me. I will provide details as a program becomes due. Programs that are not demonstrated receive a grade of zero.



A Note about email: I will have 75 students this semester spread out over three classes. I will make attempts to learn your names, but I am often unsuccessful. If I receive an email like:

Subject: I don't understand

problem 7

I have no idea whom this student is, nor what class the student is referring to. Please begin all emails to me by saying "I am in your COSC 221 class". Also make sure to sign your email with your full name and student number. I tend to work in full, complete sentences and ask that you do so as well. Emails that don't meet this standard will not be answered.


PLEASE NOTE: I do not accept assignments submitted electronically. I also do not debug programs electronically.

Cheating: It violates University policy, you don't do it. Cheating is defined as representing all or part of someones elses work as your own. While you are certainly encouraged to seek the advice of others in this class on assignments, the work you hand in should represent your own efforts. Violation of this rule will be dealt with according to University policy. If you are really stuck on a problem, come see the instructor!

Is this a hybrid course ?
No it isn't. But I have prepared videos for most of the lectures. responsibilities that will have me out of the classroom and off campus.

Random Notes and Thoughts (I will fill this in as the class progresses)

Chapter 2 - OrderedArray  Chapter 3 - Simple Sorting and Big-Oh

Video - Insertion Loop, Introduction to Analysis of Algorithms, Insertion Sort

Video - the three elementary sorts: Insertion, Selection, Exchange

Video - Linear Search and Binary Search
Video - the OrderedArray Class

Time to start think about the first programming Assignment (Video)

Prerequisites for the assignment ( Short! Length 3:40)
The assignment (Length 42:01)
Some helpful hints (Length 6:38)

Why do we need iterators ? Start writing your first programming assignment and you will discover why.

Chapter 4 - Static Implementation of Stacks and Queues

Implementation of Stacks and Queues
Parse an arithmetic expression - better algorithm than the book !

Chapter 5 - Linked Lists

Memory Management in Java - not in book, but helpful for what follows
Intro to Linked Lists
Double Ended Lists
Sorted Linked Lists
Doubly Linked Lists and some thoughts on Program 2

Chapter 6 - Recursion

Introduction to Recursion
Recursion Examples

Chapter 11 - Hashing

Linear, quadratic and rehashing resolution

Chapter 10 - Multiway Trees

Motivation and 2-3-4 Trees
2-3 Trees and Indexed External Files

Chapter 9 - Balanced Binary Search Trees
The Red-Black Tree by Susan Haynes

Red-Black Trees - the Video
Red-Black Trees - Homework

Programming Assignments and Homework

My colleague, Dr. Haynes, has provided specifications for coding style. I will adhere to these standards. Please read these standards carefully!

You will need to demonstrate your programs to me. There will be a sign up sheet for doing this. Demo times will occur either directly before class or duringmy office hours. You must submit a paper listing when demoing your program; failure to do so is the same as not handing in your program at all.

Prerequisites for the assignment ( Short! Length 3:40)
The assignment (Length 42:01)
Some helpful hints (Length 6:38)

Why do we need iterators ? Start writing your first programming assignment and you will discover why.

Parse an arithmetic expression - better algorithm than the book !

Video for Programming Assignment #2

Driver Program
A Problematic Doubly Linked List

Check here for assignments

Program #1 - due Monday Feb. 10 

Program #2 - due Wednesday March 4

Program #3 - due  Monday March 30

Program #4 - due Wednesday April 8

Approximate Schedule

Date Read Notes
Weeks 1, 2,3      
Chap 2
Chap 3
Mathematical background, elementary sorts

 Weeks 4,5,6        Chap 4
Chap 5
Stacks, Queues, Linked Lists
Linked Lists with Iterators

 Weeks 7,8,9
Chap 6
Chap 7
Recursion, Advanced Sorts

 Weeks 10,11,12
Chap 8
Chap 10

Trees, trees, trees

Weeks 13,14,15
Chap 11
Chap 12
Hash tables, heaps, heap sort

A contract:

I will:

-treat you with respect. This includes honoring your time.
-arrive to class on time
-not use a cell phone during class
-not engage in any social networking while in class
-will return exams, quizzes and assignments in a timely manner. Typically, this will be within one week.

I expect the following from each of you:

- that you treat me with the same respect you would like me to show you
- you will arrive to class on time
- you will put your cell phones on "Silence" and not engage in any texting at all during class. In fact, you should not even look at your cell phone during class.
- you will use your computer for class purposes only. You will not Facebook, Twitter, or engage in any other non-class related activities
- you will approach me with any questions concerning the class at the earliest possible time. Coming to my office 3 months into the semester and telling me "I don't understand" is unacceptable.