Subscribe

Archives

Categories

Attribution-NonCommercial-ShareAlike 4.0 International

Except where otherwise noted, content on this site is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license.

Syllabus

CSCI 33500: Software Analysis and Design 3

3 hrs, 3 credits. Computer Science, City University of New York (CUNY) Hunter College.

Details

Field Value
Instructor: Raffi Khatchadourian
Office: 1090H Hunter North Building
Email: raffi.khatchadourian@hunter.cuny.edu
Phone: (212) 650-3988
Office hours: See my website.
Semester: Spring 2022
Section: CSCI 33500-01

Course Content and Objectives

This course is the sequel to CSCI 235, and as such, a major objective is to deepen and enhance your programming skills as well as knowledge of various advanced algorithms. The course will cover algorithm analysis, advanced trees, special priority queues, sorting algorithms, disjoint sets, graph algorithms, dynamic programming, randomized algorithms, and amortized analysis.

Prerequisites

  • CSCI 23500
  • MATH 15500

Textbooks

Title Publisher Edition Author ISBN Type Comment
Data Structures and Algorithm Analysis in C++ Pearson 4 Mark Allen Weiss 978-0132847377 Required
Introduction to Algorithms McGraw-Hill Cormen, Leiserson, Rivest, and Stein Optional Comprehensive and advanced.
The Art of Computer Programming, Volumes I through III Addison-Wesley Knuth Optional Valuable texts for Computer Scientists.
Algorithms in C++, Parts 1--4 and Part 5 Addison-Wesley Robert Sedgewick Optional In-depth algorithm analysis.
Effective Modern C++: 42 Specific Ways to Improve Your Use of C++11 and C++14 Scott Meyers Optional Modern C++ techniques.

Succeeding in this Course

If you want to succeed in this course, do all of the following:

  • Do the assigned readings before the lecture, not after it.
  • Make a list of questions before the class.
  • Submit all assignments on time.
  • Solve a set of problems at the end of each chapter.
  • Study for exams.
  • Do all assignments yourself! Expect severe penalties for plagiarism.

Organization

Syllabus and Readings

At the end of this document, you can see which parts of the textbook we will cover. You are responsible for everything in the listed chapters regardless of how much time we spend on them in class. As noted above, you should read ahead so that you can ask questions in class to clear up anything you find confusing.

Assignments

No one can become proficient at programming without writing many programs. I will assign five assignments during the semester.

Every program must satisfy the programming rules stated in the rules.html (posted on Blackboard) document. Please read it very carefully. Rules governing lateness, plagiarism, and how they are graded are also contained there. You are not allowed to work in groups. You can discuss about the assignments. However, copying of pieces of code among peers is a serious problem. It is critically important that all submitted program listings and executions be thoroughly documented. Each assignment will count for 12% of your final grade. That means that the five assignments will constitute 60% of your final grade. You are allowed to use the source code that is provided by the book.

All programs must compile and run. Zero credit will be given for programs that do not compile or do not run. The homework assignments will only state the major objectives of the program to be written; it will be often up to you to make design decisions regarding I/O, efficiency, error handling, and so on. Make sure you provide adequate test cases to indicate the correctness and robustness of your approaches.

Each will be assigned in Blackboard along with submission instructions. I have designed this course to be self-contained. Thus, the only resources you need to answer the questions are contained within the course. Searching the web (e.g., Google) for answers is not only unnecessary but also risks academic violations, which can result in course failure.

Notes

  • Deadlines and due dates for assignments will be assigned in class.
  • Late assignments will be penalized.
  • No extensions will be given for extra credit assignments.
  • Assignments are the result of individual effort unless otherwise noted (e.g., group projects).

Exams

Test make-ups will be given if and only if:

  • the request is made sufficiently in advance of the test, and
  • the make-up is scheduled prior to the next class.

Class Meetings

Professional Presence

Every student is expected to present themselves in a professional manner. Students with questions or who wish to participate during the lecture are encouraged to raise their hands during class.

Attendance

Attendance is expected for each and every class meeting. The instructor will start the class on time, and students are expected to be present on time.

Course Material and Communication

All course material (e.g., slides, course documents, announcements, homework) will be posted on Blackboard.

Email

  • Emails to the instructor must be via a CUNY Hunter College email addresses for FERPA reasons.
  • Include the class name or number in the subject line of the email.
  • Email thread hijacking is strongly discouraged. Ensure that the subject of your email matches its contents.
  • Post all class-related discussions on the Bb discussion board. Students are highly encouraged to "subscribe" to the general forum to receive email notifications regarding new posts.
  • Ensure that your correct (CUNY) email address is entered into the CUNY Blackboard.

