Syllabus for CSC216
Data Structures and Algorithm Analysis
4 Credit Hours (3/2 lecture/lab)
Online ANYTIME
Spring 2021
Harper College

SECTION

Class will meet:

Section Time Days Room
W01 It's online, silly. Just email me and I'll respond during my office hours!

from Jan 19th to May 21st.

FINAL TIME

Your final will be during the first three (3) days of Finals Week — May 17-May 19.

PREREQUISITE

CSC 122 (computer science II) with a grade of C or better
OR
consent of instructor
[it is recommended that you had a B or better to actually do well in this class — as this class is more demanding/challenging in time and intellectual difficulty]

TEXTS

Data Structures and Algorithms Using C++; Goodrich, et al; Wiley, 2nd Edition

OR

Data Structures and Algorithms Using Java; Goodrich, et al; Wiley, 6th Edition

Your choice depends on which language you want to code in.

OTHER TEXTS
(you might find useful)

Big C++, Horstmann & Budd, John Wiley & Sons
Accelerated C++, Koenig & Moo, Addison Wesley
Problem Solving with C++, Savitch, Addison Wesley
Data Structures With C++ Using STL, Ford & Topp, Prentice Hall
C++ from the Ground Up, Schildt, Osborne
STL from the Ground Up, Schildt, Osborne
STL Tutorial and Reference Guide; Musser, Derge, Saini; Addison Wesley
Effective STL, Meyers, Addison Wesley
C++: The Core Language, Satir & Brown, O'Reilley & Associates, Inc.
Practical C++ Programming, Oualline, O'Reilley & Associates, Inc.
The ANSI/ISO C++ Professional Programmer's Handbook, Kalev, Que Professional
The C++ Programming Language, Bjarne Stroustrup, Addison Wesley
Big Java, Horstmann, John Wiley & Sons
Absolute Java, Savitch, Addison Wesley
Data Structures, Algorithms, and Applications in Java, Sahni, McGraw Hill
Data Structures and Algorithm Analysis in Java, Weiss, Addison Wesley
Compared to What? An Introduction to the Analysis of Algorithms, Rawlins, Computer Science Press
SAMS Teach Yourself Data Structures and Algorithms in 24 Hours, Lafore, MacMillian

COURSE DESCRIPTION

Provides exposure to techniques for storing and manipulating data. Includes discussion of insertion, deletion, and retrieval algorithms for stacks, queues, deques, linked lists, trees, etc. Emphasizes algorithm analysis as it builds on topics from previous course (CSC 122).

Emphasizes mathematics, engineering, science, and computer science applications.

Designed as the third of a sequence of courses (CSC 121, CSC 122, CSC 216 and CSC 217) for students majoring in Computer Science.

