CS 122 Algorithms and Data Structures

Fall 2004

General Information

Instructor

Xiao Qin

Office

SPEARE 146

Email

xqin@cs.nmt.edu

Telephone

(505)835-5902

Web

http://www.cs.nmt.edu/~xqin

Office Hours

M 13:00-14:00

W 14:00-15:00

(You can also ask for an appointment by e-mail)

COURSE HOURS

MW 11:00-12:15, MSEC 101

 

 

ASSISTANTS

Adam Roth                 aroth@nmt.edu

Office                          Speare 138

Office Hours              W 15:15-16:15

                                    F  16:00-17:00

 

 

 

TEXT BOOK

Adam Drozdek, “Data Structures and Algorithms in C++,” by Thomson Learning, 2nd Edition, 2001, ISBN: 0-534-37597-9.

Course Syllabus

Grades

Exams

Midterm exam was held on Oct. 18, 2004, between 11:00 and 12:15. The location will be MSEC 101.

The final will be held on Dec. 13, 2004, between 1:30PM and 3:00PM. Please mark your calendars now. The location will be MSEC 101.

Assignments

Assignments can be downloaded from here. No hardcopies will be provided. Each homework will have specific instructions for deadlines and delivery. Those assignments and their due dates will be listed here as they are assigned. There is a 20% deduction for late homework. The deduction becomes 50% if the homework is two days late. No credit is given after three days. Please hand in assignments to the lab TA.

 

Lecture Slides

Week

Topics

Reading Assignments

Related Slides

8/25/2004

Overview of course, Object-Oriented Programming.

Ch. 1

 Introduction and review

 The code for the Laptop  class

8/30/2004

Big-O Notation, Big-Omega and Big-Theta Notations, Asymptotic Complexity.

Ch.2

  Complexity Analysis

9/1/2004

Structured data type, Abstract data type, and Class data type.

Ch.1

 Structured Types and Classes

 9/8/2004

 Linked lists, Dynamic linked lists, Traversal, Insertion, and Deletion of Elements in a dynamic linked list.

Ch.3.1

  Linked Lists

 9/13/2004

 Doubly linked lists, circular lists, skip lists, and linked stacks Ch.3.2-3.4, and Ch.4.1  Doubly linked lists and stacks

 9/15/2004

Stacks and Queues

 Ch 4.1-4.2  Stacks and Queues

 9/20/2004

 Recursive definitions, BNF, Activation Stack, Recursive functions, indirect recursion Ch5.1-5.3  Recursion 1
9/22/2004 Tail recursion, Recursive function call, Tracing with multiple recursive calls, rules of recursion Ch5.4-5.8  Recursion 2
9/27/2004 Trees, Recursive definition of a binary trees, and Mathematical properties Ch6.1-6.2  Binary Trees 1
9/29/2004 Mathematical properties, Array representation, and Linked representation,  Ch6.2-6.3  Binary Trees 1
10/4/2004 Binary search trees, insertion, and deletion Ch6.3, 6.5-6.6  Binary Trees 2
10/6/2004 No Class
10/11/2004 Binary expression trees, Binary Tree Traversal Ch 6.4,6.10  Binary Trees 3 and Binary Trees 4
10/13/2004

Traversal applications, and Review

 Ch1-6
10/18/2004 Mid-Term Exam Ch1-6
10/25/2004 Balanced trees, DSW algorithm, AVL trees Ch 6.7  Balancing Trees
10/27/2004 Graphs representation, Depth First Search  Ch8.1-8.2  Graphs 1
11/1/2004 Breadth First Search, shortest paths Ch8.2-8.3  Graphs 2
11/3/2004 Positive weighted shortest path, spanning trees Ch8.3, 8.5  Graphs 2
11/8/2004 Spanning trees, connectivity Ch8.5-8.6  Graphs 3
11/10/2004 Topological sort, maximum flows Ch8.7-8.8  Graphs 4
11/15/2004 Maximum flows, matching Ch8.8-8.9  Graphs 5
11/17/2004 Insertion sort, selection sort, and bubble sort Ch9.1  Sorting 1
11/22/2004 Heap Sort Ch9.3.2  Sorting 2
11/29/2004 Quick Sort Ch9.3.3  Sorting 3
12/1/2004 Merge Sort Ch9.3.4  Sorting 3
12/6/2004 Hashing Ch10.1-10.2  Hashing
Acknowledgements: 
Lecture slides are modified from those made available by Dr. William Spears with the University of Wyoming and Terry B. Gillette with the Florida Institute of Technology.

 Misc Related Material

Instructor Wiley's C++ Tips

gdb Tutorial