CSCI 340 Data Structures and Algorithm Analysis Fall 2012

Instructor

Professor Nathalie Japkowicz

Office: PM 559

Phone: (815) 753-3846

E-mail: nat@cs.niu.edu

Office Hours: Tuesday/Thursdays 11am-12pm

Geoffrey Miller

Office: PM 254

Phone: (815) 753-3935

E-mail: Z1644162@students.niu.edu

Office Hours : Monday/Wednesday 9 :30am-12:30pm

Important Information

· Keep on checking http://omega.onyuksel.net/courses/340/index.html for important announcements (including assignments) as well as useful resources.

· Assignments must be submitted to the TA in two formats:

o On-line, by submission as described at http://omega.onyuksel.net/courses/340/index.html

o On paper, by submission to the TA (The paper and online submissions must be identical. The TA will use the paper copy to record his comments)

Meeting Times and Locations

Time: Tuesday/Thursday: 9:30am – 10:45am

Location: PM 203

Required/Recommended Material:

Textbooks

· Required: The C++ Standard Library: A Tutorial and Reference, Nicolai M. Josuttis, Addison-Wesley, 1999

· Recommended: Data Structures and Algorithm Analysis in C++, third edition, Mark Allen Weiss, Addison Wesley, 2006 — The lecture slides will be mostly based on this book.

The slides presented in class will be available on Blackboard.

Course Description

The application of analysis and design techniques to nonnumeric algorithms on data structures. The utilization of algorithmic analysis and design criteria in the selection of methods for data manipulation. PRQ: CSCI 241

Evaluation

Your final grade will be broken down as:

· 20% ……………………………. Assignments

· 25% ……………………………. Midterm 1

· 25% …………………….……… Midterm 2

· 30% …………………….……… Final exam

The grading scale used for this course is:

A: 90-100%

B: 80-90%

C: 70-80%

D: 60-70%

F: 0-60%

There is no rounding up to the nearest letter grade.

Assignments

There will be several computer assignments in programming language C++. These assignments need to be coded, tested, run, and debugged on the Computer Science Department’s Unix-based system.

You must include the following information (in the form of a “Doc.-Box”) at the top of each computer assignment that you turn in for grading:

a) Your name,

b) The assignment number, and

c) The date the assignment is due.

The course TA will grade all computer assignments. When your assignment is ready, submit the source codes of your computer assignment to your TA for grading. If you have any questions about the grading of one of your assignments, or if you do not agree with the way that one of your assignment is graded, you must confer with your TA first. If you’re still not satisfied with your grade, bring your graded assignment to your instructor. On reviewing your assignment, your instructor may assign a grade that differs from the one given by your TA. The new grade may be higher or lower than the grade given by your TA.

The maximum grade that you can receive for a late assignment will be reduced by 10% of the maximum possible points for each day – includes weekends and university holidays – that the assignment is late.

Computer assignments will be graded using the following criteria:

a) Program output and compliance with the stated objectives and specification of the

assignment => 60%

b) Structure and efficiency => 20%

c) Documentation => 20%2

Any computer assignment that is submitted for grading that contains any compile-time errors, will receive zero points.

Course Web Page and E-mails:

Hard copies of handouts of computer assignments will not be available, but they will be posted as PDF files on the course web page at http://omega.onyuksel.net/courses/340/index.html. Also, any additional information for an assignment can be posted on the course web page or sent to you by an e-mail, so you are responsible of checking the course web page and your e-mails on a regular basis.

Attendance:

You’re responsible for all material presented in class. If you miss a lecture, be sure to obtain class notes from a classmate before the next class meeting.

Independent Work:

Everything that you do in this course must reflect your own work. If you copy all or part of another student’s work, no matter where or how you get it, it will be considered as an act of cheating. This is not to discourage discussions among classmates. However, discussions should not be as extensive and detailed as to border on collaboration.

Cheating of any form cannot be tolerated. Any student caught on cheating will receive a grade of an F for the course with possible disciplinary action from the university.

Tentative Schedule (The assignments will be announced in class and posted at http://omega.onyuksel.net/courses/340/index.html

Week	Week of	Topics	Slide Set Numbers	Exams
1	Aug 27	Course Organisation; Algorithm Analysis, Overview of the C++ Standard Template Library (STL)	1, 2, 3, 4
2	Sept 3	Basic Data Structures: Arrays, Lists, Stacks, Queues STL Sequence Containers: String, Vector, Stack, Queue, Dequeue, List STL Iterators	5, 6, 6-extra1, 6-extra2
3	Sept 10	STL Sequence Containers (cont’d): Stack, Queue, Dequeue, List STL Iterators, Functors STL Associative Containers: Set, Multiset, Map, Multimap	6-extra3, 6-extra4, 6-extra5, 7, 7-extra1, 7-extra2
4	Sept 17	Beginning of Term Question Session (Homework, Course Contents, Programming, etc.); Algorithms: Sorting STL Algorithms: Non-modifying Sequence Operations, Modifying Sequence Operations, Sorting	8 8-extra1
5	Sept 24	Binary Trees: Concepts, Binary Search Trees, Insertions, Deletions, Traversals Binary Search Trees: Search, Insertion, Deletion	9 10
6	Oct 1	Beginning of Term Question Session (Homework, Course Contents, Programming, etc.); Midterm 1 Review
7	Oct 8	Midterm 1 Balancing a Tree: Overview, AVL Trees	11	Midterm 1
8	Oct 15	Balancing a Tree (cont’d): B-Trees Heaps: Heaps as Priority Queues	11 12
9	Oct 22	Heaps (cont’d): Organizing Arrays as Heaps Tree Applications	12 13
10	Oct 29	Dictionnaries More Sorting	14 15
11	Nov 5	Hashing	16
12	Nov 12	Midterm 2 Review Midterm 2		Midterm 2
13	Nov 19	Hashing (cont’d) Thanksgiving Break	16
14	Nov 26	Graphs: Representation, Traversals, Shortest Paths	19
15	Dec 3	Graphs (cont’d): Spanning Trees, Topological Ordering, Cycle Detection Final Review	19
16	Dec 10	Finals week		Final