Course Information | Assignments | Labs | Lecture Notes |

 

.. I seek the knowledge of how little I know! ..

CIS*2520 Data Structures - Fall 2009
Course Information and Outline

Course Objectives and Methods

  • CIS*2520 will convey the concept of layered software by separating the application from the implementation using abstraction.
  • Students will acquire the skill of designing and implementing abstract data structures in C programming language.
  • When building data structures students will review methods of performance and complexity analysis of algorithms used for implementation.
  • Data structures will include lists, strings, queues, stacks, trees, dictionaries, hash-tables, and graphs.
  • Algorithms used include searching, sorting, recursion using the above data structures.
  • On assignments and exams, students are asked to solve problems using analytical methods and programming skills acquired from lectures and assignments to demonstrate knowledge and comprehension of course material.

Prerequisite(s):

(CIS*1910 or CIS*1900) or (ENGG*1500, ENGG*2410), CIS*2500

Equate(s):

CIS*2420

Instructor Information

Instructor Name

E-mail

Office

Tel. Extension

Prof. Xining Li

xli@cis.uoguelph.ca

Thornbrough 1389

56548

Course Format and Schedule

Day

Lecture Time

Room

Office Hours

Tuesdays/Thursdays

2:30 - 3:50 PM

MACK 029

Tuesdays 9:00 - 11:00 AM

Course Evaluation

Activity

Weight

Assignments

4 * 7% = 28%

Midterm Test

22%

Final Exam

50%

Total

100%

 


Important Notes

  1. Late assignments are NOT ACCEPTED, unless (see Note 3).
  2. Missed midterm test results in a mark of zero, unless (see Note 3).
  3. Illness and severe circumstances may be accommodated, email your instructor at least 48 hours before the due time and provide certification whenever possible.
  4. Your final grade will be based on the grading system published in the university calendar.
  5. To appeal a mark on an assignment, or the midterm test you must do so within two weeks after they are handed back.
  6. Academic misconduct includes the submission of program code or assignment answers that appear so similar to another student's work as to be semantically indistinguishable. Misconduct cases will be handles swiftly, discreetly, and summarily by the Department in accordance with University principles.

Text Book

Thomas A. Standish: Data Structures, Algorithms & Software Principles in C, Addison Wesley

Course Topics and Dates

Lecture Topics

Week

Lab Activity

Deadline of the week
  • Introduction to CIS*2520
  • Review of C Programming Language

1
  • Getting Started
  • C Language Basics
  • Compilaton and execution

None.
  • Recursion
  • Design of Algorithm
  • Linked lists

2
  • Pointer and list example
  • Assignment #1 discussion

Assignment #1 is published.
  • Stacks
  • Queues

 

3
  • Handling Errors  
  • Debugging
  • Common Coding Problems

None.
  • Analysis of algorithms
  • Complexity
  • O-notation

4
  • Stack and Queue examples
  • C execution stack
  • Assignment #2 discussion

Assignment #1 is due on Sept. 29, 2009, 23:59.
Assignment #2 is published.
  • More lists
  • Strings
  • Dynamic memory allocation

5
  • C libraries

 

None.
  • B-tree
  • Heap
  • AVL Trees

6
  • Working with strings
  • Dynamic memory allocation examples

 

None.
  • 2-4 Trees
  • Red-Black Trees
  • Tries

7
  • Tree Examples
  • Assignment #3 discussion

Assignment #2 is due on Oct. 20, 2009, 23:59.
Assignment #3 is published.
  • Graphs
  • Searching
  • Shortest path

8
  • Tree algorithms analysis
  • Mid-test Review

Midterm Test is on Oct. 29, 2009, in class.
  • Hashing
  • Tables

9
  • Assignment #4 discussion
  • Working with  tries

None.
  • Sorting Algorithms

10
  • Assignment #4 discussion
  • Working with graph algorithms

Assignment #3 is due on Nov. 10, 2009. 23:59.
Assignment #4 is published.
  • External data
  • Sorting 

11
  • Discuss sorting algorithms

None.
  • TBA

12
  • TBA

Assignment #4 is due on Dec. 1, 2009, 23:59.

Final Exam:   Check with the Registrar's office (also see WebAdvisor!)

For any suggestions or problems with this document, contact Xining Li.