CISC 3130

About

Stacks and their implementations. Prefix, postfix, and infix notation. Queues and linked lists and their implementations. Binary and general trees and their implementations and traversals. Sorting and searching techniques. Graph algorithms.

By the end of the course, you should be able to:

1. Demonstrate understanding of the abstract properties of various data structures such as stacks, queues, lists, and trees and be able to use these structures effectively in application programs.
2. Implement various data structures in more than one manner, compare the different implementations and explain the advantages and disadvantages of the different implementations.
3. Demonstrate understanding of and be able to program various sorting algorithms, and be able to compare the efficiency of these algorithms in terms of both time and space.
4. Trace and code recursive functions.
5. Demonstrate some understanding of object-oriented programming and be able to program with C++ classes.

---

The faculty and administration of Brooklyn College support an environment free from cheating and plagiarism. Each student is responsible for being aware of what constitutes cheating and plagiarism and for avoiding both. The complete text of the CUNY Academic Integrity Policy and the Brooklyn College procedure for implementing that policy can be found at this site: http://www.brooklyn.cuny.edu/bc/policies. If a faculty member suspects a violation of academic integrity and, upon investigation, confirms that violation, or if the student admits the violation, the faculty member MUST report the violation.

In order to receive disability-related academic accommodations students must first be registered with the Center for Student Disability Services. Students who have a documented disability or suspect they may have a disability are invited to set up an appointment with the Director of the Center for Student Disability Services, Ms. Valerie Stewart-Lovell at 718-951-5538. If you have already registered with the Center for Student Disability Services please provide your professor with the course accommodation form and discuss your specific accommodation with him/her.

Contact

Email:

connor@sci.brooklyn.cuny.edu

Office Hours:

Tuesday @ 10:45 - 11:45, 2109 Ingersoll Hall

Materials

Data Structures and Algorithms in C++ Fourth Edition by Adam Drozdek

Recommended Reading

• TIOBE Index (popularity of programming languages)
• The C Family of Languages
• Google C++ Style Guide
• lvalues and rvalues

Grading

• 10% Quiz (Weekly-ish)
• 30% Final
• 30% Midterm
• 30% Homework (Bi-Weekly-ish)

There are no makeup quizzes. I will occasionally accept late homework, but I will not mark it higher than a C. Your grades are available as a downloadable CSV file.

Slides / Notes

• Lecture 1
• Lecture 2
• Lecture 3
• Lecture 6
• Lecture Notes

Quiz

• Quiz 1
• Quiz 2

Examples

Example Final
• Linked List Animation
• Stack Delimiter Matching
• Example Midterm There will be questions about binary trees and binary seaarch trees on the midterm. Make sure that you can write the code for the three traversals we convered in lecture, as well as how to (quickly) find a value in a given binary search tree (Or what the text book calls an Ordered Binary Tree / Strong Binary Search Tree).

Homework

• Homework 1
  You can compile and run homework/homework1.test.cpp in the same directory as your SinglyLinkedList.h file, and you can check if the expected outputs match the actual outputs. If you see segfaults, then you have a bug!
• Homework 2 is from the Oxford Math Center.
  Complete the assignment described at: http://www.oxfordmathcenter.com/drupal7/node/631, using C++ instead of Java.
  The code we worked on in class is available here: homework2
• Homework 3 (optional)
  The code we worked on in class is available here.
  By popular request, here is an example using this JSON library: https://github.com/nlohmann/json.

  Warning!

  I wrote this on the train this morning, so there may be bugs: decisiontree.cpp
  And here is an example JSON file you can use with it: test.json
• Homework 4
• We will also do many example problems in class on Tuesday. Homework 5

Calendar

---