Computer Science Department

 

Loyola College

 

CS 302 – Data Structures & Algorithms II

 

                                                     

    

Instructor:             Roberta E. Sabin                                    

Office:                   Donnelly Science 127C

 

Telephone:            (410) 617-2562

FAX :                     (410) 617-2157

E-mail: res@loyola.edu

 

                        Black Board Course Website:

                            http://www.loyola.edu/blackboard/index.html

      

                      Visit the CS Department WebSite: http://www.cs.loyola.edu

 

                                    Class Meets:  MWF 1-1:50 (in KH006)

 

Office Hours:      Monday, Wednesday, Friday:   11-11:50

                                                                Thursday:  10:50-12:15  

            Others times by appointment. (I am usually here every weekday except Tuesday.)

    

                                       

 

High thoughts must have high language.                                                                                                                                              – Aristophanes

 

You can’t trust code that you did not totally create yourself. (Especially code from companies that employ people like me.

                                                                                                                                                                   ---Ken Thompson, 1983 ACM Turing Award Lecture

 

Instead of this absurd division into sexes they ought to class people as static or dynamic.                                                              –Evelyn Waugh

 

Good as it is to inherit a library, it is better to collect one.                                                                                                                 -- Augustune Birrell

 

In programming, it is not enough to be inventive and ingenious. One also needs to be disciplined and controlled in order not be become entangled in one's own complexities.

--Harlan D. Mills, Forward to Programming Proverbs by Henry Ledgard

 

I have made this letter longer than usual, because I lack the time to make it short.                                                                                      –Blaise Pascal

 

CS 302                                     Data Structures & Algorithms II                                     3 credits

 

SYLLABUS

 

Catalog Description:                                                                                                                                                          Prerequisite: CS301.

A continuation of CS301.  More advanced data structures are designed, analyzed, and created using an object-oriented language.  File structures, hashing, and formal methods are studied.  More UNIX programming tools are introduced.

 

Text:  Folk, Zoellick, and Riccardi. File Structures, Addison-Wesley, 1998.  

Supplemental Reference:  Kernighan and Ritchie, The C Programming Language, Prentice-Hall, 1988.

 

Supplemental Software:  at ftp://ftp.aw.com/cseng/authors/riccardi/

 

Course Objectives:

  Upon successful completion of this course, the student should be able to:

1.      understand the basic issues in file management and be able to process large files of data

2.      be able to parse and write programs using standard C including C memory management

3.      further understand and use object-oriented design in software development  and represent class relationships with simple UML diagrams

4.      have increased understanding of object-oriented programming and the use of classes in C++ including template and derived classes

5.      competently use basic Linux utilities and a Linux-based IDE for program development

6.      have increased understanding of time efficiency issues as they relate to choices of algorithms and file management

7.      understand and be able to use sorting, searching, and recursive algorithms

8.      understand and implement complex data structures using original C++ code and the Standard Template Library (STL)

 

What you can expect of me: You can expect that I will come to class prepared and ready to help you learn.  You can expect me to be enthusiastic (easy since I LOVE computer science and teaching!), be knowledgeable, and keep the class moving.  You can expect me to be available during my office hours and at other times that you arrange to see me.  Expect me to return graded work promptly.  You can expect me to treat you respectfully.

 

What I expect of you:  I expect you to come to class prepared to contribute to class—computing is an active sport.  You CANNOT learn it in the passive mode. This means that you should have completed the assignment, done the reading, and determined what you need help in understanding.  You contribute to class by intelligently questioning the instructor and offering further explanation to me and your colleagues. I expect you to take responsibility for learning computer science—you won’t be sorry.  Further, I expect you to treat every other member of the class (including me) with respect.

 

Course Outline of Class Lectures:

 

Class No.

Date

Major Topics

References[1]

1

1/12 M

Intro to the course

Going back in time: C

Syllabus

CN

2

 1/14W

C language: memory allocation

CN

3

1/16 F

C and C++ file processing

2.1-2.6

4

1/21W

Files in Unix and Linux

2.7-2.10

5

1/23 F

File processing in C (con’t)

 

6

1/26 M

Secondary Storage: Disk and Tape

PA1 due

3.1-3.3

7

1/28 W

CDs

File management by the OS

3.4-3.10

8

1/30 F

Quiz 1

File Organizations

4.1

9

2/2 M

Using Buffers for file processing

4.2-4.5

10

2/4 W

Files of records

5.1-5.6

11

2/6 F

Compressing data

6.1-6.2

12

2/9 M

 Sorting and searching in files

6.3-6.4

13

2/11 W

Review of elementary file concepts

PA2 due

 

14

2/13 F

Test1

 

15

2/16 M

Indexing of files

7.1-7.3

16

2/18 W

Indexing (con’t)

7.4-7.10

17

2/20 F

Sorting  with Heapsort

8.1-8.4

18

2/23 M

External sorting with merging

8.5-8.8

19

2/25  W

More on external sorting

 

20

2/27 F

Quiz 2

3/ 17: PA3 due

 

 

The class schedule for the second half of the semester will be distributed on 3/8.

The second half of the course will cover several complex abstract data types, STL, and miscellaneous additional topics.

 

Exam:  Friday, April 30, 9AM, KH006 

 

 

GRADING

 

Your final grade will be determined by the number of points that you earn.  Approximately 1000 points will be possible this semester. They will result from:

Approximately 10 collected assignments                and 3 quizzes                                        =  250 points                                        

6 programming assignments (approximately)                                                         =  350 points

2 tests (100 points each)                                                                                            =  200 points

1 final exam                                                                                                                   =  200 points

Total       = 1000 points

Final letter grades will be calculated on a scale close to the following: 


A  =  91 - 100% (905-1000 points)

A- =  88 - 90% (875-904 points)

B+ =  85 - 87% (845-874 points)

                         B  =  81 - 84% (805-844 points)

                         B- =  78 - 80% (775-795 points)

C+ =  75 - 77% (745-774 points)

C  =  71 - 74% (705-744 points)

C- =  68 - 70% (675-704 points)

D+ =  65 - 67% (645-674 points)

D  =  60 - 64% (595-644points)

F  =   0 - 59% (594 or fewer points)

 

 

1.   Tests and quizzes are announced.  Consult the class schedule.

 

2.     Normally, a homework assignment is due at the beginning of each class. If an assignment is collected, it is assigned a value of 10-20 points.   Generally, half the points are awarded for completeness and half for correctness.   Correctness is determined by my checking all or a portion of the assigned exercises.

 

3.   Programming assignments will be given periodically.  Generally 10 days to 2 weeks are provided for the completion of a programming assignment.  Late programming assignments are NOT accepted, unless so stated when the assignment is given. Programming assignments are normally due at the beginning of the regular class period. See class schedule for dates.

 

4.    Please keep a record of the points you have earned.  This will enable you to calculate your current average and correct errors on my part.

 

CLASS PROCEDURES

 

1.     You are expected to have read the reference material listed in the class schedule before the lecture.  Both the textbook and the "breadth-first" notes present material in a very concise manner. You will greatly enhance your experience of the lectures by coming to class prepared. I normally distribute many handouts--copies of notes, assignment sheets, etc.   In the past, many students have increased their success in this course by keeping notes, programs, tests, and assignments organized.  A three-ring binder is recommended (sections for breadth-first topics, class notes, home assignments, and programming assignments may be helpful.)

 

2.        I will use Blackboard for dissemination of class materials. Blackboard will also hold copies of code snippets, classnotes, programming assignments, weekly assignments, data files, and important announcements.  Normally, you will submit your programming assignment BOTH in hardcopy and as a file dropped in the Peanuts’ dropbox.

 

3.        Regular attendance is necessary for success in this course.  As a point of courtesy, plan to arrive on time for class.  Students are responsible for material presented and assignments made during absences.  Normally, make-up exams are not administered and LATE ASSIGNMENTS ARE NOT ACCEPTED.

 

4.        This is a "hands-on" course.  Therefore, besides reading the texts, attending all classes, taking good notes, completing assignments and studying, to be successful in this course, you will need to spend a substantial amount of time in the lab or at your computer. Many students find they need five to eight such hours per week. Try to avoid pulling “all-nighters” to complete programming assignments.  No one thinks clearly or uses time effectively when he or she is exhausted.  Start planning a programming assignment when it is first distributed. Remember that the Linux Lab (DS130) is usually quiet and not crowded.

 

5.        Should you need extra help, please see me during office hours or make an appointment for a mutually convenient time.  Do NOT wait until you are totally lost and have failed a test or quiz.  Your success is my first priority.  Even if I am busy or seem distracted, please know that I am determined to be available to you for your assistance.