STUDENT OUTCOMES (The student should...)
  1. know the formal definitions of basic data types and structures (list, stack, queue, tree, table, graph, network, etc.) as abstract data types (ADTs).
  2. recognize the role of ADTs in realistic, large-scale applications.
  3. have implemented some applications of stacks and queues (and other ADTs) in an object-oriented language.
  4. be able to and have analyzed various sorting and searching algorithms.
  5. understand algorithms for graph and network traversal.
  6. be able to apply methods to determine properties of random number generators (randomness, usability, appropriateness to application.
OBJECTIVE

To foster the student's understanding of proper storage and retrieval of data. We will emphasize algorithm analysis to compare various approaches and determine which is best for different situations. Either the C++ or Java programming language may be used.

EVALUATION
Activity Percent
Tests35 %
Paper9 %
Projects18 %
Labs19 16 %
Homework19 16 %
Participation 6 %
Total100 %
Grade Percentage
A 90-
B 80- 90
C 70- 80
D 60- 70
F 0- 60
 

Also note that you cannot earn a C in this course without having shown at least a 70% competency on each and every topic covered during the semester (not a 70% average over all topics, but 70% on each topic). (See main page for the course for a topic list.)

The homework, labs, paper, and projects portions of your grade will come from the three portfolios you will be handing in (see below). Tests will be done in lecture time — not take-home.

TESTING

Lecture tests consist (most often) of true/false, fill in the blank (no word list), short answer, and hand-execution of code. Lecture tests may also include hand-coding of small (5-15 line) segments of code. Multiple choice can also occur, but all correct answers must be chosen (i.e. it isn't multiple guess). Finally, matching is a rare occurrence. (The online homework makes a pretty good sample of questions and style.)

Make-up exams (with reasonable excuse — see participation), will be ALL essay and/or hand-coding/execution.

Also there will be five tests (including the final) during the semester. This means that each test will be worth 7% of your overall grade.

ASSIGNMENTS

When an assignment is given (i.e. placed on the web page), you can hand it in as soon as you are done for a review of its content. ('done' here means that you've made a reasonable attempt to start the program or answer the questions. You don't have to have it perfect before you hand it in. You can even hand in something you've merely outlined/flow-charted, if it is a complete enough outline.)

I will give the checked paper back to you ASAP so that you can make any needed corrections to it before using it in a portfolio (if you so choose). You can also hand papers in as many times as you like before the portfolio is due. (Remember that this corrections policy is good for ANY of the online assignments: the paper, projects, labs, and even homework.)

Finally, every assignment will also be rated (typically between 1 and 7) as to its difficulty (1 is quite easy, 7 is fairly challenging). These ratings will help you determine what (corrected) assignments you'd like to hand in for your portfolios. Also, labs and projects often have options which can be done that will increase the level rating of the assignment.

PORTFOLIOS

Three times during the semester, you will turn in what you consider to be your best work up to that point (since the last portfolio). Collect together your best (corrected) assignments and hand them in as a portfolio. (This doesn't have to be a fancy bound work, just make sure your papers aren't going to go flying around. It is a good idea to have your name on each item as well.) The portfolio must contain a project (2 during the semester) or paper (1 during the semester) as well as a certain total ratings value each of homework and labs and consist of only a certain total number of items. These totals will be mentioned in the portfolio announcement on the web page and/or during class. The announcement is purposely delayed until at least a week before the due date so that you will concentrate on doing and understanding and not meeting minimum requirements.

Any assignments you turn in that exceed the total ratings value for their category will be added to an extra credit pile for review at the end of the semester. This extra credit work will be added to some part of your grade where it will do the most good (typically projects or tests).

Example: If the projects section of a portfolio said the minimum ratings value was 16 and the maximum number of projects were 4, you could choose several different combinations of project ratings to satisfy these requirements. You might choose to hand in 3 projects which were rated 6. You might choose to hand in 4 projects rated 4. You might choose to hand projects in rated at 4, 6, and 7.

You might choose to hand in a 4, a 6, and 2 7's. If you did this, I might place either the 4, the 6, or either of the 7's on the extra credit pile (the remaining items already add up to more than 16). To avoid me picking, you can mark those items you wish to be extra credit with XC or EC or XCred or Extra Credit marked in plain large type/writing at the top.

LATE POLICY

Due dates (on portfolios) are present for a reason. If you do not turn in your papers by the due dates given, credit may be denied. (Reasonable excuses may be accepted.)

TENTATIVE OUTLINE
Week(s) C++ Location Topic(s) Java Location
0 Chapters 1-2; Appendix A Review of Programming Basics & Math Stuff
(the math may not be needed, but it can't hurt you..!)
Chapters 1 & 2; online Appendix

1 Chapter 3
(skip recursion for now)
Linked Lists vs. Arrays & Recursion Chapter 3
2 Chapter 4
(skip the recursion stuff)
Algorithm Analysis Basics Chapter 4
3 Chapter 3 & 4
(now just the recursion!)
Recursion Chapter 5
4 Chapter 5 Stacks and Queues Chapter 6
5 Chapter 6 Iterators of a List Chapter 7
5, 6 Chapter 7 Trees Chapter 8
7, 8 Chapter 8 Heaps & Priority Queues Chapter 9
8, 9 Chapter 9 Hash Tables, Maps, & Skip Lists Chapter 10
(this is also where Sets are hiding)
10, 11 Chapter 10 Search Trees
(binary, AVL, and Red-Black only)
Chapter 11
12, 13 Chapter 11 Sorting, Sets, & Selection Chapter 12
(see Chapter 10 for Sets & Section 14.7.3 for Union-Find)
14 Chapter 13 Graph Algorithms Chapter 14
(this is also where Union-Find is hiding)

15 Chapter 12 Dynamic Programming Chapter 13
16 Chapter 14 Memory Management & B-trees Chapter 15

Those topics above the first horizontal rule are considered preperatory review topics. If you don't know them, you won't do well later on.

Those topics after the last horizontal rule are considered optional and may be covered or left out depending on the student's interests and available time.

Always look for online notes to supplement (and sometimes correct/override) the book information.

I reserve the right to change this syllabus with sufficient warning to you.