Bulletin Board

You should check the Blackboard site regularly since all class material will be posted there. Please make sure you have configured Bb to use your CUNY email address. You are responsible for any email the instructors might send there.

Grading

Category Percentage
Assignments (5; lowest grade dropped) 60%
Midterm Exam 15%
Final Exam (non-accumulative) 25%

Key Dates

Event Date
College Closed–No classes scheduled Feb 11
Midterm Exam Mar 18
Recess Apr 15--Apr 22
Withdrawal Deadline May 17
Final Exam May 24 11:30--1:30 pm

Resources

Source code from the book can be found here.

C++ STL

C++ STL Exceptions

Source Code Documentation Generating Tool (Doxygen)

Learning goals

This class satisfies the following learning goals:

  1. Demonstrate an understanding of the basic foundations and relevant applications of mathematics and statistics, particularly those branches related to computer science.
  2. Understand the relationship between computer architectures and software systems.
  3. Deep practical knowledge of one widely used programming language (C++).
  4. Be experienced in working in at least two widely used operating system environments.
  5. Be able to apply principles of design and analysis in creating substantial programs.
  6. Be able to communicate technical ideas effectively, both in writing and in oral presentations.

Academic Violations

CUNY Hunter College regards acts of academic dishonesty (e.g., plagiarism, cheating on examinations, obtaining unfair advantage, and falsification of records and official documents) as serious offenses against the values of intellectual honesty. The college is committed to enforcing the CUNY Policy on Academic Integrity and will pursue cases of academic dishonesty according to the Hunter College Academic Integrity Procedures. Special attention is given to CONTRACT CHEATING (this is where students have work completed on their behalf which is then submitted for academic credit). Academic violations will be pursued to the fullest extent possible, including failure from the course.

Computer Science Facilities & Labs

  • All Computer Science students can use any of the general-purpose labs throughout Hunter College.
  • Computer Science majors and students enrolled in CSCI courses can obtain an account on the Computer Science Department Network. More information can be found on the Computer Science Department's website.

Credit/No Credit Policy & Special Enrollment Permission

The instructor will not approve C/NC requests for this course. However, such requests may be approved by the college on a per-semester basis; students are encouraged to check the college policies. Students are also encouraged to discuss these options with their academic advisors. Special enrollment permissions, e.g., prerequisite waivers, will not be granted without substantial supporting evidence, e.g., sufficient professional experience.

ADA Compliance

In compliance with the American Disability Act of 1990 (ADA) and with Section 504 of the Rehabilitation Act of 1973, Hunter College is committed to ensuring educational parity and accommodations for all students with documented disabilities and/or medical conditions. It is recommended that all students with documented disabilities (Emotional, Medical, Physical and/or Learning) consult the Office of Accessibility located in Room E1124 to secure necessary academic accommodations. For further information and assistance please call (212-772-4857)/TTY (212-650-3230).

Sexual Misconduct

In compliance with the CUNY Policy on Sexual Misconduct, Hunter College reaffirms the prohibition of any sexual misconduct, which includes sexual violence, sexual harassment, and gender-based harassment retaliation against students, employees, or visitors, as well as certain intimate relationships. Students who have experienced any form of sexual violence on or off-campus (including CUNY-sponsored trips and events) are entitled to the rights outlined in the Bill of Rights for Hunter College.

  1. Sexual Violence: Students are strongly encouraged to immediately report the incident by calling 911, contacting NYPD Special Victims Division Hotline (646-610-7272) or their local police precinct, or contacting the College's Public Safety Office (212-772-4444).
  2. All Other Forms of Sexual Misconduct: Students are also encouraged to contact the College's Title IX Campus Coordinator, Dean John Rose (jtrose@hunter.cuny.edu or 212-650-3262) or Colleen Barry (colleen.barry@hunter.cuny.edu or 212-772-4534) and seek complementary services through the Counseling and Wellness Services Office, Hunter East 1123. CUNY Policy on Sexual Misconduct Link: http://www.cuny.edu/about/administration/offices/la/Policy-on-Sexual-Misconduct-12-1-14-with-links.pdf

Counseling & Wellness Services

Counseling & Wellness Services (CWS) provides mental health, health, and wellness services aimed at enhancing students' quality of life and maximizing personal and academic growth and development. More information can be found on the Counseling & Wellness Services website.

Special Needs

Students with special needs should see me for accommodation at least two weeks prior to the due date of any assignment or exam.

Family Educational Rights and Privacy Act (FERPA)

The Family Educational Rights and Privacy Act (FERPA) (20 U.S.C. § 1232g; 34 CFR Part 99) is a Federal law that protects the privacy of student education records. The law applies to all schools that receive funds under an applicable program of the U.S. Department of Education.

