CSCI 340 Data Structures and Algorithm Analysis Spring 2013
Professor Nathalie Japkowicz
Office: PM 559
Phone: (815) 753-3846
E-mail: nat@cs.niu.edu
Office
Hours: Tuesday/Thursdays
11am-12pm
TAs
Section 1:
Geoffrey Miller
Office:
PM 254
Phone: 753-3935
Office
Hours: Monday/Wednesday/Friday 9am-11am
Section 2: John Doyle
Office:
PM 254
Phone: 753-3935
Office
Hours: Monday/Wednesday/Friday 11am-1pm
Important Information
·
Keep
on checking http://omega.onyuksel.net/~onyuksel/courses/340/index.html for important
announcements (including assignments) as well as useful resources.
·
Assignments
must be submitted to the TA on-line as described at http://omega.onyuksel.net/~onyuksel/courses/340/index.html
Section 1:
Time: Tuesday/Thursday: 9:30am – 10:45am
Location: PM 251
Section 2:
Time: Tuesday/Thursday: 12:30pm – 1:45pm
Location: PM 252
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 are
available on Blackboard.
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
Your final grade will be broken down as:
· 25% ……………………………. Assignments
·
25% ……………………………. Midterm 1 (February 21, 2013 In-Class)
· 25% …………………….……… Midterm 2 (April 2, 2013 In-Class)
·
25% …………………….……… Final exam (May 9, 2013
o
Section
1: 10am to 11:50am
o Section 2: 12pm to 1:50pm )
The grading scale used for this course is:
|
A: 80-100% |
B: 70-79% |
C: 60-69% |
D: 50-59% |
F: 0-49% |
There is no rounding up to the nearest letter grade.
Assignments
There will
be around 10-12 computer assignments in the C++ programming language. In
particular, the student will develop a good knowledge of C++’s Standard
Template Library (STL). The 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 code of your computer assignment (as will be described at http://omega.onyuksel.net/~onyuksel/courses/340/index.html)
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%
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/~onyuksel/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, by
e-mail and posted on http://omega.onyuksel.net/~onyuksel/courses/340/index.html)
|
Week |
Week of |
Topics |
Slide Set Numbers |
Exams |
|
1 |
January 14 |
Course Organisation; Algorithm Analysis, Overview
of the C++ Standard Template Library (STL) |
1, 2, 3,
4 |
|
|
2 |
January 21 |
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 |
January 28 |
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, |
|
|
4 |
February 4 |
STL Associative Containers: Set, Multiset,
Map, Multimap Algorithms: Sorting STL Algorithms: Non-modifying Sequence Operations, Modifying
Sequence Operations, Sorting |
7, 7-extra1, 7-extra2 8 8-extra1 |
|
|
5 |
February 11 |
Binary Trees: Concepts, Binary Search Trees, Insertions,
Deletions, Traversals |
9 |
|
|
6 |
February 18 |
Midterm 1 Review Midterm 1 (February 21) |
10 |
Midterm 1 |
|
7 |
February 25 |
Binary Search Trees: Search, Insertion, Deletion Balancing a Tree: Overview, AVL Trees |
10 11 |
|
|
8 |
March 4 |
Balancing a Tree (cont’d): AVL Trees, 2-3 Trees, B-Trees |
11 |
|
|
|
March 11 |
|
|
|
|
10 |
March 18 |
Heaps: Heaps as Priority Queues, Organizing Arrays as Heaps |
12 |
|
|
11 |
March 25 |
Tree Applications Midterm 2 Review |
13 |
|
|
12 |
April
1 |
Midterm 2
(April 2) Dictionnaries |
14 |
|
|
13 |
April
8 |
Dictionnaries (Cont’d) More Sorting |
14 15 |
|
|
14 |
April 15 |
Hashing |
16 |
|
|
15 |
April 22 |
Graphs: Representation, Traversals, Shortest Paths |
19 |
|
|
16 |
April 29 |
Graphs (cont’d): Spanning Trees, Topological
Ordering, Cycle Detection Final Review |
19 |
|
|
17 |
May
6 |
Finals
week |
|