FERPA gives parents certain rights with respect to their children's education records. These rights transfer to the student when he or she reaches the age of 18 or attends a school beyond the high school level. Students to whom the rights have transferred are "eligible students."

  • Parents or eligible students have the right to inspect and review the student's education records maintained by the school. Schools are not required to provide copies of records unless, for reasons such as great distance, it is impossible for parents or eligible students to review the records. Schools may charge a fee for copies.
  • Parents or eligible students have the right to request that a school correct records which they believe to be inaccurate or misleading. If the school decides not to amend the record, the parent or eligible student then has the right to a formal hearing. After the hearing, if the school still decides not to amend the record, the parent or eligible student has the right to place a statement with the record setting forth his or her view about the contested information.
  • Generally, schools must have written permission from the parent or eligible student in order to release any information from a student's education record. However, FERPA allows schools to disclose those records, without consent, to the following parties or under the following conditions (34 CFR § 99.31):
    • School officials with legitimate educational interest;
    • Other schools to which a student is transferring;
    • Specified officials for audit or evaluation purposes;
    • Appropriate parties in connection with financial aid to a student;
    • Organizations conducting certain studies for or on behalf of the school;
    • Accrediting organizations;
    • To comply with a judicial order or lawfully issued subpoena;
    • Appropriate officials in cases of health and safety emergencies; and
    • State and local authorities, within a juvenile justice system, pursuant to specific State law.

Schools may disclose, without consent, "directory" information such as a student's name, address, telephone number, date and place of birth, honors and awards, and dates of attendance. However, schools must tell parents and eligible students about directory information and allow parents and eligible students a reasonable amount of time to request that the school not disclose directory information about them. Schools must notify parents and eligible students annually of their rights under FERPA. The actual means of notification (special letter, inclusion in a PTA bulletin, student handbook, or newspaper article) is left to the discretion of each school.

For additional information, you may call 1-800-USA-LEARN (1-800-872-5327) (voice). Individuals who use TDD may use the Federal Relay Service.

Or you may contact us at the following address:

Family Policy Compliance Office U.S. Department of Education 400 Maryland Avenue, SW Washington, D.C. 20202-8520

Syllabus Change Policy

This syllabus is subject to change. Students may be informed of changes via GitHub.

Outline and Schedule of Course Topics

This schedule is tentative. All due dates will be posted on the Bb calendar.

Date Topics Reading (Ch.) Deadlines
1/28 Introduction - C++ basics 1
2/1 -//- -//-
2/4 -//- -//-
2/8 Algorithm Analysis 2
2/11 No class
2/15 -//- -//-
2/18 Review of Vector/List and Iterators 3
2/22 Review (cont.) #1 due
2/25 Trees (AVL) 4.1-4.3
3/1 Trees (cont.)
3/4 Trees (Splay Trees, B-Trees) 4.5, 4.6-4.7
3/8 Sets/Maps 4.8
3/11 Hashing 5
3/15 -//-
3/18 Midterm Exam #2 due
3/22 Heaps 6
3/25 Midterm exam solution review -//-
3/29 Heaps -//-
4/1 Assignment 3 intro -//-
4/5 Heaps -//-
4/8 Sorting 7.1-7.7
4/12 Sorting 7.8-7.9
4/15 No class - Spring Break #3 due
4/19 No class - Spring Break
4/22 No class - Spring Break
4/26 Union/Find 8
4/29 Graph Algorithms 9.1-9.3
5/3 -//- 9.4-9.6
5/6 -//- (NP) 9.7 #4 due
5/10 Greedy Algorithms 10.1.1, 10.1.3
5/13 Divide and Conquer 10.2
5/17 Divide and Conquer (cont.)/Dynamic Programming 10.3
5/24 Final Exam 11:30--1:30 pm #5 due

Instructor Biography

Raffi Khatchadourian is an Assistant Professor in the Computer Science Department at Hunter College and the Graduate Center of the City University of New York (CUNY). He received his MS and Ph.D. degrees in Computer Science from Ohio State University and BS degree in Computer Science from Monmouth University in New Jersey. Prior to joining CUNY, he was a Software Engineer at Apple, Inc. in Cupertino, California, where he worked on Digital Rights Management (DRM) for iTunes, iBooks, and the App Store. He also developed distributed software that tested various features of iPhones, iPads, and iPods. Raffi's research focus is techniques for automated software evolution, particularly those related to automated refactoring and source code recommendation systems with the goal of easing the burden associated with correctly and efficiently evolving large and complex software.

Fork me on GitHub